Changeset 2573:a9758ea1f01c in lemon0.x for lemon/cycle_canceling.h
 Timestamp:
 02/18/08 04:30:12 (12 years ago)
 Branch:
 default
 Phase:
 public
 Convert:
 svn:c9d7d8f590d60310b91f818b3a526b0e/lemon/trunk@3455
 File:

 1 edited
Legend:
 Unmodified
 Added
 Removed

lemon/cycle_canceling.h
r2556 r2573 23 23 /// 24 24 /// \file 25 /// \brief A cyclecanceling algorithm for finding a minimum cost flow.25 /// \brief Cyclecanceling algorithm for finding a minimum cost flow. 26 26 27 27 #include <vector> 28 28 #include <lemon/graph_adaptor.h> 29 #include <lemon/path.h> 30 29 31 #include <lemon/circulation.h> 30 31 /// \brief The used cyclecanceling 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 // BellmanFord algorithm. It should be at least 2. 39 #define STARTING_LIMIT 2 40 // The iteration limit for the BellmanFord 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> 56 34 57 35 namespace lemon { … … 66 44 /// finding a minimum cost flow. 67 45 /// 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. 73 51 /// 74 52 /// \warning 75 ///  Edge capacities and costs should be nonnegative 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 nonnegative \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 "BellmanFord" algorithm is 62 /// used for negative cycle detection with limited iteration number. 63 /// However \ref CycleCanceling also provides the "Minimum Mean 64 /// CycleCanceling" 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. 81 68 /// 82 69 /// \author Peter Kovacs … … 84 71 template < typename Graph, 85 72 typename LowerMap = typename Graph::template EdgeMap<int>, 86 typename CapacityMap = LowerMap,73 typename CapacityMap = typename Graph::template EdgeMap<int>, 87 74 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> > 90 76 class CycleCanceling 91 77 { 92 78 GRAPH_TYPEDEFS(typename Graph); 93 79 94 typedef typename LowerMap::Value Lower;95 80 typedef typename CapacityMap::Value Capacity; 96 81 typedef typename CostMap::Value Cost; … … 111 96 typedef typename Graph::template EdgeMap<Capacity> FlowMap; 112 97 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> 117 105 { 118 106 private: 119 107 120 const CostMap & cost_map;108 const CostMap &_cost_map; 121 109 122 110 public: 123 111 124 ResCostMap(const CostMap &_cost) : cost_map(_cost) {} 125 112 ///\e 113 ResidualCostMap(const CostMap &cost_map) : _cost_map(cost_map) {} 114 115 ///\e 126 116 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 // BellmanFord algorithm. It should be at least 2. 126 static const int BF_FIRST_LIMIT = 2; 127 // The iteration limit for the BellmanFord 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: 154 154 155 155 /// \brief General constructor of the class (with lower bounds). … … 157 157 /// General constructor of the class (with lower bounds). 158 158 /// 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) 172 172 { 173 173 // Removing nonzero lower bounds 174 capacity = subMap(_capacity, _lower);174 _capacity = subMap(capacity, lower); 175 175 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; 185 185 } 186 186 … … 189 189 /// General constructor of the class (without lower bounds). 190 190 /// 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) 202 202 { 203 203 // Checking the sum of supply values 204 204 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; 207 207 } 208 208 … … 211 211 /// Simple constructor of the class (with lower bounds). 212 212 /// 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 _s220 /// 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) 230 230 { 231 231 // Removing nonzero 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; 244 244 } 245 245 … … 248 248 /// Simple constructor of the class (without lower bounds). 249 249 /// 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 _s256 /// 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) 265 265 { 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; 269 269 } 270 270 … … 273 273 /// Runs the algorithm. 274 274 /// 275 /// \param min_mean_cc Set this parameter to \c true to run the 276 /// "Minimum Mean CycleCanceling" algorithm, which is strongly 277 /// polynomial, but rather slower in practice. 278 /// 275 279 /// \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. 283 288 /// 284 289 /// \pre \ref run() must be called before using this function. 285 290 const FlowMap& flowMap() const { 286 return flow;291 return _flow; 287 292 } 288 293 … … 295 300 Cost totalCost() const { 296 301 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]; 299 304 return c; 300 305 } 301 306 302 pr otected:307 private: 303 308 304 309 /// Initializes the algorithm. 305 310 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 312 314 Circulation< Graph, ConstMap<Edge, Capacity>, CapacityEdgeMap, 313 315 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 cyclecanceling algorithm using 322 /// \ref BellmanFord 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 /// "BellmanFord" algorithm for negative cycle detection with 332 /// successively larger limit for the number of iterations. 323 333 bool start() { 324 typename BellmanFord<ResGraph, Res CostMap>::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); 326 336 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; 333 340 bool optimal = false; 334 341 while (!optimal) { 335 BellmanFord<ResGraph, Res CostMap> bf(res_graph,res_cost);342 BellmanFord<ResGraph, ResidualCostMap> bf(_res_graph, _res_cost); 336 343 bf.predMap(pred); 337 344 bf.init(0); … … 339 346 bool cycle_found = false; 340 347 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 #else345 348 int curr_iter_num = iter_num + length_bound <= node_num ? 346 349 length_bound : node_num  iter_num; 347 #endif348 350 iter_num += curr_iter_num; 349 351 int real_iter_num = curr_iter_num; … … 359 361 } else { 360 362 // Searching for node disjoint negative cycles 361 for (ResNodeIt n( res_graph); n != INVALID; ++n)363 for (ResNodeIt n(_res_graph); n != INVALID; ++n) 362 364 visited[n] = 0; 363 365 int id = 0; 364 for (ResNodeIt n( res_graph); n != INVALID; ++n) {366 for (ResNodeIt n(_res_graph); n != INVALID; ++n) { 365 367 if (visited[n] > 0) continue; 366 368 visited[n] = ++id; 367 369 ResNode u = pred[n] == INVALID ? 368 INVALID : res_graph.source(pred[n]);370 INVALID : _res_graph.source(pred[n]); 369 371 while (u != INVALID && visited[u] == 0) { 370 372 visited[u] = id; 371 373 u = pred[u] == INVALID ? 372 INVALID : res_graph.source(pred[u]);374 INVALID : _res_graph.source(pred[u]); 373 375 } 374 376 if (u != INVALID && visited[u] == id) { … … 378 380 ResEdge e = pred[u]; 379 381 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); 385 387 } 386 #ifdef _DEBUG_ITER_ 387 ++cycle_num; 388 #endif 388 389 389 // 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); 395 392 } 396 393 } … … 398 395 399 396 if (!cycle_found) 400 length_bound = length_bound * ALPHA_MUL / ALPHA_DIV;397 length_bound = int(length_bound * BF_ALPHA); 401 398 } 402 399 } 403 400 404 #ifdef _DEBUG_ITER_405 std::cout << "Limited cyclecanceling algorithm finished. "406 << "Found " << cycle_num << " negative cycles."407 << std::endl;408 #endif409 410 401 // Handling nonzero 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]; 414 405 } 415 406 return true; 416 407 } 417 #endif 418 419 #ifdef MIN_MEAN_CYCLE_CANCELING 420 /// \brief Executes the minimum mean cyclecanceling algorithm421 /// 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() { 423 414 typedef Path<ResGraph> ResPath; 424 MinMeanCycle<ResGraph, Res CostMap> mmc(res_graph,res_cost);415 MinMeanCycle<ResGraph, ResidualCostMap> mmc(_res_graph, _res_cost); 425 416 ResPath cycle; 426 417 427 #ifdef _DEBUG_ITER_428 int cycle_num = 0;429 #endif430 418 mmc.cyclePath(cycle).init(); 431 419 if (mmc.findMinMean()) { 432 420 while (mmc.cycleLength() < 0) { 433 #ifdef _DEBUG_ITER_434 ++cycle_num;435 #endif436 421 // Finding the cycle 437 422 mmc.findCycle(); … … 441 426 Capacity delta = 0; 442 427 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); 445 430 } 446 431 447 432 // Augmenting along the cycle 448 433 for (typename ResPath::EdgeIt e(cycle); e != INVALID; ++e) 449 res_graph.augment(e, delta);434 _res_graph.augment(e, delta); 450 435 451 436 // Finding the minimum cycle mean for the modified residual … … 456 441 } 457 442 458 #ifdef _DEBUG_ITER_459 std::cout << "Minimum mean cyclecanceling algorithm finished. "460 << "Found " << cycle_num << " negative cycles."461 << std::endl;462 #endif463 464 443 // Handling nonzero 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]; 468 447 } 469 448 return true; 470 449 } 471 #endif472 450 473 451 }; //class CycleCanceling
Note: See TracChangeset
for help on using the changeset viewer.