COIN-OR::LEMON - Graph Library

Changeset 2573:a9758ea1f01c in lemon-0.x for lemon


Ignore:
Timestamp:
02/18/08 04:30:12 (12 years ago)
Author:
Peter Kovacs
Branch:
default
Phase:
public
Convert:
svn:c9d7d8f5-90d6-0310-b91f-818b3a526b0e/lemon/trunk@3455
Message:

Improvements in CycleCanceling?.

Main changes:

  • Use function parameter instead of #define commands to select negative

cycle detection method.

  • Change the name of private members to start with "_".
  • Change the name of function parameters not to start with "_".
  • Remove unnecessary documentation for private members.
  • Doc improvements.
File:
1 edited

Legend:

Unmodified
Added
Removed
  • lemon/cycle_canceling.h

    r2556 r2573  
    2323///
    2424/// \file
    25 /// \brief A cycle-canceling algorithm for finding a minimum cost flow.
     25/// \brief Cycle-canceling algorithm for finding a minimum cost flow.
    2626
    2727#include <vector>
    2828#include <lemon/graph_adaptor.h>
     29#include <lemon/path.h>
     30
    2931#include <lemon/circulation.h>
    30 
    31 /// \brief The used cycle-canceling method.
    32 #define LIMITED_CYCLE_CANCELING
    33 //#define MIN_MEAN_CYCLE_CANCELING
    34 
    35 #ifdef LIMITED_CYCLE_CANCELING
    36   #include <lemon/bellman_ford.h>
    37   // The maximum number of iterations for the first execution of the
    38   // Bellman-Ford algorithm. It should be at least 2.
    39   #define STARTING_LIMIT        2
    40   // The iteration limit for the Bellman-Ford algorithm is multiplied by
    41   // <tt>ALPHA_MUL / ALPHA_DIV</tt> in every round.
    42   // <tt>ALPHA_MUL / ALPHA_DIV</tt> must be greater than 1.
    43   #define ALPHA_MUL             3
    44   #define ALPHA_DIV             2
    45 
    46 //#define _ONLY_ONE_CYCLE_
    47 //#define _NO_BACK_STEP_
    48 #endif
    49 
    50 #ifdef MIN_MEAN_CYCLE_CANCELING
    51   #include <lemon/min_mean_cycle.h>
    52   #include <lemon/path.h>
    53 #endif
    54 
    55 //#define _DEBUG_ITER_
     32#include <lemon/bellman_ford.h>
     33#include <lemon/min_mean_cycle.h>
    5634
    5735namespace lemon {
     
    6644  /// finding a minimum cost flow.
    6745  ///
    68   /// \param Graph The directed graph type the algorithm runs on.
    69   /// \param LowerMap The type of the lower bound map.
    70   /// \param CapacityMap The type of the capacity (upper bound) map.
    71   /// \param CostMap The type of the cost (length) map.
    72   /// \param SupplyMap The type of the supply map.
     46  /// \tparam Graph The directed graph type the algorithm runs on.
     47  /// \tparam LowerMap The type of the lower bound map.
     48  /// \tparam CapacityMap The type of the capacity (upper bound) map.
     49  /// \tparam CostMap The type of the cost (length) map.
     50  /// \tparam SupplyMap The type of the supply map.
    7351  ///
    7452  /// \warning
    75   /// - Edge capacities and costs should be non-negative integers.
    76   ///   However \c CostMap::Value should be signed type.
    77   /// - Supply values should be signed integers.
    78   /// - \c LowerMap::Value must be convertible to
    79   ///   \c CapacityMap::Value and \c CapacityMap::Value must be
    80   ///   convertible to \c SupplyMap::Value.
     53  /// - Edge capacities and costs should be \e non-negative \e integers.
     54  /// - Supply values should be \e signed \e integers.
     55  /// - \c LowerMap::Value must be convertible to \c CapacityMap::Value.
     56  /// - \c CapacityMap::Value and \c SupplyMap::Value must be
     57  ///   convertible to each other.
     58  /// - All value types must be convertible to \c CostMap::Value, which
     59  ///   must be signed type.
     60  ///
     61  /// \note By default the \ref BellmanFord "Bellman-Ford" algorithm is
     62  /// used for negative cycle detection with limited iteration number.
     63  /// However \ref CycleCanceling also provides the "Minimum Mean
     64  /// Cycle-Canceling" algorithm, which is \e strongly \e polynomial,
     65  /// but rather slower in practice.
     66  /// To use this version of the algorithm, call \ref run() with \c true
     67  /// parameter.
    8168  ///
    8269  /// \author Peter Kovacs
     
    8471  template < typename Graph,
    8572             typename LowerMap = typename Graph::template EdgeMap<int>,
    86              typename CapacityMap = LowerMap,
     73             typename CapacityMap = typename Graph::template EdgeMap<int>,
    8774             typename CostMap = typename Graph::template EdgeMap<int>,
    88              typename SupplyMap = typename Graph::template NodeMap
    89                                   <typename CapacityMap::Value> >
     75             typename SupplyMap = typename Graph::template NodeMap<int> >
    9076  class CycleCanceling
    9177  {
    9278    GRAPH_TYPEDEFS(typename Graph);
    9379
    94     typedef typename LowerMap::Value Lower;
    9580    typedef typename CapacityMap::Value Capacity;
    9681    typedef typename CostMap::Value Cost;
     
    11196    typedef typename Graph::template EdgeMap<Capacity> FlowMap;
    11297
    113   protected:
    114 
    115     /// Map adaptor class for handling residual edge costs.
    116     class ResCostMap : public MapBase<ResEdge, Cost>
     98  private:
     99
     100    /// \brief Map adaptor class for handling residual edge costs.
     101    ///
     102    /// \ref ResidualCostMap is a map adaptor class for handling
     103    /// residual edge costs.
     104    class ResidualCostMap : public MapBase<ResEdge, Cost>
    117105    {
    118106    private:
    119107
    120       const CostMap &cost_map;
     108      const CostMap &_cost_map;
    121109
    122110    public:
    123111
    124       ResCostMap(const CostMap &_cost) : cost_map(_cost) {}
    125 
     112      ///\e
     113      ResidualCostMap(const CostMap &cost_map) : _cost_map(cost_map) {}
     114
     115      ///\e
    126116      Cost operator[](const ResEdge &e) const {
    127         return ResGraph::forward(e) ? cost_map[e] : -cost_map[e];
    128       }
    129 
    130     }; //class ResCostMap
    131 
    132   protected:
    133 
    134     /// The directed graph the algorithm runs on.
    135     const Graph &graph;
    136     /// The original lower bound map.
    137     const LowerMap *lower;
    138     /// The modified capacity map.
    139     CapacityEdgeMap capacity;
    140     /// The cost map.
    141     const CostMap &cost;
    142     /// The modified supply map.
    143     SupplyNodeMap supply;
    144     bool valid_supply;
    145 
    146     /// The current flow.
    147     FlowMap flow;
    148     /// The residual graph.
    149     ResGraph res_graph;
    150     /// The residual cost map.
    151     ResCostMap res_cost;
    152 
    153   public :
     117        return ResGraph::forward(e) ? _cost_map[e] : -_cost_map[e];
     118      }
     119
     120    }; //class ResidualCostMap
     121
     122  private:
     123
     124    // The maximum number of iterations for the first execution of the
     125    // Bellman-Ford algorithm. It should be at least 2.
     126    static const int BF_FIRST_LIMIT = 2;
     127    // The iteration limit for the Bellman-Ford algorithm is multiplied
     128    // by BF_ALPHA in every round.
     129    static const double BF_ALPHA = 1.5;
     130
     131  private:
     132
     133    // The directed graph the algorithm runs on
     134    const Graph &_graph;
     135    // The original lower bound map
     136    const LowerMap *_lower;
     137    // The modified capacity map
     138    CapacityEdgeMap _capacity;
     139    // The original cost map
     140    const CostMap &_cost;
     141    // The modified supply map
     142    SupplyNodeMap _supply;
     143    bool _valid_supply;
     144
     145    // Edge map of the current flow
     146    FlowMap _flow;
     147
     148    // The residual graph
     149    ResGraph _res_graph;
     150    // The residual cost map
     151    ResidualCostMap _res_cost;
     152
     153  public:
    154154
    155155    /// \brief General constructor of the class (with lower bounds).
     
    157157    /// General constructor of the class (with lower bounds).
    158158    ///
    159     /// \param _graph The directed graph the algorithm runs on.
    160     /// \param _lower The lower bounds of the edges.
    161     /// \param _capacity The capacities (upper bounds) of the edges.
    162     /// \param _cost The cost (length) values of the edges.
    163     /// \param _supply The supply values of the nodes (signed).
    164     CycleCanceling( const Graph &_graph,
    165                     const LowerMap &_lower,
    166                     const CapacityMap &_capacity,
    167                     const CostMap &_cost,
    168                     const SupplyMap &_supply ) :
    169       graph(_graph), lower(&_lower), capacity(_graph), cost(_cost),
    170       supply(_graph), flow(_graph, 0),
    171       res_graph(_graph, capacity, flow), res_cost(cost)
     159    /// \param graph The directed graph the algorithm runs on.
     160    /// \param lower The lower bounds of the edges.
     161    /// \param capacity The capacities (upper bounds) of the edges.
     162    /// \param cost The cost (length) values of the edges.
     163    /// \param supply The supply values of the nodes (signed).
     164    CycleCanceling( const Graph &graph,
     165                    const LowerMap &lower,
     166                    const CapacityMap &capacity,
     167                    const CostMap &cost,
     168                    const SupplyMap &supply ) :
     169      _graph(graph), _lower(&lower), _capacity(graph), _cost(cost),
     170      _supply(graph), _flow(graph, 0),
     171      _res_graph(graph, _capacity, _flow), _res_cost(_cost)
    172172    {
    173173      // Removing non-zero lower bounds
    174       capacity = subMap(_capacity, _lower);
     174      _capacity = subMap(capacity, lower);
    175175      Supply sum = 0;
    176       for (NodeIt n(graph); n != INVALID; ++n) {
    177         Supply s = _supply[n];
    178         for (InEdgeIt e(graph, n); e != INVALID; ++e)
    179           s += _lower[e];
    180         for (OutEdgeIt e(graph, n); e != INVALID; ++e)
    181           s -= _lower[e];
    182         sum += (supply[n] = s);
    183       }
    184       valid_supply = sum == 0;
     176      for (NodeIt n(_graph); n != INVALID; ++n) {
     177        Supply s = supply[n];
     178        for (InEdgeIt e(_graph, n); e != INVALID; ++e)
     179          s += lower[e];
     180        for (OutEdgeIt e(_graph, n); e != INVALID; ++e)
     181          s -= lower[e];
     182        sum += (_supply[n] = s);
     183      }
     184      _valid_supply = sum == 0;
    185185    }
    186186
     
    189189    /// General constructor of the class (without lower bounds).
    190190    ///
    191     /// \param _graph The directed graph the algorithm runs on.
    192     /// \param _capacity The capacities (upper bounds) of the edges.
    193     /// \param _cost The cost (length) values of the edges.
    194     /// \param _supply The supply values of the nodes (signed).
    195     CycleCanceling( const Graph &_graph,
    196                     const CapacityMap &_capacity,
    197                     const CostMap &_cost,
    198                     const SupplyMap &_supply ) :
    199       graph(_graph), lower(NULL), capacity(_capacity), cost(_cost),
    200       supply(_supply), flow(_graph, 0),
    201       res_graph(_graph, capacity, flow), res_cost(cost)
     191    /// \param graph The directed graph the algorithm runs on.
     192    /// \param capacity The capacities (upper bounds) of the edges.
     193    /// \param cost The cost (length) values of the edges.
     194    /// \param supply The supply values of the nodes (signed).
     195    CycleCanceling( const Graph &graph,
     196                    const CapacityMap &capacity,
     197                    const CostMap &cost,
     198                    const SupplyMap &supply ) :
     199      _graph(graph), _lower(NULL), _capacity(capacity), _cost(cost),
     200      _supply(supply), _flow(graph, 0),
     201      _res_graph(graph, _capacity, _flow), _res_cost(_cost)
    202202    {
    203203      // Checking the sum of supply values
    204204      Supply sum = 0;
    205       for (NodeIt n(graph); n != INVALID; ++n) sum += supply[n];
    206       valid_supply = sum == 0;
     205      for (NodeIt n(_graph); n != INVALID; ++n) sum += _supply[n];
     206      _valid_supply = sum == 0;
    207207    }
    208208
     
    211211    /// Simple constructor of the class (with lower bounds).
    212212    ///
    213     /// \param _graph The directed graph the algorithm runs on.
    214     /// \param _lower The lower bounds of the edges.
    215     /// \param _capacity The capacities (upper bounds) of the edges.
    216     /// \param _cost The cost (length) values of the edges.
    217     /// \param _s The source node.
    218     /// \param _t The target node.
    219     /// \param _flow_value The required amount of flow from node \c _s
    220     /// to node \c _t (i.e. the supply of \c _s and the demand of \c _t).
    221     CycleCanceling( const Graph &_graph,
    222                     const LowerMap &_lower,
    223                     const CapacityMap &_capacity,
    224                     const CostMap &_cost,
    225                     Node _s, Node _t,
    226                     Supply _flow_value ) :
    227       graph(_graph), lower(&_lower), capacity(_graph), cost(_cost),
    228       supply(_graph), flow(_graph, 0),
    229       res_graph(_graph, capacity, flow), res_cost(cost)
     213    /// \param graph The directed graph the algorithm runs on.
     214    /// \param lower The lower bounds of the edges.
     215    /// \param capacity The capacities (upper bounds) of the edges.
     216    /// \param cost The cost (length) values of the edges.
     217    /// \param s The source node.
     218    /// \param t The target node.
     219    /// \param flow_value The required amount of flow from node \c s
     220    /// to node \c t (i.e. the supply of \c s and the demand of \c t).
     221    CycleCanceling( const Graph &graph,
     222                    const LowerMap &lower,
     223                    const CapacityMap &capacity,
     224                    const CostMap &cost,
     225                    Node s, Node t,
     226                    Supply flow_value ) :
     227      _graph(graph), _lower(&lower), _capacity(graph), _cost(cost),
     228      _supply(graph), _flow(graph, 0),
     229      _res_graph(graph, _capacity, _flow), _res_cost(_cost)
    230230    {
    231231      // Removing non-zero lower bounds
    232       capacity = subMap(_capacity, _lower);
    233       for (NodeIt n(graph); n != INVALID; ++n) {
    234         Supply s = 0;
    235         if (n == _s) s =  _flow_value;
    236         if (n == _t) s = -_flow_value;
    237         for (InEdgeIt e(graph, n); e != INVALID; ++e)
    238           s += _lower[e];
    239         for (OutEdgeIt e(graph, n); e != INVALID; ++e)
    240           s -= _lower[e];
    241         supply[n] = s;
    242       }
    243       valid_supply = true;
     232      _capacity = subMap(capacity, lower);
     233      for (NodeIt n(_graph); n != INVALID; ++n) {
     234        Supply sum = 0;
     235        if (n == s) sum =  flow_value;
     236        if (n == t) sum = -flow_value;
     237        for (InEdgeIt e(_graph, n); e != INVALID; ++e)
     238          sum += lower[e];
     239        for (OutEdgeIt e(_graph, n); e != INVALID; ++e)
     240          sum -= lower[e];
     241        _supply[n] = sum;
     242      }
     243      _valid_supply = true;
    244244    }
    245245
     
    248248    /// Simple constructor of the class (without lower bounds).
    249249    ///
    250     /// \param _graph The directed graph the algorithm runs on.
    251     /// \param _capacity The capacities (upper bounds) of the edges.
    252     /// \param _cost The cost (length) values of the edges.
    253     /// \param _s The source node.
    254     /// \param _t The target node.
    255     /// \param _flow_value The required amount of flow from node \c _s
    256     /// to node \c _t (i.e. the supply of \c _s and the demand of \c _t).
    257     CycleCanceling( const Graph &_graph,
    258                     const CapacityMap &_capacity,
    259                     const CostMap &_cost,
    260                     Node _s, Node _t,
    261                     Supply _flow_value ) :
    262       graph(_graph), lower(NULL), capacity(_capacity), cost(_cost),
    263       supply(_graph, 0), flow(_graph, 0),
    264       res_graph(_graph, capacity, flow), res_cost(cost)
     250    /// \param graph The directed graph the algorithm runs on.
     251    /// \param capacity The capacities (upper bounds) of the edges.
     252    /// \param cost The cost (length) values of the edges.
     253    /// \param s The source node.
     254    /// \param t The target node.
     255    /// \param flow_value The required amount of flow from node \c s
     256    /// to node \c t (i.e. the supply of \c s and the demand of \c t).
     257    CycleCanceling( const Graph &graph,
     258                    const CapacityMap &capacity,
     259                    const CostMap &cost,
     260                    Node s, Node t,
     261                    Supply flow_value ) :
     262      _graph(graph), _lower(NULL), _capacity(capacity), _cost(cost),
     263      _supply(graph, 0), _flow(graph, 0),
     264      _res_graph(graph, _capacity, _flow), _res_cost(_cost)
    265265    {
    266       supply[_s] =  _flow_value;
    267       supply[_t] = -_flow_value;
    268       valid_supply = true;
     266      _supply[s] =  flow_value;
     267      _supply[t] = -flow_value;
     268      _valid_supply = true;
    269269    }
    270270
     
    273273    /// Runs the algorithm.
    274274    ///
     275    /// \param min_mean_cc Set this parameter to \c true to run the
     276    /// "Minimum Mean Cycle-Canceling" algorithm, which is strongly
     277    /// polynomial, but rather slower in practice.
     278    ///
    275279    /// \return \c true if a feasible flow can be found.
    276     bool run() {
    277       return init() && start();
    278     }
    279 
    280     /// \brief Returns a const reference to the flow map.
    281     ///
    282     /// Returns a const reference to the flow map.
     280    bool run(bool min_mean_cc = false) {
     281      return init() && start(min_mean_cc);
     282    }
     283
     284    /// \brief Returns a const reference to the edge map storing the
     285    /// found flow.
     286    ///
     287    /// Returns a const reference to the edge map storing the found flow.
    283288    ///
    284289    /// \pre \ref run() must be called before using this function.
    285290    const FlowMap& flowMap() const {
    286       return flow;
     291      return _flow;
    287292    }
    288293
     
    295300    Cost totalCost() const {
    296301      Cost c = 0;
    297       for (EdgeIt e(graph); e != INVALID; ++e)
    298         c += flow[e] * cost[e];
     302      for (EdgeIt e(_graph); e != INVALID; ++e)
     303        c += _flow[e] * _cost[e];
    299304      return c;
    300305    }
    301306
    302   protected:
     307  private:
    303308
    304309    /// Initializes the algorithm.
    305310    bool init() {
    306       // Checking the sum of supply values
    307       Supply sum = 0;
    308       for (NodeIt n(graph); n != INVALID; ++n) sum += supply[n];
    309       if (sum != 0) return false;
    310 
    311       // Finding a feasible flow
     311      if (!_valid_supply) return false;
     312
     313      // Finding a feasible flow using Circulation
    312314      Circulation< Graph, ConstMap<Edge, Capacity>, CapacityEdgeMap,
    313315                   SupplyMap >
    314         circulation( graph, constMap<Edge>((Capacity)0), capacity,
    315                      supply );
    316       circulation.flowMap(flow);
    317       return circulation.run();
    318     }
    319 
    320 #ifdef LIMITED_CYCLE_CANCELING
    321     /// \brief Executes a cycle-canceling algorithm using
    322     /// \ref Bellman-Ford algorithm with limited iteration count.
     316        circulation( _graph, constMap<Edge>((Capacity)0), _capacity,
     317                     _supply );
     318      return circulation.flowMap(_flow).run();
     319    }
     320
     321    bool start(bool min_mean_cc) {
     322      if (min_mean_cc)
     323        return startMinMean();
     324      else
     325        return start();
     326    }
     327
     328    /// \brief Executes the algorithm using \ref BellmanFord.
     329    ///
     330    /// Executes the algorithm using the \ref BellmanFord
     331    /// "Bellman-Ford" algorithm for negative cycle detection with
     332    /// successively larger limit for the number of iterations.
    323333    bool start() {
    324       typename BellmanFord<ResGraph, ResCostMap>::PredMap pred(res_graph);
    325       typename ResGraph::template NodeMap<int> visited(res_graph);
     334      typename BellmanFord<ResGraph, ResidualCostMap>::PredMap pred(_res_graph);
     335      typename ResGraph::template NodeMap<int> visited(_res_graph);
    326336      std::vector<ResEdge> cycle;
    327       int node_num = countNodes(graph);
    328 
    329 #ifdef _DEBUG_ITER_
    330       int cycle_num = 0;
    331 #endif
    332       int length_bound = STARTING_LIMIT;
     337      int node_num = countNodes(_graph);
     338
     339      int length_bound = BF_FIRST_LIMIT;
    333340      bool optimal = false;
    334341      while (!optimal) {
    335         BellmanFord<ResGraph, ResCostMap> bf(res_graph, res_cost);
     342        BellmanFord<ResGraph, ResidualCostMap> bf(_res_graph, _res_cost);
    336343        bf.predMap(pred);
    337344        bf.init(0);
     
    339346        bool cycle_found = false;
    340347        while (!cycle_found) {
    341 #ifdef _NO_BACK_STEP_
    342           int curr_iter_num = length_bound <= node_num ?
    343                               length_bound - iter_num : node_num - iter_num;
    344 #else
    345348          int curr_iter_num = iter_num + length_bound <= node_num ?
    346349                              length_bound : node_num - iter_num;
    347 #endif
    348350          iter_num += curr_iter_num;
    349351          int real_iter_num = curr_iter_num;
     
    359361          } else {
    360362            // Searching for node disjoint negative cycles
    361             for (ResNodeIt n(res_graph); n != INVALID; ++n)
     363            for (ResNodeIt n(_res_graph); n != INVALID; ++n)
    362364              visited[n] = 0;
    363365            int id = 0;
    364             for (ResNodeIt n(res_graph); n != INVALID; ++n) {
     366            for (ResNodeIt n(_res_graph); n != INVALID; ++n) {
    365367              if (visited[n] > 0) continue;
    366368              visited[n] = ++id;
    367369              ResNode u = pred[n] == INVALID ?
    368                           INVALID : res_graph.source(pred[n]);
     370                          INVALID : _res_graph.source(pred[n]);
    369371              while (u != INVALID && visited[u] == 0) {
    370372                visited[u] = id;
    371373                u = pred[u] == INVALID ?
    372                     INVALID : res_graph.source(pred[u]);
     374                    INVALID : _res_graph.source(pred[u]);
    373375              }
    374376              if (u != INVALID && visited[u] == id) {
     
    378380                ResEdge e = pred[u];
    379381                cycle.push_back(e);
    380                 Capacity d = res_graph.rescap(e);
    381                 while (res_graph.source(e) != u) {
    382                   cycle.push_back(e = pred[res_graph.source(e)]);
    383                   if (res_graph.rescap(e) < d)
    384                     d = res_graph.rescap(e);
     382                Capacity d = _res_graph.rescap(e);
     383                while (_res_graph.source(e) != u) {
     384                  cycle.push_back(e = pred[_res_graph.source(e)]);
     385                  if (_res_graph.rescap(e) < d)
     386                    d = _res_graph.rescap(e);
    385387                }
    386 #ifdef _DEBUG_ITER_
    387                 ++cycle_num;
    388 #endif
     388
    389389                // Augmenting along the cycle
    390                 for (int i = 0; i < cycle.size(); ++i)
    391                   res_graph.augment(cycle[i], d);
    392 #ifdef _ONLY_ONE_CYCLE_
    393                 break;
    394 #endif
     390                for (int i = 0; i < int(cycle.size()); ++i)
     391                  _res_graph.augment(cycle[i], d);
    395392              }
    396393            }
     
    398395
    399396          if (!cycle_found)
    400             length_bound = length_bound * ALPHA_MUL / ALPHA_DIV;
     397            length_bound = int(length_bound * BF_ALPHA);
    401398        }
    402399      }
    403400
    404 #ifdef _DEBUG_ITER_
    405       std::cout << "Limited cycle-canceling algorithm finished. "
    406                 << "Found " << cycle_num << " negative cycles."
    407                 << std::endl;
    408 #endif
    409 
    410401      // Handling non-zero lower bounds
    411       if (lower) {
    412         for (EdgeIt e(graph); e != INVALID; ++e)
    413           flow[e] += (*lower)[e];
     402      if (_lower) {
     403        for (EdgeIt e(_graph); e != INVALID; ++e)
     404          _flow[e] += (*_lower)[e];
    414405      }
    415406      return true;
    416407    }
    417 #endif
    418 
    419 #ifdef MIN_MEAN_CYCLE_CANCELING
    420     /// \brief Executes the minimum mean cycle-canceling algorithm
    421     /// using \ref MinMeanCycle.
    422     bool start() {
     408
     409    /// \brief Executes the algorithm using \ref MinMeanCycle.
     410    ///
     411    /// Executes the algorithm using \ref MinMeanCycle for negative
     412    /// cycle detection.
     413    bool startMinMean() {
    423414      typedef Path<ResGraph> ResPath;
    424       MinMeanCycle<ResGraph, ResCostMap> mmc(res_graph, res_cost);
     415      MinMeanCycle<ResGraph, ResidualCostMap> mmc(_res_graph, _res_cost);
    425416      ResPath cycle;
    426417
    427 #ifdef _DEBUG_ITER_
    428       int cycle_num = 0;
    429 #endif
    430418      mmc.cyclePath(cycle).init();
    431419      if (mmc.findMinMean()) {
    432420        while (mmc.cycleLength() < 0) {
    433 #ifdef _DEBUG_ITER_
    434           ++cycle_num;
    435 #endif
    436421          // Finding the cycle
    437422          mmc.findCycle();
     
    441426          Capacity delta = 0;
    442427          for (typename ResPath::EdgeIt e(cycle); e != INVALID; ++e) {
    443             if (delta == 0 || res_graph.rescap(e) < delta)
    444               delta = res_graph.rescap(e);
     428            if (delta == 0 || _res_graph.rescap(e) < delta)
     429              delta = _res_graph.rescap(e);
    445430          }
    446431
    447432          // Augmenting along the cycle
    448433          for (typename ResPath::EdgeIt e(cycle); e != INVALID; ++e)
    449             res_graph.augment(e, delta);
     434            _res_graph.augment(e, delta);
    450435
    451436          // Finding the minimum cycle mean for the modified residual
     
    456441      }
    457442
    458 #ifdef _DEBUG_ITER_
    459       std::cout << "Minimum mean cycle-canceling algorithm finished. "
    460                 << "Found " << cycle_num << " negative cycles."
    461                 << std::endl;
    462 #endif
    463 
    464443      // Handling non-zero lower bounds
    465       if (lower) {
    466         for (EdgeIt e(graph); e != INVALID; ++e)
    467           flow[e] += (*lower)[e];
     444      if (_lower) {
     445        for (EdgeIt e(_graph); e != INVALID; ++e)
     446          _flow[e] += (*_lower)[e];
    468447      }
    469448      return true;
    470449    }
    471 #endif
    472450
    473451  }; //class CycleCanceling
Note: See TracChangeset for help on using the changeset viewer.