1.1 --- a/lemon/cycle_canceling.h Sun Jan 13 10:26:55 2008 +0000
1.2 +++ b/lemon/cycle_canceling.h Sun Jan 13 10:32:14 2008 +0000
1.3 @@ -34,24 +34,17 @@
1.4
1.5 #ifdef LIMITED_CYCLE_CANCELING
1.6 #include <lemon/bellman_ford.h>
1.7 - /// \brief The maximum number of iterations for the first execution
1.8 - /// of the \ref lemon::BellmanFord "Bellman-Ford" algorithm.
1.9 - /// It should be at least 2.
1.10 - #define STARTING_LIMIT 2
1.11 - /// \brief The iteration limit for the
1.12 - /// \ref lemon::BellmanFord "Bellman-Ford" algorithm is multiplied by
1.13 - /// <tt>ALPHA_MUL / ALPHA_DIV</tt> in every round.
1.14 - /// <tt>ALPHA_MUL / ALPHA_DIV</tt> must be greater than 1.
1.15 - #define ALPHA_MUL 3
1.16 - /// \brief The iteration limit for the
1.17 - /// \ref lemon::BellmanFord "Bellman-Ford" algorithm is multiplied by
1.18 - /// <tt>ALPHA_MUL / ALPHA_DIV</tt> in every round.
1.19 - /// <tt>ALPHA_MUL / ALPHA_DIV</tt> must be greater than 1.
1.20 - #define ALPHA_DIV 2
1.21 + // The maximum number of iterations for the first execution of the
1.22 + // Bellman-Ford algorithm. It should be at least 2.
1.23 + #define STARTING_LIMIT 2
1.24 + // The iteration limit for the Bellman-Ford algorithm is multiplied by
1.25 + // <tt>ALPHA_MUL / ALPHA_DIV</tt> in every round.
1.26 + // <tt>ALPHA_MUL / ALPHA_DIV</tt> must be greater than 1.
1.27 + #define ALPHA_MUL 3
1.28 + #define ALPHA_DIV 2
1.29
1.30 //#define _ONLY_ONE_CYCLE_
1.31 //#define _NO_BACK_STEP_
1.32 -//#define _DEBUG_ITER_
1.33 #endif
1.34
1.35 #ifdef MIN_MEAN_CYCLE_CANCELING
1.36 @@ -59,16 +52,18 @@
1.37 #include <lemon/path.h>
1.38 #endif
1.39
1.40 +//#define _DEBUG_ITER_
1.41 +
1.42 namespace lemon {
1.43
1.44 /// \addtogroup min_cost_flow
1.45 /// @{
1.46
1.47 - /// \brief Implementation of a cycle-canceling algorithm for finding
1.48 - /// a minimum cost flow.
1.49 + /// \brief Implementation of a cycle-canceling algorithm for
1.50 + /// finding a minimum cost flow.
1.51 ///
1.52 - /// \ref lemon::CycleCanceling "CycleCanceling" implements a
1.53 - /// cycle-canceling algorithm for finding a minimum cost flow.
1.54 + /// \ref CycleCanceling implements a cycle-canceling algorithm for
1.55 + /// finding a minimum cost flow.
1.56 ///
1.57 /// \param Graph The directed graph type the algorithm runs on.
1.58 /// \param LowerMap The type of the lower bound map.
1.59 @@ -77,12 +72,12 @@
1.60 /// \param SupplyMap The type of the supply map.
1.61 ///
1.62 /// \warning
1.63 - /// - Edge capacities and costs should be nonnegative integers.
1.64 - /// However \c CostMap::Value should be signed type.
1.65 + /// - Edge capacities and costs should be non-negative integers.
1.66 + /// However \c CostMap::Value should be signed type.
1.67 /// - Supply values should be signed integers.
1.68 /// - \c LowerMap::Value must be convertible to
1.69 - /// \c CapacityMap::Value and \c CapacityMap::Value must be
1.70 - /// convertible to \c SupplyMap::Value.
1.71 + /// \c CapacityMap::Value and \c CapacityMap::Value must be
1.72 + /// convertible to \c SupplyMap::Value.
1.73 ///
1.74 /// \author Peter Kovacs
1.75
1.76 @@ -94,22 +89,17 @@
1.77 <typename CapacityMap::Value> >
1.78 class CycleCanceling
1.79 {
1.80 - typedef typename Graph::Node Node;
1.81 - typedef typename Graph::NodeIt NodeIt;
1.82 - typedef typename Graph::Edge Edge;
1.83 - typedef typename Graph::EdgeIt EdgeIt;
1.84 - typedef typename Graph::InEdgeIt InEdgeIt;
1.85 - typedef typename Graph::OutEdgeIt OutEdgeIt;
1.86 + GRAPH_TYPEDEFS(typename Graph);
1.87
1.88 typedef typename LowerMap::Value Lower;
1.89 typedef typename CapacityMap::Value Capacity;
1.90 typedef typename CostMap::Value Cost;
1.91 typedef typename SupplyMap::Value Supply;
1.92 - typedef typename Graph::template EdgeMap<Capacity> CapacityRefMap;
1.93 - typedef typename Graph::template NodeMap<Supply> SupplyRefMap;
1.94 + typedef typename Graph::template EdgeMap<Capacity> CapacityEdgeMap;
1.95 + typedef typename Graph::template NodeMap<Supply> SupplyNodeMap;
1.96
1.97 typedef ResGraphAdaptor< const Graph, Capacity,
1.98 - CapacityRefMap, CapacityRefMap > ResGraph;
1.99 + CapacityEdgeMap, CapacityEdgeMap > ResGraph;
1.100 typedef typename ResGraph::Node ResNode;
1.101 typedef typename ResGraph::NodeIt ResNodeIt;
1.102 typedef typename ResGraph::Edge ResEdge;
1.103 @@ -117,12 +107,12 @@
1.104
1.105 public:
1.106
1.107 - /// \brief The type of the flow map.
1.108 - typedef CapacityRefMap FlowMap;
1.109 + /// The type of the flow map.
1.110 + typedef typename Graph::template EdgeMap<Capacity> FlowMap;
1.111
1.112 protected:
1.113
1.114 - /// \brief Map adaptor class for handling residual edge costs.
1.115 + /// Map adaptor class for handling residual edge costs.
1.116 class ResCostMap : public MapBase<ResEdge, Cost>
1.117 {
1.118 private:
1.119 @@ -134,31 +124,30 @@
1.120 ResCostMap(const CostMap &_cost) : cost_map(_cost) {}
1.121
1.122 Cost operator[](const ResEdge &e) const {
1.123 - return ResGraph::forward(e) ? cost_map[e] : -cost_map[e];
1.124 + return ResGraph::forward(e) ? cost_map[e] : -cost_map[e];
1.125 }
1.126
1.127 }; //class ResCostMap
1.128
1.129 protected:
1.130
1.131 - /// \brief The directed graph the algorithm runs on.
1.132 + /// The directed graph the algorithm runs on.
1.133 const Graph &graph;
1.134 - /// \brief The original lower bound map.
1.135 + /// The original lower bound map.
1.136 const LowerMap *lower;
1.137 - /// \brief The modified capacity map.
1.138 - CapacityRefMap capacity;
1.139 - /// \brief The cost map.
1.140 + /// The modified capacity map.
1.141 + CapacityEdgeMap capacity;
1.142 + /// The cost map.
1.143 const CostMap &cost;
1.144 - /// \brief The modified supply map.
1.145 - SupplyRefMap supply;
1.146 - /// \brief The sum of supply values equals zero.
1.147 + /// The modified supply map.
1.148 + SupplyNodeMap supply;
1.149 bool valid_supply;
1.150
1.151 - /// \brief The current flow.
1.152 + /// The current flow.
1.153 FlowMap flow;
1.154 - /// \brief The residual graph.
1.155 + /// The residual graph.
1.156 ResGraph res_graph;
1.157 - /// \brief The residual cost map.
1.158 + /// The residual cost map.
1.159 ResCostMap res_cost;
1.160
1.161 public :
1.162 @@ -173,24 +162,24 @@
1.163 /// \param _cost The cost (length) values of the edges.
1.164 /// \param _supply The supply values of the nodes (signed).
1.165 CycleCanceling( const Graph &_graph,
1.166 - const LowerMap &_lower,
1.167 - const CapacityMap &_capacity,
1.168 - const CostMap &_cost,
1.169 - const SupplyMap &_supply ) :
1.170 + const LowerMap &_lower,
1.171 + const CapacityMap &_capacity,
1.172 + const CostMap &_cost,
1.173 + const SupplyMap &_supply ) :
1.174 graph(_graph), lower(&_lower), capacity(_graph), cost(_cost),
1.175 supply(_graph), flow(_graph, 0),
1.176 res_graph(_graph, capacity, flow), res_cost(cost)
1.177 {
1.178 - // Removing nonzero lower bounds
1.179 + // Removing non-zero lower bounds
1.180 capacity = subMap(_capacity, _lower);
1.181 Supply sum = 0;
1.182 for (NodeIt n(graph); n != INVALID; ++n) {
1.183 - Supply s = _supply[n];
1.184 - for (InEdgeIt e(graph, n); e != INVALID; ++e)
1.185 - s += _lower[e];
1.186 - for (OutEdgeIt e(graph, n); e != INVALID; ++e)
1.187 - s -= _lower[e];
1.188 - sum += (supply[n] = s);
1.189 + Supply s = _supply[n];
1.190 + for (InEdgeIt e(graph, n); e != INVALID; ++e)
1.191 + s += _lower[e];
1.192 + for (OutEdgeIt e(graph, n); e != INVALID; ++e)
1.193 + s -= _lower[e];
1.194 + sum += (supply[n] = s);
1.195 }
1.196 valid_supply = sum == 0;
1.197 }
1.198 @@ -204,9 +193,9 @@
1.199 /// \param _cost The cost (length) values of the edges.
1.200 /// \param _supply The supply values of the nodes (signed).
1.201 CycleCanceling( const Graph &_graph,
1.202 - const CapacityMap &_capacity,
1.203 - const CostMap &_cost,
1.204 - const SupplyMap &_supply ) :
1.205 + const CapacityMap &_capacity,
1.206 + const CostMap &_cost,
1.207 + const SupplyMap &_supply ) :
1.208 graph(_graph), lower(NULL), capacity(_capacity), cost(_cost),
1.209 supply(_supply), flow(_graph, 0),
1.210 res_graph(_graph, capacity, flow), res_cost(cost)
1.211 @@ -217,7 +206,6 @@
1.212 valid_supply = sum == 0;
1.213 }
1.214
1.215 -
1.216 /// \brief Simple constructor of the class (with lower bounds).
1.217 ///
1.218 /// Simple constructor of the class (with lower bounds).
1.219 @@ -229,29 +217,28 @@
1.220 /// \param _s The source node.
1.221 /// \param _t The target node.
1.222 /// \param _flow_value The required amount of flow from node \c _s
1.223 - /// to node \c _t (i.e. the supply of \c _s and the demand of
1.224 - /// \c _t).
1.225 + /// to node \c _t (i.e. the supply of \c _s and the demand of \c _t).
1.226 CycleCanceling( const Graph &_graph,
1.227 - const LowerMap &_lower,
1.228 - const CapacityMap &_capacity,
1.229 - const CostMap &_cost,
1.230 - Node _s, Node _t,
1.231 - Supply _flow_value ) :
1.232 + const LowerMap &_lower,
1.233 + const CapacityMap &_capacity,
1.234 + const CostMap &_cost,
1.235 + Node _s, Node _t,
1.236 + Supply _flow_value ) :
1.237 graph(_graph), lower(&_lower), capacity(_graph), cost(_cost),
1.238 supply(_graph), flow(_graph, 0),
1.239 res_graph(_graph, capacity, flow), res_cost(cost)
1.240 {
1.241 - // Removing nonzero lower bounds
1.242 + // Removing non-zero lower bounds
1.243 capacity = subMap(_capacity, _lower);
1.244 for (NodeIt n(graph); n != INVALID; ++n) {
1.245 - Supply s = 0;
1.246 - if (n == _s) s = _flow_value;
1.247 - if (n == _t) s = -_flow_value;
1.248 - for (InEdgeIt e(graph, n); e != INVALID; ++e)
1.249 - s += _lower[e];
1.250 - for (OutEdgeIt e(graph, n); e != INVALID; ++e)
1.251 - s -= _lower[e];
1.252 - supply[n] = s;
1.253 + Supply s = 0;
1.254 + if (n == _s) s = _flow_value;
1.255 + if (n == _t) s = -_flow_value;
1.256 + for (InEdgeIt e(graph, n); e != INVALID; ++e)
1.257 + s += _lower[e];
1.258 + for (OutEdgeIt e(graph, n); e != INVALID; ++e)
1.259 + s -= _lower[e];
1.260 + supply[n] = s;
1.261 }
1.262 valid_supply = true;
1.263 }
1.264 @@ -266,13 +253,12 @@
1.265 /// \param _s The source node.
1.266 /// \param _t The target node.
1.267 /// \param _flow_value The required amount of flow from node \c _s
1.268 - /// to node \c _t (i.e. the supply of \c _s and the demand of
1.269 - /// \c _t).
1.270 + /// to node \c _t (i.e. the supply of \c _s and the demand of \c _t).
1.271 CycleCanceling( const Graph &_graph,
1.272 - const CapacityMap &_capacity,
1.273 - const CostMap &_cost,
1.274 - Node _s, Node _t,
1.275 - Supply _flow_value ) :
1.276 + const CapacityMap &_capacity,
1.277 + const CostMap &_cost,
1.278 + Node _s, Node _t,
1.279 + Supply _flow_value ) :
1.280 graph(_graph), lower(NULL), capacity(_capacity), cost(_cost),
1.281 supply(_graph, 0), flow(_graph, 0),
1.282 res_graph(_graph, capacity, flow), res_cost(cost)
1.283 @@ -282,6 +268,15 @@
1.284 valid_supply = true;
1.285 }
1.286
1.287 + /// \brief Runs the algorithm.
1.288 + ///
1.289 + /// Runs the algorithm.
1.290 + ///
1.291 + /// \return \c true if a feasible flow can be found.
1.292 + bool run() {
1.293 + return init() && start();
1.294 + }
1.295 +
1.296 /// \brief Returns a const reference to the flow map.
1.297 ///
1.298 /// Returns a const reference to the flow map.
1.299 @@ -300,22 +295,13 @@
1.300 Cost totalCost() const {
1.301 Cost c = 0;
1.302 for (EdgeIt e(graph); e != INVALID; ++e)
1.303 - c += flow[e] * cost[e];
1.304 + c += flow[e] * cost[e];
1.305 return c;
1.306 }
1.307
1.308 - /// \brief Runs the algorithm.
1.309 - ///
1.310 - /// Runs the algorithm.
1.311 - ///
1.312 - /// \return \c true if a feasible flow can be found.
1.313 - bool run() {
1.314 - return init() && start();
1.315 - }
1.316 -
1.317 protected:
1.318
1.319 - /// \brief Initializes the algorithm.
1.320 + /// Initializes the algorithm.
1.321 bool init() {
1.322 // Checking the sum of supply values
1.323 Supply sum = 0;
1.324 @@ -323,18 +309,17 @@
1.325 if (sum != 0) return false;
1.326
1.327 // Finding a feasible flow
1.328 - Circulation< Graph, ConstMap<Edge, Capacity>, CapacityRefMap,
1.329 - SupplyMap >
1.330 - circulation( graph, constMap<Edge>((Capacity)0), capacity,
1.331 - supply );
1.332 + Circulation< Graph, ConstMap<Edge, Capacity>, CapacityEdgeMap,
1.333 + SupplyMap >
1.334 + circulation( graph, constMap<Edge>((Capacity)0), capacity,
1.335 + supply );
1.336 circulation.flowMap(flow);
1.337 return circulation.run();
1.338 }
1.339
1.340 #ifdef LIMITED_CYCLE_CANCELING
1.341 /// \brief Executes a cycle-canceling algorithm using
1.342 - /// \ref lemon::BellmanFord "Bellman-Ford" algorithm with limited
1.343 - /// iteration count.
1.344 + /// \ref Bellman-Ford algorithm with limited iteration count.
1.345 bool start() {
1.346 typename BellmanFord<ResGraph, ResCostMap>::PredMap pred(res_graph);
1.347 typename ResGraph::template NodeMap<int> visited(res_graph);
1.348 @@ -347,85 +332,85 @@
1.349 int length_bound = STARTING_LIMIT;
1.350 bool optimal = false;
1.351 while (!optimal) {
1.352 - BellmanFord<ResGraph, ResCostMap> bf(res_graph, res_cost);
1.353 - bf.predMap(pred);
1.354 - bf.init(0);
1.355 - int iter_num = 0;
1.356 - bool cycle_found = false;
1.357 - while (!cycle_found) {
1.358 + BellmanFord<ResGraph, ResCostMap> bf(res_graph, res_cost);
1.359 + bf.predMap(pred);
1.360 + bf.init(0);
1.361 + int iter_num = 0;
1.362 + bool cycle_found = false;
1.363 + while (!cycle_found) {
1.364 #ifdef _NO_BACK_STEP_
1.365 - int curr_iter_num = length_bound <= node_num ?
1.366 - length_bound - iter_num : node_num - iter_num;
1.367 + int curr_iter_num = length_bound <= node_num ?
1.368 + length_bound - iter_num : node_num - iter_num;
1.369 #else
1.370 - int curr_iter_num = iter_num + length_bound <= node_num ?
1.371 - length_bound : node_num - iter_num;
1.372 + int curr_iter_num = iter_num + length_bound <= node_num ?
1.373 + length_bound : node_num - iter_num;
1.374 #endif
1.375 - iter_num += curr_iter_num;
1.376 - int real_iter_num = curr_iter_num;
1.377 - for (int i = 0; i < curr_iter_num; ++i) {
1.378 - if (bf.processNextWeakRound()) {
1.379 - real_iter_num = i;
1.380 - break;
1.381 - }
1.382 - }
1.383 - if (real_iter_num < curr_iter_num) {
1.384 - optimal = true;
1.385 - break;
1.386 - } else {
1.387 - // Searching for node disjoint negative cycles
1.388 - for (ResNodeIt n(res_graph); n != INVALID; ++n)
1.389 - visited[n] = 0;
1.390 - int id = 0;
1.391 - for (ResNodeIt n(res_graph); n != INVALID; ++n) {
1.392 - if (visited[n] > 0) continue;
1.393 - visited[n] = ++id;
1.394 - ResNode u = pred[n] == INVALID ?
1.395 - INVALID : res_graph.source(pred[n]);
1.396 - while (u != INVALID && visited[u] == 0) {
1.397 - visited[u] = id;
1.398 - u = pred[u] == INVALID ?
1.399 - INVALID : res_graph.source(pred[u]);
1.400 - }
1.401 - if (u != INVALID && visited[u] == id) {
1.402 - // Finding the negative cycle
1.403 - cycle_found = true;
1.404 - cycle.clear();
1.405 - ResEdge e = pred[u];
1.406 - cycle.push_back(e);
1.407 - Capacity d = res_graph.rescap(e);
1.408 - while (res_graph.source(e) != u) {
1.409 - cycle.push_back(e = pred[res_graph.source(e)]);
1.410 - if (res_graph.rescap(e) < d)
1.411 - d = res_graph.rescap(e);
1.412 - }
1.413 + iter_num += curr_iter_num;
1.414 + int real_iter_num = curr_iter_num;
1.415 + for (int i = 0; i < curr_iter_num; ++i) {
1.416 + if (bf.processNextWeakRound()) {
1.417 + real_iter_num = i;
1.418 + break;
1.419 + }
1.420 + }
1.421 + if (real_iter_num < curr_iter_num) {
1.422 + optimal = true;
1.423 + break;
1.424 + } else {
1.425 + // Searching for node disjoint negative cycles
1.426 + for (ResNodeIt n(res_graph); n != INVALID; ++n)
1.427 + visited[n] = 0;
1.428 + int id = 0;
1.429 + for (ResNodeIt n(res_graph); n != INVALID; ++n) {
1.430 + if (visited[n] > 0) continue;
1.431 + visited[n] = ++id;
1.432 + ResNode u = pred[n] == INVALID ?
1.433 + INVALID : res_graph.source(pred[n]);
1.434 + while (u != INVALID && visited[u] == 0) {
1.435 + visited[u] = id;
1.436 + u = pred[u] == INVALID ?
1.437 + INVALID : res_graph.source(pred[u]);
1.438 + }
1.439 + if (u != INVALID && visited[u] == id) {
1.440 + // Finding the negative cycle
1.441 + cycle_found = true;
1.442 + cycle.clear();
1.443 + ResEdge e = pred[u];
1.444 + cycle.push_back(e);
1.445 + Capacity d = res_graph.rescap(e);
1.446 + while (res_graph.source(e) != u) {
1.447 + cycle.push_back(e = pred[res_graph.source(e)]);
1.448 + if (res_graph.rescap(e) < d)
1.449 + d = res_graph.rescap(e);
1.450 + }
1.451 #ifdef _DEBUG_ITER_
1.452 - ++cycle_num;
1.453 + ++cycle_num;
1.454 #endif
1.455 - // Augmenting along the cycle
1.456 - for (int i = 0; i < cycle.size(); ++i)
1.457 - res_graph.augment(cycle[i], d);
1.458 + // Augmenting along the cycle
1.459 + for (int i = 0; i < cycle.size(); ++i)
1.460 + res_graph.augment(cycle[i], d);
1.461 #ifdef _ONLY_ONE_CYCLE_
1.462 - break;
1.463 + break;
1.464 #endif
1.465 - }
1.466 - }
1.467 - }
1.468 + }
1.469 + }
1.470 + }
1.471
1.472 - if (!cycle_found)
1.473 - length_bound = length_bound * ALPHA_MUL / ALPHA_DIV;
1.474 - }
1.475 + if (!cycle_found)
1.476 + length_bound = length_bound * ALPHA_MUL / ALPHA_DIV;
1.477 + }
1.478 }
1.479
1.480 #ifdef _DEBUG_ITER_
1.481 std::cout << "Limited cycle-canceling algorithm finished. "
1.482 - << "Found " << cycle_num << " negative cycles."
1.483 - << std::endl;
1.484 + << "Found " << cycle_num << " negative cycles."
1.485 + << std::endl;
1.486 #endif
1.487
1.488 - // Handling nonzero lower bounds
1.489 + // Handling non-zero lower bounds
1.490 if (lower) {
1.491 - for (EdgeIt e(graph); e != INVALID; ++e)
1.492 - flow[e] += (*lower)[e];
1.493 + for (EdgeIt e(graph); e != INVALID; ++e)
1.494 + flow[e] += (*lower)[e];
1.495 }
1.496 return true;
1.497 }
1.498 @@ -433,7 +418,7 @@
1.499
1.500 #ifdef MIN_MEAN_CYCLE_CANCELING
1.501 /// \brief Executes the minimum mean cycle-canceling algorithm
1.502 - /// using \ref lemon::MinMeanCycle "MinMeanCycle" class.
1.503 + /// using \ref MinMeanCycle.
1.504 bool start() {
1.505 typedef Path<ResGraph> ResPath;
1.506 MinMeanCycle<ResGraph, ResCostMap> mmc(res_graph, res_cost);
1.507 @@ -444,42 +429,42 @@
1.508 #endif
1.509 mmc.cyclePath(cycle).init();
1.510 if (mmc.findMinMean()) {
1.511 - while (mmc.cycleLength() < 0) {
1.512 + while (mmc.cycleLength() < 0) {
1.513 #ifdef _DEBUG_ITER_
1.514 - ++iter;
1.515 + ++cycle_num;
1.516 #endif
1.517 - // Finding the cycle
1.518 - mmc.findCycle();
1.519 + // Finding the cycle
1.520 + mmc.findCycle();
1.521
1.522 - // Finding the largest flow amount that can be augmented
1.523 - // along the cycle
1.524 - Capacity delta = 0;
1.525 - for (typename ResPath::EdgeIt e(cycle); e != INVALID; ++e) {
1.526 - if (delta == 0 || res_graph.rescap(e) < delta)
1.527 - delta = res_graph.rescap(e);
1.528 - }
1.529 + // Finding the largest flow amount that can be augmented
1.530 + // along the cycle
1.531 + Capacity delta = 0;
1.532 + for (typename ResPath::EdgeIt e(cycle); e != INVALID; ++e) {
1.533 + if (delta == 0 || res_graph.rescap(e) < delta)
1.534 + delta = res_graph.rescap(e);
1.535 + }
1.536
1.537 - // Augmenting along the cycle
1.538 - for (typename ResPath::EdgeIt e(cycle); e != INVALID; ++e)
1.539 - res_graph.augment(e, delta);
1.540 + // Augmenting along the cycle
1.541 + for (typename ResPath::EdgeIt e(cycle); e != INVALID; ++e)
1.542 + res_graph.augment(e, delta);
1.543
1.544 - // Finding the minimum cycle mean for the modified residual
1.545 - // graph
1.546 - mmc.reset();
1.547 - if (!mmc.findMinMean()) break;
1.548 - }
1.549 + // Finding the minimum cycle mean for the modified residual
1.550 + // graph
1.551 + mmc.reset();
1.552 + if (!mmc.findMinMean()) break;
1.553 + }
1.554 }
1.555
1.556 #ifdef _DEBUG_ITER_
1.557 std::cout << "Minimum mean cycle-canceling algorithm finished. "
1.558 - << "Found " << cycle_num << " negative cycles."
1.559 - << std::endl;
1.560 + << "Found " << cycle_num << " negative cycles."
1.561 + << std::endl;
1.562 #endif
1.563
1.564 - // Handling nonzero lower bounds
1.565 + // Handling non-zero lower bounds
1.566 if (lower) {
1.567 - for (EdgeIt e(graph); e != INVALID; ++e)
1.568 - flow[e] += (*lower)[e];
1.569 + for (EdgeIt e(graph); e != INVALID; ++e)
1.570 + flow[e] += (*lower)[e];
1.571 }
1.572 return true;
1.573 }