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.
1.1 --- a/lemon/cycle_canceling.h Fri Feb 08 11:58:32 2008 +0000
1.2 +++ b/lemon/cycle_canceling.h Mon Feb 18 03:30:12 2008 +0000
1.3 @@ -22,37 +22,15 @@
1.4 /// \ingroup min_cost_flow
1.5 ///
1.6 /// \file
1.7 -/// \brief A cycle-canceling algorithm for finding a minimum cost flow.
1.8 +/// \brief Cycle-canceling algorithm for finding a minimum cost flow.
1.9
1.10 #include <vector>
1.11 #include <lemon/graph_adaptor.h>
1.12 +#include <lemon/path.h>
1.13 +
1.14 #include <lemon/circulation.h>
1.15 -
1.16 -/// \brief The used cycle-canceling method.
1.17 -#define LIMITED_CYCLE_CANCELING
1.18 -//#define MIN_MEAN_CYCLE_CANCELING
1.19 -
1.20 -#ifdef LIMITED_CYCLE_CANCELING
1.21 - #include <lemon/bellman_ford.h>
1.22 - // The maximum number of iterations for the first execution of the
1.23 - // Bellman-Ford algorithm. It should be at least 2.
1.24 - #define STARTING_LIMIT 2
1.25 - // The iteration limit for the Bellman-Ford algorithm is multiplied by
1.26 - // <tt>ALPHA_MUL / ALPHA_DIV</tt> in every round.
1.27 - // <tt>ALPHA_MUL / ALPHA_DIV</tt> must be greater than 1.
1.28 - #define ALPHA_MUL 3
1.29 - #define ALPHA_DIV 2
1.30 -
1.31 -//#define _ONLY_ONE_CYCLE_
1.32 -//#define _NO_BACK_STEP_
1.33 -#endif
1.34 -
1.35 -#ifdef MIN_MEAN_CYCLE_CANCELING
1.36 - #include <lemon/min_mean_cycle.h>
1.37 - #include <lemon/path.h>
1.38 -#endif
1.39 -
1.40 -//#define _DEBUG_ITER_
1.41 +#include <lemon/bellman_ford.h>
1.42 +#include <lemon/min_mean_cycle.h>
1.43
1.44 namespace lemon {
1.45
1.46 @@ -65,33 +43,40 @@
1.47 /// \ref CycleCanceling implements a cycle-canceling algorithm for
1.48 /// finding a minimum cost flow.
1.49 ///
1.50 - /// \param Graph The directed graph type the algorithm runs on.
1.51 - /// \param LowerMap The type of the lower bound map.
1.52 - /// \param CapacityMap The type of the capacity (upper bound) map.
1.53 - /// \param CostMap The type of the cost (length) map.
1.54 - /// \param SupplyMap The type of the supply map.
1.55 + /// \tparam Graph The directed graph type the algorithm runs on.
1.56 + /// \tparam LowerMap The type of the lower bound map.
1.57 + /// \tparam CapacityMap The type of the capacity (upper bound) map.
1.58 + /// \tparam CostMap The type of the cost (length) map.
1.59 + /// \tparam SupplyMap The type of the supply map.
1.60 ///
1.61 /// \warning
1.62 - /// - Edge capacities and costs should be non-negative integers.
1.63 - /// However \c CostMap::Value should be signed type.
1.64 - /// - Supply values should be signed integers.
1.65 - /// - \c LowerMap::Value must be convertible to
1.66 - /// \c CapacityMap::Value and \c CapacityMap::Value must be
1.67 - /// convertible to \c SupplyMap::Value.
1.68 + /// - Edge capacities and costs should be \e non-negative \e integers.
1.69 + /// - Supply values should be \e signed \e integers.
1.70 + /// - \c LowerMap::Value must be convertible to \c CapacityMap::Value.
1.71 + /// - \c CapacityMap::Value and \c SupplyMap::Value must be
1.72 + /// convertible to each other.
1.73 + /// - All value types must be convertible to \c CostMap::Value, which
1.74 + /// must be signed type.
1.75 + ///
1.76 + /// \note By default the \ref BellmanFord "Bellman-Ford" algorithm is
1.77 + /// used for negative cycle detection with limited iteration number.
1.78 + /// However \ref CycleCanceling also provides the "Minimum Mean
1.79 + /// Cycle-Canceling" algorithm, which is \e strongly \e polynomial,
1.80 + /// but rather slower in practice.
1.81 + /// To use this version of the algorithm, call \ref run() with \c true
1.82 + /// parameter.
1.83 ///
1.84 /// \author Peter Kovacs
1.85
1.86 template < typename Graph,
1.87 typename LowerMap = typename Graph::template EdgeMap<int>,
1.88 - typename CapacityMap = LowerMap,
1.89 + typename CapacityMap = typename Graph::template EdgeMap<int>,
1.90 typename CostMap = typename Graph::template EdgeMap<int>,
1.91 - typename SupplyMap = typename Graph::template NodeMap
1.92 - <typename CapacityMap::Value> >
1.93 + typename SupplyMap = typename Graph::template NodeMap<int> >
1.94 class CycleCanceling
1.95 {
1.96 GRAPH_TYPEDEFS(typename Graph);
1.97
1.98 - typedef typename LowerMap::Value Lower;
1.99 typedef typename CapacityMap::Value Capacity;
1.100 typedef typename CostMap::Value Cost;
1.101 typedef typename SupplyMap::Value Supply;
1.102 @@ -110,180 +95,200 @@
1.103 /// The type of the flow map.
1.104 typedef typename Graph::template EdgeMap<Capacity> FlowMap;
1.105
1.106 - protected:
1.107 + private:
1.108
1.109 - /// Map adaptor class for handling residual edge costs.
1.110 - class ResCostMap : public MapBase<ResEdge, Cost>
1.111 + /// \brief Map adaptor class for handling residual edge costs.
1.112 + ///
1.113 + /// \ref ResidualCostMap is a map adaptor class for handling
1.114 + /// residual edge costs.
1.115 + class ResidualCostMap : public MapBase<ResEdge, Cost>
1.116 {
1.117 private:
1.118
1.119 - const CostMap &cost_map;
1.120 + const CostMap &_cost_map;
1.121
1.122 public:
1.123
1.124 - ResCostMap(const CostMap &_cost) : cost_map(_cost) {}
1.125 + ///\e
1.126 + ResidualCostMap(const CostMap &cost_map) : _cost_map(cost_map) {}
1.127
1.128 + ///\e
1.129 Cost operator[](const ResEdge &e) const {
1.130 - return ResGraph::forward(e) ? cost_map[e] : -cost_map[e];
1.131 + return ResGraph::forward(e) ? _cost_map[e] : -_cost_map[e];
1.132 }
1.133
1.134 - }; //class ResCostMap
1.135 + }; //class ResidualCostMap
1.136
1.137 - protected:
1.138 + private:
1.139
1.140 - /// The directed graph the algorithm runs on.
1.141 - const Graph &graph;
1.142 - /// The original lower bound map.
1.143 - const LowerMap *lower;
1.144 - /// The modified capacity map.
1.145 - CapacityEdgeMap capacity;
1.146 - /// The cost map.
1.147 - const CostMap &cost;
1.148 - /// The modified supply map.
1.149 - SupplyNodeMap supply;
1.150 - bool valid_supply;
1.151 + // The maximum number of iterations for the first execution of the
1.152 + // Bellman-Ford algorithm. It should be at least 2.
1.153 + static const int BF_FIRST_LIMIT = 2;
1.154 + // The iteration limit for the Bellman-Ford algorithm is multiplied
1.155 + // by BF_ALPHA in every round.
1.156 + static const double BF_ALPHA = 1.5;
1.157
1.158 - /// The current flow.
1.159 - FlowMap flow;
1.160 - /// The residual graph.
1.161 - ResGraph res_graph;
1.162 - /// The residual cost map.
1.163 - ResCostMap res_cost;
1.164 + private:
1.165
1.166 - public :
1.167 + // The directed graph the algorithm runs on
1.168 + const Graph &_graph;
1.169 + // The original lower bound map
1.170 + const LowerMap *_lower;
1.171 + // The modified capacity map
1.172 + CapacityEdgeMap _capacity;
1.173 + // The original cost map
1.174 + const CostMap &_cost;
1.175 + // The modified supply map
1.176 + SupplyNodeMap _supply;
1.177 + bool _valid_supply;
1.178 +
1.179 + // Edge map of the current flow
1.180 + FlowMap _flow;
1.181 +
1.182 + // The residual graph
1.183 + ResGraph _res_graph;
1.184 + // The residual cost map
1.185 + ResidualCostMap _res_cost;
1.186 +
1.187 + public:
1.188
1.189 /// \brief General constructor of the class (with lower bounds).
1.190 ///
1.191 /// General constructor of the class (with lower bounds).
1.192 ///
1.193 - /// \param _graph The directed graph the algorithm runs on.
1.194 - /// \param _lower The lower bounds of the edges.
1.195 - /// \param _capacity The capacities (upper bounds) of the edges.
1.196 - /// \param _cost The cost (length) values of the edges.
1.197 - /// \param _supply The supply values of the nodes (signed).
1.198 - CycleCanceling( const Graph &_graph,
1.199 - const LowerMap &_lower,
1.200 - const CapacityMap &_capacity,
1.201 - const CostMap &_cost,
1.202 - const SupplyMap &_supply ) :
1.203 - graph(_graph), lower(&_lower), capacity(_graph), cost(_cost),
1.204 - supply(_graph), flow(_graph, 0),
1.205 - res_graph(_graph, capacity, flow), res_cost(cost)
1.206 + /// \param graph The directed graph the algorithm runs on.
1.207 + /// \param lower The lower bounds of the edges.
1.208 + /// \param capacity The capacities (upper bounds) of the edges.
1.209 + /// \param cost The cost (length) values of the edges.
1.210 + /// \param supply The supply values of the nodes (signed).
1.211 + CycleCanceling( const Graph &graph,
1.212 + const LowerMap &lower,
1.213 + const CapacityMap &capacity,
1.214 + const CostMap &cost,
1.215 + const SupplyMap &supply ) :
1.216 + _graph(graph), _lower(&lower), _capacity(graph), _cost(cost),
1.217 + _supply(graph), _flow(graph, 0),
1.218 + _res_graph(graph, _capacity, _flow), _res_cost(_cost)
1.219 {
1.220 // Removing non-zero lower bounds
1.221 - capacity = subMap(_capacity, _lower);
1.222 + _capacity = subMap(capacity, lower);
1.223 Supply sum = 0;
1.224 - for (NodeIt n(graph); n != INVALID; ++n) {
1.225 - Supply s = _supply[n];
1.226 - for (InEdgeIt e(graph, n); e != INVALID; ++e)
1.227 - s += _lower[e];
1.228 - for (OutEdgeIt e(graph, n); e != INVALID; ++e)
1.229 - s -= _lower[e];
1.230 - sum += (supply[n] = s);
1.231 + for (NodeIt n(_graph); n != INVALID; ++n) {
1.232 + Supply s = supply[n];
1.233 + for (InEdgeIt e(_graph, n); e != INVALID; ++e)
1.234 + s += lower[e];
1.235 + for (OutEdgeIt e(_graph, n); e != INVALID; ++e)
1.236 + s -= lower[e];
1.237 + sum += (_supply[n] = s);
1.238 }
1.239 - valid_supply = sum == 0;
1.240 + _valid_supply = sum == 0;
1.241 }
1.242
1.243 /// \brief General constructor of the class (without lower bounds).
1.244 ///
1.245 /// General constructor of the class (without lower bounds).
1.246 ///
1.247 - /// \param _graph The directed graph the algorithm runs on.
1.248 - /// \param _capacity The capacities (upper bounds) of the edges.
1.249 - /// \param _cost The cost (length) values of the edges.
1.250 - /// \param _supply The supply values of the nodes (signed).
1.251 - CycleCanceling( const Graph &_graph,
1.252 - const CapacityMap &_capacity,
1.253 - const CostMap &_cost,
1.254 - const SupplyMap &_supply ) :
1.255 - graph(_graph), lower(NULL), capacity(_capacity), cost(_cost),
1.256 - supply(_supply), flow(_graph, 0),
1.257 - res_graph(_graph, capacity, flow), res_cost(cost)
1.258 + /// \param graph The directed graph the algorithm runs on.
1.259 + /// \param capacity The capacities (upper bounds) of the edges.
1.260 + /// \param cost The cost (length) values of the edges.
1.261 + /// \param supply The supply values of the nodes (signed).
1.262 + CycleCanceling( const Graph &graph,
1.263 + const CapacityMap &capacity,
1.264 + const CostMap &cost,
1.265 + const SupplyMap &supply ) :
1.266 + _graph(graph), _lower(NULL), _capacity(capacity), _cost(cost),
1.267 + _supply(supply), _flow(graph, 0),
1.268 + _res_graph(graph, _capacity, _flow), _res_cost(_cost)
1.269 {
1.270 // Checking the sum of supply values
1.271 Supply sum = 0;
1.272 - for (NodeIt n(graph); n != INVALID; ++n) sum += supply[n];
1.273 - valid_supply = sum == 0;
1.274 + for (NodeIt n(_graph); n != INVALID; ++n) sum += _supply[n];
1.275 + _valid_supply = sum == 0;
1.276 }
1.277
1.278 /// \brief Simple constructor of the class (with lower bounds).
1.279 ///
1.280 /// Simple constructor of the class (with lower bounds).
1.281 ///
1.282 - /// \param _graph The directed graph the algorithm runs on.
1.283 - /// \param _lower The lower bounds of the edges.
1.284 - /// \param _capacity The capacities (upper bounds) of the edges.
1.285 - /// \param _cost The cost (length) values of the edges.
1.286 - /// \param _s The source node.
1.287 - /// \param _t The target node.
1.288 - /// \param _flow_value The required amount of flow from node \c _s
1.289 - /// to node \c _t (i.e. the supply of \c _s and the demand of \c _t).
1.290 - CycleCanceling( const Graph &_graph,
1.291 - const LowerMap &_lower,
1.292 - const CapacityMap &_capacity,
1.293 - const CostMap &_cost,
1.294 - Node _s, Node _t,
1.295 - Supply _flow_value ) :
1.296 - graph(_graph), lower(&_lower), capacity(_graph), cost(_cost),
1.297 - supply(_graph), flow(_graph, 0),
1.298 - res_graph(_graph, capacity, flow), res_cost(cost)
1.299 + /// \param graph The directed graph the algorithm runs on.
1.300 + /// \param lower The lower bounds of the edges.
1.301 + /// \param capacity The capacities (upper bounds) of the edges.
1.302 + /// \param cost The cost (length) values of the edges.
1.303 + /// \param s The source node.
1.304 + /// \param t The target node.
1.305 + /// \param flow_value The required amount of flow from node \c s
1.306 + /// to node \c t (i.e. the supply of \c s and the demand of \c t).
1.307 + CycleCanceling( const Graph &graph,
1.308 + const LowerMap &lower,
1.309 + const CapacityMap &capacity,
1.310 + const CostMap &cost,
1.311 + Node s, Node t,
1.312 + Supply flow_value ) :
1.313 + _graph(graph), _lower(&lower), _capacity(graph), _cost(cost),
1.314 + _supply(graph), _flow(graph, 0),
1.315 + _res_graph(graph, _capacity, _flow), _res_cost(_cost)
1.316 {
1.317 // Removing non-zero lower bounds
1.318 - capacity = subMap(_capacity, _lower);
1.319 - for (NodeIt n(graph); n != INVALID; ++n) {
1.320 - Supply s = 0;
1.321 - if (n == _s) s = _flow_value;
1.322 - if (n == _t) s = -_flow_value;
1.323 - for (InEdgeIt e(graph, n); e != INVALID; ++e)
1.324 - s += _lower[e];
1.325 - for (OutEdgeIt e(graph, n); e != INVALID; ++e)
1.326 - s -= _lower[e];
1.327 - supply[n] = s;
1.328 + _capacity = subMap(capacity, lower);
1.329 + for (NodeIt n(_graph); n != INVALID; ++n) {
1.330 + Supply sum = 0;
1.331 + if (n == s) sum = flow_value;
1.332 + if (n == t) sum = -flow_value;
1.333 + for (InEdgeIt e(_graph, n); e != INVALID; ++e)
1.334 + sum += lower[e];
1.335 + for (OutEdgeIt e(_graph, n); e != INVALID; ++e)
1.336 + sum -= lower[e];
1.337 + _supply[n] = sum;
1.338 }
1.339 - valid_supply = true;
1.340 + _valid_supply = true;
1.341 }
1.342
1.343 /// \brief Simple constructor of the class (without lower bounds).
1.344 ///
1.345 /// Simple constructor of the class (without lower bounds).
1.346 ///
1.347 - /// \param _graph The directed graph the algorithm runs on.
1.348 - /// \param _capacity The capacities (upper bounds) of the edges.
1.349 - /// \param _cost The cost (length) values of the edges.
1.350 - /// \param _s The source node.
1.351 - /// \param _t The target node.
1.352 - /// \param _flow_value The required amount of flow from node \c _s
1.353 - /// to node \c _t (i.e. the supply of \c _s and the demand of \c _t).
1.354 - CycleCanceling( const Graph &_graph,
1.355 - const CapacityMap &_capacity,
1.356 - const CostMap &_cost,
1.357 - Node _s, Node _t,
1.358 - Supply _flow_value ) :
1.359 - graph(_graph), lower(NULL), capacity(_capacity), cost(_cost),
1.360 - supply(_graph, 0), flow(_graph, 0),
1.361 - res_graph(_graph, capacity, flow), res_cost(cost)
1.362 + /// \param graph The directed graph the algorithm runs on.
1.363 + /// \param capacity The capacities (upper bounds) of the edges.
1.364 + /// \param cost The cost (length) values of the edges.
1.365 + /// \param s The source node.
1.366 + /// \param t The target node.
1.367 + /// \param flow_value The required amount of flow from node \c s
1.368 + /// to node \c t (i.e. the supply of \c s and the demand of \c t).
1.369 + CycleCanceling( const Graph &graph,
1.370 + const CapacityMap &capacity,
1.371 + const CostMap &cost,
1.372 + Node s, Node t,
1.373 + Supply flow_value ) :
1.374 + _graph(graph), _lower(NULL), _capacity(capacity), _cost(cost),
1.375 + _supply(graph, 0), _flow(graph, 0),
1.376 + _res_graph(graph, _capacity, _flow), _res_cost(_cost)
1.377 {
1.378 - supply[_s] = _flow_value;
1.379 - supply[_t] = -_flow_value;
1.380 - valid_supply = true;
1.381 + _supply[s] = flow_value;
1.382 + _supply[t] = -flow_value;
1.383 + _valid_supply = true;
1.384 }
1.385
1.386 /// \brief Runs the algorithm.
1.387 ///
1.388 /// Runs the algorithm.
1.389 ///
1.390 + /// \param min_mean_cc Set this parameter to \c true to run the
1.391 + /// "Minimum Mean Cycle-Canceling" algorithm, which is strongly
1.392 + /// polynomial, but rather slower in practice.
1.393 + ///
1.394 /// \return \c true if a feasible flow can be found.
1.395 - bool run() {
1.396 - return init() && start();
1.397 + bool run(bool min_mean_cc = false) {
1.398 + return init() && start(min_mean_cc);
1.399 }
1.400
1.401 - /// \brief Returns a const reference to the flow map.
1.402 + /// \brief Returns a const reference to the edge map storing the
1.403 + /// found flow.
1.404 ///
1.405 - /// Returns a const reference to the flow map.
1.406 + /// Returns a const reference to the edge map storing the found flow.
1.407 ///
1.408 /// \pre \ref run() must be called before using this function.
1.409 const FlowMap& flowMap() const {
1.410 - return flow;
1.411 + return _flow;
1.412 }
1.413
1.414 /// \brief Returns the total cost of the found flow.
1.415 @@ -294,57 +299,54 @@
1.416 /// \pre \ref run() must be called before using this function.
1.417 Cost totalCost() const {
1.418 Cost c = 0;
1.419 - for (EdgeIt e(graph); e != INVALID; ++e)
1.420 - c += flow[e] * cost[e];
1.421 + for (EdgeIt e(_graph); e != INVALID; ++e)
1.422 + c += _flow[e] * _cost[e];
1.423 return c;
1.424 }
1.425
1.426 - protected:
1.427 + private:
1.428
1.429 /// Initializes the algorithm.
1.430 bool init() {
1.431 - // Checking the sum of supply values
1.432 - Supply sum = 0;
1.433 - for (NodeIt n(graph); n != INVALID; ++n) sum += supply[n];
1.434 - if (sum != 0) return false;
1.435 + if (!_valid_supply) return false;
1.436
1.437 - // Finding a feasible flow
1.438 + // Finding a feasible flow using Circulation
1.439 Circulation< Graph, ConstMap<Edge, Capacity>, CapacityEdgeMap,
1.440 SupplyMap >
1.441 - circulation( graph, constMap<Edge>((Capacity)0), capacity,
1.442 - supply );
1.443 - circulation.flowMap(flow);
1.444 - return circulation.run();
1.445 + circulation( _graph, constMap<Edge>((Capacity)0), _capacity,
1.446 + _supply );
1.447 + return circulation.flowMap(_flow).run();
1.448 }
1.449
1.450 -#ifdef LIMITED_CYCLE_CANCELING
1.451 - /// \brief Executes a cycle-canceling algorithm using
1.452 - /// \ref Bellman-Ford algorithm with limited iteration count.
1.453 + bool start(bool min_mean_cc) {
1.454 + if (min_mean_cc)
1.455 + return startMinMean();
1.456 + else
1.457 + return start();
1.458 + }
1.459 +
1.460 + /// \brief Executes the algorithm using \ref BellmanFord.
1.461 + ///
1.462 + /// Executes the algorithm using the \ref BellmanFord
1.463 + /// "Bellman-Ford" algorithm for negative cycle detection with
1.464 + /// successively larger limit for the number of iterations.
1.465 bool start() {
1.466 - typename BellmanFord<ResGraph, ResCostMap>::PredMap pred(res_graph);
1.467 - typename ResGraph::template NodeMap<int> visited(res_graph);
1.468 + typename BellmanFord<ResGraph, ResidualCostMap>::PredMap pred(_res_graph);
1.469 + typename ResGraph::template NodeMap<int> visited(_res_graph);
1.470 std::vector<ResEdge> cycle;
1.471 - int node_num = countNodes(graph);
1.472 + int node_num = countNodes(_graph);
1.473
1.474 -#ifdef _DEBUG_ITER_
1.475 - int cycle_num = 0;
1.476 -#endif
1.477 - int length_bound = STARTING_LIMIT;
1.478 + int length_bound = BF_FIRST_LIMIT;
1.479 bool optimal = false;
1.480 while (!optimal) {
1.481 - BellmanFord<ResGraph, ResCostMap> bf(res_graph, res_cost);
1.482 + BellmanFord<ResGraph, ResidualCostMap> bf(_res_graph, _res_cost);
1.483 bf.predMap(pred);
1.484 bf.init(0);
1.485 int iter_num = 0;
1.486 bool cycle_found = false;
1.487 while (!cycle_found) {
1.488 -#ifdef _NO_BACK_STEP_
1.489 - int curr_iter_num = length_bound <= node_num ?
1.490 - length_bound - iter_num : node_num - iter_num;
1.491 -#else
1.492 int curr_iter_num = iter_num + length_bound <= node_num ?
1.493 length_bound : node_num - iter_num;
1.494 -#endif
1.495 iter_num += curr_iter_num;
1.496 int real_iter_num = curr_iter_num;
1.497 for (int i = 0; i < curr_iter_num; ++i) {
1.498 @@ -358,18 +360,18 @@
1.499 break;
1.500 } else {
1.501 // Searching for node disjoint negative cycles
1.502 - for (ResNodeIt n(res_graph); n != INVALID; ++n)
1.503 + for (ResNodeIt n(_res_graph); n != INVALID; ++n)
1.504 visited[n] = 0;
1.505 int id = 0;
1.506 - for (ResNodeIt n(res_graph); n != INVALID; ++n) {
1.507 + for (ResNodeIt n(_res_graph); n != INVALID; ++n) {
1.508 if (visited[n] > 0) continue;
1.509 visited[n] = ++id;
1.510 ResNode u = pred[n] == INVALID ?
1.511 - INVALID : res_graph.source(pred[n]);
1.512 + INVALID : _res_graph.source(pred[n]);
1.513 while (u != INVALID && visited[u] == 0) {
1.514 visited[u] = id;
1.515 u = pred[u] == INVALID ?
1.516 - INVALID : res_graph.source(pred[u]);
1.517 + INVALID : _res_graph.source(pred[u]);
1.518 }
1.519 if (u != INVALID && visited[u] == id) {
1.520 // Finding the negative cycle
1.521 @@ -377,62 +379,45 @@
1.522 cycle.clear();
1.523 ResEdge e = pred[u];
1.524 cycle.push_back(e);
1.525 - Capacity d = res_graph.rescap(e);
1.526 - while (res_graph.source(e) != u) {
1.527 - cycle.push_back(e = pred[res_graph.source(e)]);
1.528 - if (res_graph.rescap(e) < d)
1.529 - d = res_graph.rescap(e);
1.530 + Capacity d = _res_graph.rescap(e);
1.531 + while (_res_graph.source(e) != u) {
1.532 + cycle.push_back(e = pred[_res_graph.source(e)]);
1.533 + if (_res_graph.rescap(e) < d)
1.534 + d = _res_graph.rescap(e);
1.535 }
1.536 -#ifdef _DEBUG_ITER_
1.537 - ++cycle_num;
1.538 -#endif
1.539 +
1.540 // Augmenting along the cycle
1.541 - for (int i = 0; i < cycle.size(); ++i)
1.542 - res_graph.augment(cycle[i], d);
1.543 -#ifdef _ONLY_ONE_CYCLE_
1.544 - break;
1.545 -#endif
1.546 + for (int i = 0; i < int(cycle.size()); ++i)
1.547 + _res_graph.augment(cycle[i], d);
1.548 }
1.549 }
1.550 }
1.551
1.552 if (!cycle_found)
1.553 - length_bound = length_bound * ALPHA_MUL / ALPHA_DIV;
1.554 + length_bound = int(length_bound * BF_ALPHA);
1.555 }
1.556 }
1.557
1.558 -#ifdef _DEBUG_ITER_
1.559 - std::cout << "Limited cycle-canceling algorithm finished. "
1.560 - << "Found " << cycle_num << " negative cycles."
1.561 - << std::endl;
1.562 -#endif
1.563 -
1.564 // Handling non-zero lower bounds
1.565 - if (lower) {
1.566 - for (EdgeIt e(graph); e != INVALID; ++e)
1.567 - flow[e] += (*lower)[e];
1.568 + if (_lower) {
1.569 + for (EdgeIt e(_graph); e != INVALID; ++e)
1.570 + _flow[e] += (*_lower)[e];
1.571 }
1.572 return true;
1.573 }
1.574 -#endif
1.575
1.576 -#ifdef MIN_MEAN_CYCLE_CANCELING
1.577 - /// \brief Executes the minimum mean cycle-canceling algorithm
1.578 - /// using \ref MinMeanCycle.
1.579 - bool start() {
1.580 + /// \brief Executes the algorithm using \ref MinMeanCycle.
1.581 + ///
1.582 + /// Executes the algorithm using \ref MinMeanCycle for negative
1.583 + /// cycle detection.
1.584 + bool startMinMean() {
1.585 typedef Path<ResGraph> ResPath;
1.586 - MinMeanCycle<ResGraph, ResCostMap> mmc(res_graph, res_cost);
1.587 + MinMeanCycle<ResGraph, ResidualCostMap> mmc(_res_graph, _res_cost);
1.588 ResPath cycle;
1.589
1.590 -#ifdef _DEBUG_ITER_
1.591 - int cycle_num = 0;
1.592 -#endif
1.593 mmc.cyclePath(cycle).init();
1.594 if (mmc.findMinMean()) {
1.595 while (mmc.cycleLength() < 0) {
1.596 -#ifdef _DEBUG_ITER_
1.597 - ++cycle_num;
1.598 -#endif
1.599 // Finding the cycle
1.600 mmc.findCycle();
1.601
1.602 @@ -440,13 +425,13 @@
1.603 // along the cycle
1.604 Capacity delta = 0;
1.605 for (typename ResPath::EdgeIt e(cycle); e != INVALID; ++e) {
1.606 - if (delta == 0 || res_graph.rescap(e) < delta)
1.607 - delta = res_graph.rescap(e);
1.608 + if (delta == 0 || _res_graph.rescap(e) < delta)
1.609 + delta = _res_graph.rescap(e);
1.610 }
1.611
1.612 // Augmenting along the cycle
1.613 for (typename ResPath::EdgeIt e(cycle); e != INVALID; ++e)
1.614 - res_graph.augment(e, delta);
1.615 + _res_graph.augment(e, delta);
1.616
1.617 // Finding the minimum cycle mean for the modified residual
1.618 // graph
1.619 @@ -455,20 +440,13 @@
1.620 }
1.621 }
1.622
1.623 -#ifdef _DEBUG_ITER_
1.624 - std::cout << "Minimum mean cycle-canceling algorithm finished. "
1.625 - << "Found " << cycle_num << " negative cycles."
1.626 - << std::endl;
1.627 -#endif
1.628 -
1.629 // Handling non-zero lower bounds
1.630 - if (lower) {
1.631 - for (EdgeIt e(graph); e != INVALID; ++e)
1.632 - flow[e] += (*lower)[e];
1.633 + if (_lower) {
1.634 + for (EdgeIt e(_graph); e != INVALID; ++e)
1.635 + _flow[e] += (*_lower)[e];
1.636 }
1.637 return true;
1.638 }
1.639 -#endif
1.640
1.641 }; //class CycleCanceling
1.642