Changeset 2574:7058c9690e7d in lemon0.x
 Timestamp:
 02/18/08 04:30:53 (11 years ago)
 Branch:
 default
 Phase:
 public
 Convert:
 svn:c9d7d8f590d60310b91f818b3a526b0e/lemon/trunk@3456
 File:

 1 edited
Legend:
 Unmodified
 Added
 Removed

lemon/capacity_scaling.h
r2556 r2574 23 23 /// 24 24 /// \file 25 /// \brief The capacity scaling algorithm for finding a minimum cost flow. 25 /// \brief Capacity scaling algorithm for finding a minimum cost flow. 26 27 #include <vector> 26 28 27 29 #include <lemon/graph_adaptor.h> 28 30 #include <lemon/bin_heap.h> 29 #include <vector>30 31 31 32 namespace lemon { … … 34 35 /// @{ 35 36 36 /// \brief Implementation of the capacity scaling version of the 37 /// successive shortest path algorithm for finding a minimum cost 38 /// flow. 37 /// \brief Implementation of the capacity scaling algorithm for 38 /// finding a minimum cost flow. 39 39 /// 40 40 /// \ref CapacityScaling implements the capacity scaling version … … 42 42 /// cost flow. 43 43 /// 44 /// \ param Graph The directed graph type the algorithm runs on.45 /// \ param LowerMap The type of the lower bound map.46 /// \ param CapacityMap The type of the capacity (upper bound) map.47 /// \ param CostMap The type of the cost (length) map.48 /// \ param SupplyMap The type of the supply map.44 /// \tparam Graph The directed graph type the algorithm runs on. 45 /// \tparam LowerMap The type of the lower bound map. 46 /// \tparam CapacityMap The type of the capacity (upper bound) map. 47 /// \tparam CostMap The type of the cost (length) map. 48 /// \tparam SupplyMap The type of the supply map. 49 49 /// 50 50 /// \warning 51 ///  Edge capacities and costs should be nonnegative integers. 52 /// However \c CostMap::Value should be signed type. 53 ///  Supply values should be signed integers. 54 ///  \c LowerMap::Value must be convertible to 55 /// \c CapacityMap::Value and \c CapacityMap::Value must be 56 /// convertible to \c SupplyMap::Value. 51 ///  Edge capacities and costs should be \e nonnegative \e integers. 52 ///  Supply values should be \e signed \e integers. 53 ///  \c LowerMap::Value must be convertible to \c CapacityMap::Value. 54 ///  \c CapacityMap::Value and \c SupplyMap::Value must be 55 /// convertible to each other. 56 ///  All value types must be convertible to \c CostMap::Value, which 57 /// must be signed type. 57 58 /// 58 59 /// \author Peter Kovacs … … 60 61 template < typename Graph, 61 62 typename LowerMap = typename Graph::template EdgeMap<int>, 62 typename CapacityMap = LowerMap,63 typename CapacityMap = typename Graph::template EdgeMap<int>, 63 64 typename CostMap = typename Graph::template EdgeMap<int>, 64 typename SupplyMap = typename Graph::template NodeMap 65 <typename CapacityMap::Value> > 65 typename SupplyMap = typename Graph::template NodeMap<int> > 66 66 class CapacityScaling 67 67 { 68 68 GRAPH_TYPEDEFS(typename Graph); 69 69 70 typedef typename LowerMap::Value Lower;71 70 typedef typename CapacityMap::Value Capacity; 72 71 typedef typename CostMap::Value Cost; … … 78 77 public: 79 78 80 /// Type to enable or disable capacity scaling.81 enum ScalingEnum {82 WITH_SCALING = 0,83 WITHOUT_SCALING = 184 };85 86 79 /// The type of the flow map. 87 80 typedef typename Graph::template EdgeMap<Capacity> FlowMap; … … 89 82 typedef typename Graph::template NodeMap<Cost> PotentialMap; 90 83 91 pr otected:84 private: 92 85 93 86 /// \brief Special implementation of the \ref Dijkstra algorithm 94 /// for finding shortest paths in the residual network of the graph 95 /// with respect to the reduced edge costs and modifying the 96 /// node potentials according to the distance of the nodes. 87 /// for finding shortest paths in the residual network. 88 /// 89 /// \ref ResidualDijkstra is a special implementation of the 90 /// \ref Dijkstra algorithm for finding shortest paths in the 91 /// residual network of the graph with respect to the reduced edge 92 /// costs and modifying the node potentials according to the 93 /// distance of the nodes. 97 94 class ResidualDijkstra 98 95 { … … 103 100 typedef BinHeap<Cost, HeapCrossRef> Heap; 104 101 105 protected: 106 107 /// The directed graph the algorithm runs on. 108 const Graph &graph; 109 110 /// The flow map. 111 const FlowMap &flow; 112 /// The residual capacity map. 113 const CapacityEdgeMap &res_cap; 114 /// The cost map. 115 const CostMap &cost; 116 /// The excess map. 117 const SupplyNodeMap &excess; 118 119 /// The potential map. 120 PotentialMap &potential; 121 122 /// The distance map. 123 CostNodeMap dist; 124 /// The map of predecessors edges. 125 PredMap &pred; 126 /// The processed (i.e. permanently labeled) nodes. 127 std::vector<Node> proc_nodes; 102 private: 103 104 // The directed graph the algorithm runs on 105 const Graph &_graph; 106 107 // The main maps 108 const FlowMap &_flow; 109 const CapacityEdgeMap &_res_cap; 110 const CostMap &_cost; 111 const SupplyNodeMap &_excess; 112 PotentialMap &_potential; 113 114 // The distance map 115 CostNodeMap _dist; 116 // The pred edge map 117 PredMap &_pred; 118 // The processed (i.e. permanently labeled) nodes 119 std::vector<Node> _proc_nodes; 128 120 129 121 public: 130 122 131 123 /// The constructor of the class. 132 ResidualDijkstra( const Graph & _graph,133 const FlowMap & _flow,134 const CapacityEdgeMap & _res_cap,135 const CostMap & _cost,136 const SupplyMap & _excess,137 PotentialMap & _potential,138 PredMap & _pred ) :139 graph(_graph), flow(_flow), res_cap(_res_cap), cost(_cost),140 excess(_excess), potential(_potential), dist(_graph),141 pred(_pred)124 ResidualDijkstra( const Graph &graph, 125 const FlowMap &flow, 126 const CapacityEdgeMap &res_cap, 127 const CostMap &cost, 128 const SupplyMap &excess, 129 PotentialMap &potential, 130 PredMap &pred ) : 131 _graph(graph), _flow(flow), _res_cap(res_cap), _cost(cost), 132 _excess(excess), _potential(potential), _dist(graph), 133 _pred(pred) 142 134 {} 143 135 144 136 /// Runs the algorithm from the given source node. 145 137 Node run(Node s, Capacity delta) { 146 HeapCrossRef heap_cross_ref( graph, Heap::PRE_HEAP);138 HeapCrossRef heap_cross_ref(_graph, Heap::PRE_HEAP); 147 139 Heap heap(heap_cross_ref); 148 140 heap.push(s, 0); 149 pred[s] = INVALID;150 proc_nodes.clear();141 _pred[s] = INVALID; 142 _proc_nodes.clear(); 151 143 152 144 // Processing nodes 153 while (!heap.empty() && excess[heap.top()] > delta) {145 while (!heap.empty() && _excess[heap.top()] > delta) { 154 146 Node u = heap.top(), v; 155 Cost d = heap.prio() potential[u], nd;156 dist[u] = heap.prio();147 Cost d = heap.prio() + _potential[u], nd; 148 _dist[u] = heap.prio(); 157 149 heap.pop(); 158 proc_nodes.push_back(u);150 _proc_nodes.push_back(u); 159 151 160 152 // Traversing outgoing edges 161 for (OutEdgeIt e( graph, u); e != INVALID; ++e) {162 if ( res_cap[e] >= delta) {163 v = graph.target(e);153 for (OutEdgeIt e(_graph, u); e != INVALID; ++e) { 154 if (_res_cap[e] >= delta) { 155 v = _graph.target(e); 164 156 switch(heap.state(v)) { 165 157 case Heap::PRE_HEAP: 166 heap.push(v, d + cost[e] +potential[v]);167 pred[v] = e;158 heap.push(v, d + _cost[e]  _potential[v]); 159 _pred[v] = e; 168 160 break; 169 161 case Heap::IN_HEAP: 170 nd = d + cost[e] +potential[v];162 nd = d + _cost[e]  _potential[v]; 171 163 if (nd < heap[v]) { 172 164 heap.decrease(v, nd); 173 pred[v] = e;165 _pred[v] = e; 174 166 } 175 167 break; … … 181 173 182 174 // Traversing incoming edges 183 for (InEdgeIt e( graph, u); e != INVALID; ++e) {184 if ( flow[e] >= delta) {185 v = graph.source(e);175 for (InEdgeIt e(_graph, u); e != INVALID; ++e) { 176 if (_flow[e] >= delta) { 177 v = _graph.source(e); 186 178 switch(heap.state(v)) { 187 179 case Heap::PRE_HEAP: 188 heap.push(v, d  cost[e] +potential[v]);189 pred[v] = e;180 heap.push(v, d  _cost[e]  _potential[v]); 181 _pred[v] = e; 190 182 break; 191 183 case Heap::IN_HEAP: 192 nd = d  cost[e] +potential[v];184 nd = d  _cost[e]  _potential[v]; 193 185 if (nd < heap[v]) { 194 186 heap.decrease(v, nd); 195 pred[v] = e;187 _pred[v] = e; 196 188 } 197 189 break; … … 206 198 // Updating potentials of processed nodes 207 199 Node t = heap.top(); 208 Cost dt = heap.prio();209 for (int i = 0; i < proc_nodes.size(); ++i)210 potential[proc_nodes[i]] = dist[proc_nodes[i]]  dt;200 Cost t_dist = heap.prio(); 201 for (int i = 0; i < int(_proc_nodes.size()); ++i) 202 _potential[_proc_nodes[i]] += _dist[_proc_nodes[i]]  t_dist; 211 203 212 204 return t; … … 215 207 }; //class ResidualDijkstra 216 208 217 protected: 218 219 /// The directed graph the algorithm runs on. 220 const Graph &graph; 221 /// The original lower bound map. 222 const LowerMap *lower; 223 /// The modified capacity map. 224 CapacityEdgeMap capacity; 225 /// The cost map. 226 const CostMap &cost; 227 /// The modified supply map. 228 SupplyNodeMap supply; 229 bool valid_supply; 230 231 /// The edge map of the current flow. 232 FlowMap flow; 233 /// The potential node map. 234 PotentialMap potential; 235 236 /// The residual capacity map. 237 CapacityEdgeMap res_cap; 238 /// The excess map. 239 SupplyNodeMap excess; 240 /// The excess nodes (i.e. the nodes with positive excess). 241 std::vector<Node> excess_nodes; 242 /// The deficit nodes (i.e. the nodes with negative excess). 243 std::vector<Node> deficit_nodes; 244 245 /// The scaling status (enabled or disabled). 246 ScalingEnum scaling; 247 /// The \c delta parameter used for capacity scaling. 248 Capacity delta; 249 /// The maximum number of phases. 250 int phase_num; 251 252 /// \brief Implementation of the \ref Dijkstra algorithm for 253 /// finding augmenting shortest paths in the residual network. 254 ResidualDijkstra dijkstra; 255 /// The map of predecessors edges. 256 PredMap pred; 209 private: 210 211 // The directed graph the algorithm runs on 212 const Graph &_graph; 213 // The original lower bound map 214 const LowerMap *_lower; 215 // The modified capacity map 216 CapacityEdgeMap _capacity; 217 // The original cost map 218 const CostMap &_cost; 219 // The modified supply map 220 SupplyNodeMap _supply; 221 bool _valid_supply; 222 223 // Edge map of the current flow 224 FlowMap _flow; 225 // Node map of the current potentials 226 PotentialMap _potential; 227 228 // The residual capacity map 229 CapacityEdgeMap _res_cap; 230 // The excess map 231 SupplyNodeMap _excess; 232 // The excess nodes (i.e. nodes with positive excess) 233 std::vector<Node> _excess_nodes; 234 // The deficit nodes (i.e. nodes with negative excess) 235 std::vector<Node> _deficit_nodes; 236 237 // The delta parameter used for capacity scaling 238 Capacity _delta; 239 // The maximum number of phases 240 int _phase_num; 241 242 // The pred edge map 243 PredMap _pred; 244 // Implementation of the Dijkstra algorithm for finding augmenting 245 // shortest paths in the residual network 246 ResidualDijkstra _dijkstra; 257 247 258 248 public : … … 262 252 /// General constructor of the class (with lower bounds). 263 253 /// 264 /// \param _graph The directed graph the algorithm runs on.265 /// \param _lower The lower bounds of the edges.266 /// \param _capacity The capacities (upper bounds) of the edges.267 /// \param _cost The cost (length) values of the edges.268 /// \param _supply The supply values of the nodes (signed).269 CapacityScaling( const Graph & _graph,270 const LowerMap & _lower,271 const CapacityMap & _capacity,272 const CostMap & _cost,273 const SupplyMap & _supply ) :274 graph(_graph), lower(&_lower), capacity(_graph), cost(_cost),275 supply(_graph), flow(_graph, 0), potential(_graph, 0),276 res_cap(_graph), excess(_graph), pred(_graph),277 dijkstra(graph, flow, res_cap, cost, excess, potential,pred)254 /// \param graph The directed graph the algorithm runs on. 255 /// \param lower The lower bounds of the edges. 256 /// \param capacity The capacities (upper bounds) of the edges. 257 /// \param cost The cost (length) values of the edges. 258 /// \param supply The supply values of the nodes (signed). 259 CapacityScaling( const Graph &graph, 260 const LowerMap &lower, 261 const CapacityMap &capacity, 262 const CostMap &cost, 263 const SupplyMap &supply ) : 264 _graph(graph), _lower(&lower), _capacity(graph), _cost(cost), 265 _supply(graph), _flow(graph, 0), _potential(graph, 0), 266 _res_cap(graph), _excess(graph), _pred(graph), 267 _dijkstra(_graph, _flow, _res_cap, _cost, _excess, _potential, _pred) 278 268 { 279 269 // Removing nonzero lower bounds 280 capacity = subMap(_capacity, _lower);281 res_cap =capacity;270 _capacity = subMap(capacity, lower); 271 _res_cap = _capacity; 282 272 Supply sum = 0; 283 for (NodeIt n( graph); n != INVALID; ++n) {284 Supply s = _supply[n];285 for (InEdgeIt e( graph, n); e != INVALID; ++e)286 s += _lower[e];287 for (OutEdgeIt e( graph, n); e != INVALID; ++e)288 s = _lower[e];289 supply[n] = s;273 for (NodeIt n(_graph); n != INVALID; ++n) { 274 Supply s = supply[n]; 275 for (InEdgeIt e(_graph, n); e != INVALID; ++e) 276 s += lower[e]; 277 for (OutEdgeIt e(_graph, n); e != INVALID; ++e) 278 s = lower[e]; 279 _supply[n] = s; 290 280 sum += s; 291 281 } 292 valid_supply = sum == 0;282 _valid_supply = sum == 0; 293 283 } 294 284 … … 297 287 /// General constructor of the class (without lower bounds). 298 288 /// 299 /// \param _graph The directed graph the algorithm runs on.300 /// \param _capacity The capacities (upper bounds) of the edges.301 /// \param _cost The cost (length) values of the edges.302 /// \param _supply The supply values of the nodes (signed).303 CapacityScaling( const Graph & _graph,304 const CapacityMap & _capacity,305 const CostMap & _cost,306 const SupplyMap & _supply ) :307 graph(_graph), lower(NULL), capacity(_capacity), cost(_cost),308 supply(_supply), flow(_graph, 0), potential(_graph, 0),309 res_cap(_capacity), excess(_graph), pred(_graph),310 dijkstra(graph, flow, res_cap, cost, excess, potential)289 /// \param graph The directed graph the algorithm runs on. 290 /// \param capacity The capacities (upper bounds) of the edges. 291 /// \param cost The cost (length) values of the edges. 292 /// \param supply The supply values of the nodes (signed). 293 CapacityScaling( const Graph &graph, 294 const CapacityMap &capacity, 295 const CostMap &cost, 296 const SupplyMap &supply ) : 297 _graph(graph), _lower(NULL), _capacity(capacity), _cost(cost), 298 _supply(supply), _flow(graph, 0), _potential(graph, 0), 299 _res_cap(capacity), _excess(graph), _pred(graph), 300 _dijkstra(_graph, _flow, _res_cap, _cost, _excess, _potential, _pred) 311 301 { 312 302 // Checking the sum of supply values 313 303 Supply sum = 0; 314 for (NodeIt n( graph); n != INVALID; ++n) sum +=supply[n];315 valid_supply = sum == 0;304 for (NodeIt n(_graph); n != INVALID; ++n) sum += _supply[n]; 305 _valid_supply = sum == 0; 316 306 } 317 307 … … 320 310 /// Simple constructor of the class (with lower bounds). 321 311 /// 322 /// \param _graph The directed graph the algorithm runs on.323 /// \param _lower The lower bounds of the edges.324 /// \param _capacity The capacities (upper bounds) of the edges.325 /// \param _cost The cost (length) values of the edges.326 /// \param _s The source node.327 /// \param _t The target node.328 /// \param _flow_value The required amount of flow from node \c _s329 /// to node \c _t (i.e. the supply of \c _s and the demand of \c _t).330 CapacityScaling( const Graph & _graph,331 const LowerMap & _lower,332 const CapacityMap & _capacity,333 const CostMap & _cost,334 Node _s, Node _t,335 Supply _flow_value ) :336 graph(_graph), lower(&_lower), capacity(_graph), cost(_cost),337 supply(_graph), flow(_graph, 0), potential(_graph, 0),338 res_cap(_graph), excess(_graph), pred(_graph),339 dijkstra(graph, flow, res_cap, cost, excess, potential)312 /// \param graph The directed graph the algorithm runs on. 313 /// \param lower The lower bounds of the edges. 314 /// \param capacity The capacities (upper bounds) of the edges. 315 /// \param cost The cost (length) values of the edges. 316 /// \param s The source node. 317 /// \param t The target node. 318 /// \param flow_value The required amount of flow from node \c s 319 /// to node \c t (i.e. the supply of \c s and the demand of \c t). 320 CapacityScaling( const Graph &graph, 321 const LowerMap &lower, 322 const CapacityMap &capacity, 323 const CostMap &cost, 324 Node s, Node t, 325 Supply flow_value ) : 326 _graph(graph), _lower(&lower), _capacity(graph), _cost(cost), 327 _supply(graph), _flow(graph, 0), _potential(graph, 0), 328 _res_cap(graph), _excess(graph), _pred(graph), 329 _dijkstra(_graph, _flow, _res_cap, _cost, _excess, _potential, _pred) 340 330 { 341 331 // Removing nonzero lower bounds 342 capacity = subMap(_capacity, _lower);343 res_cap =capacity;344 for (NodeIt n( graph); n != INVALID; ++n) {345 Supply s = 0;346 if (n == _s) s = _flow_value;347 if (n == _t) s = _flow_value;348 for (InEdgeIt e( graph, n); e != INVALID; ++e)349 s += _lower[e];350 for (OutEdgeIt e( graph, n); e != INVALID; ++e)351 s = _lower[e];352 supply[n] = s;353 } 354 valid_supply = true;332 _capacity = subMap(capacity, lower); 333 _res_cap = _capacity; 334 for (NodeIt n(_graph); n != INVALID; ++n) { 335 Supply sum = 0; 336 if (n == s) sum = flow_value; 337 if (n == t) sum = flow_value; 338 for (InEdgeIt e(_graph, n); e != INVALID; ++e) 339 sum += lower[e]; 340 for (OutEdgeIt e(_graph, n); e != INVALID; ++e) 341 sum = lower[e]; 342 _supply[n] = sum; 343 } 344 _valid_supply = true; 355 345 } 356 346 … … 359 349 /// Simple constructor of the class (without lower bounds). 360 350 /// 361 /// \param _graph The directed graph the algorithm runs on.362 /// \param _capacity The capacities (upper bounds) of the edges.363 /// \param _cost The cost (length) values of the edges.364 /// \param _s The source node.365 /// \param _t The target node.366 /// \param _flow_value The required amount of flow from node \c _s367 /// to node \c _t (i.e. the supply of \c _s and the demand of \c _t).368 CapacityScaling( const Graph & _graph,369 const CapacityMap & _capacity,370 const CostMap & _cost,371 Node _s, Node _t,372 Supply _flow_value ) :373 graph(_graph), lower(NULL), capacity(_capacity), cost(_cost),374 supply(_graph, 0), flow(_graph, 0), potential(_graph, 0),375 res_cap(_capacity), excess(_graph), pred(_graph),376 dijkstra(graph, flow, res_cap, cost, excess, potential)351 /// \param graph The directed graph the algorithm runs on. 352 /// \param capacity The capacities (upper bounds) of the edges. 353 /// \param cost The cost (length) values of the edges. 354 /// \param s The source node. 355 /// \param t The target node. 356 /// \param flow_value The required amount of flow from node \c s 357 /// to node \c t (i.e. the supply of \c s and the demand of \c t). 358 CapacityScaling( const Graph &graph, 359 const CapacityMap &capacity, 360 const CostMap &cost, 361 Node s, Node t, 362 Supply flow_value ) : 363 _graph(graph), _lower(NULL), _capacity(capacity), _cost(cost), 364 _supply(graph, 0), _flow(graph, 0), _potential(graph, 0), 365 _res_cap(capacity), _excess(graph), _pred(graph), 366 _dijkstra(_graph, _flow, _res_cap, _cost, _excess, _potential, _pred) 377 367 { 378 supply[_s] = _flow_value;379 supply[_t] = _flow_value;380 valid_supply = true;368 _supply[s] = flow_value; 369 _supply[t] = flow_value; 370 _valid_supply = true; 381 371 } 382 372 … … 385 375 /// Runs the algorithm. 386 376 /// 387 /// \param scaling_mode The scaling mode. In case of WITH_SCALING 388 /// capacity scaling is enabled in the algorithm (this is the 389 /// default) otherwise it is disabled. 377 /// \param scaling Enable or disable capacity scaling. 390 378 /// If the maximum edge capacity and/or the amount of total supply 391 /// is small, the algorithm could be slightly faster without379 /// is rather small, the algorithm could be slightly faster without 392 380 /// scaling. 393 381 /// 394 382 /// \return \c true if a feasible flow can be found. 395 bool run(int scaling_mode = WITH_SCALING) { 396 return init(scaling_mode) && start(); 397 } 398 399 /// \brief Returns a const reference to the flow map. 400 /// 401 /// Returns a const reference to the flow map. 383 bool run(bool scaling = true) { 384 return init(scaling) && start(); 385 } 386 387 /// \brief Returns a const reference to the edge map storing the 388 /// found flow. 389 /// 390 /// Returns a const reference to the edge map storing the found flow. 402 391 /// 403 392 /// \pre \ref run() must be called before using this function. 404 393 const FlowMap& flowMap() const { 405 return flow;406 } 407 408 /// \brief Returns a const reference to the potential map (the dual409 /// solution).410 /// 411 /// Returns a const reference to the potential map (the dual412 /// solution).394 return _flow; 395 } 396 397 /// \brief Returns a const reference to the node map storing the 398 /// found potentials (the dual solution). 399 /// 400 /// Returns a const reference to the node map storing the found 401 /// potentials (the dual solution). 413 402 /// 414 403 /// \pre \ref run() must be called before using this function. 415 404 const PotentialMap& potentialMap() const { 416 return potential;405 return _potential; 417 406 } 418 407 … … 425 414 Cost totalCost() const { 426 415 Cost c = 0; 427 for (EdgeIt e( graph); e != INVALID; ++e)428 c += flow[e] *cost[e];416 for (EdgeIt e(_graph); e != INVALID; ++e) 417 c += _flow[e] * _cost[e]; 429 418 return c; 430 419 } 431 420 432 pr otected:421 private: 433 422 434 423 /// Initializes the algorithm. 435 bool init( int scaling_mode) {436 if (! valid_supply) return false;437 excess =supply;424 bool init(bool scaling) { 425 if (!_valid_supply) return false; 426 _excess = _supply; 438 427 439 428 // Initilaizing delta value 440 if (scaling _mode == WITH_SCALING) {429 if (scaling) { 441 430 // With scaling 442 431 Supply max_sup = 0, max_dem = 0; 443 for (NodeIt n( graph); n != INVALID; ++n) {444 if ( supply[n] > max_sup) max_sup =supply[n];445 if ( supply[n] > max_dem) max_dem = supply[n];432 for (NodeIt n(_graph); n != INVALID; ++n) { 433 if ( _supply[n] > max_sup) max_sup = _supply[n]; 434 if (_supply[n] > max_dem) max_dem = _supply[n]; 446 435 } 447 436 if (max_dem < max_sup) max_sup = max_dem; 448 phase_num = 0;449 for ( delta = 1; 2 * delta <= max_sup;delta *= 2)450 ++ phase_num;437 _phase_num = 0; 438 for (_delta = 1; 2 * _delta <= max_sup; _delta *= 2) 439 ++_phase_num; 451 440 } else { 452 441 // Without scaling 453 delta = 1;442 _delta = 1; 454 443 } 455 444 return true; 456 445 } 457 446 458 /// Executes the algorithm.459 447 bool start() { 460 if ( delta > 1)448 if (_delta > 1) 461 449 return startWithScaling(); 462 450 else … … 464 452 } 465 453 466 /// \brief Executes the capacity scaling version of the successive 467 /// shortest path algorithm. 454 /// Executes the capacity scaling algorithm. 468 455 bool startWithScaling() { 469 456 // Processing capacity scaling phases … … 473 460 while (true) { 474 461 // Saturating all edges not satisfying the optimality condition 475 for (EdgeIt e( graph); e != INVALID; ++e) {476 Node u = graph.source(e), v =graph.target(e);477 Cost c = cost[e]  potential[u] +potential[v];478 if (c < 0 && res_cap[e] >=delta) {479 excess[u] =res_cap[e];480 excess[v] +=res_cap[e];481 flow[e] =capacity[e];482 res_cap[e] = 0;483 } 484 else if (c > 0 && flow[e] >=delta) {485 excess[u] +=flow[e];486 excess[v] =flow[e];487 flow[e] = 0;488 res_cap[e] =capacity[e];462 for (EdgeIt e(_graph); e != INVALID; ++e) { 463 Node u = _graph.source(e), v = _graph.target(e); 464 Cost c = _cost[e] + _potential[u]  _potential[v]; 465 if (c < 0 && _res_cap[e] >= _delta) { 466 _excess[u] = _res_cap[e]; 467 _excess[v] += _res_cap[e]; 468 _flow[e] = _capacity[e]; 469 _res_cap[e] = 0; 470 } 471 else if (c > 0 && _flow[e] >= _delta) { 472 _excess[u] += _flow[e]; 473 _excess[v] = _flow[e]; 474 _flow[e] = 0; 475 _res_cap[e] = _capacity[e]; 489 476 } 490 477 } 491 478 492 479 // Finding excess nodes and deficit nodes 493 excess_nodes.clear();494 deficit_nodes.clear();495 for (NodeIt n( graph); n != INVALID; ++n) {496 if ( excess[n] >= delta)excess_nodes.push_back(n);497 if ( excess[n] <= delta)deficit_nodes.push_back(n);480 _excess_nodes.clear(); 481 _deficit_nodes.clear(); 482 for (NodeIt n(_graph); n != INVALID; ++n) { 483 if (_excess[n] >= _delta) _excess_nodes.push_back(n); 484 if (_excess[n] <= _delta) _deficit_nodes.push_back(n); 498 485 } 499 486 int next_node = 0; 500 487 501 488 // Finding augmenting shortest paths 502 while (next_node < excess_nodes.size()) {489 while (next_node < int(_excess_nodes.size())) { 503 490 // Checking deficit nodes 504 if ( delta > 1) {491 if (_delta > 1) { 505 492 bool delta_deficit = false; 506 for (int i = 0; i < deficit_nodes.size(); ++i) {507 if ( excess[deficit_nodes[i]] <= delta) {493 for (int i = 0; i < int(_deficit_nodes.size()); ++i) { 494 if (_excess[_deficit_nodes[i]] <= _delta) { 508 495 delta_deficit = true; 509 496 break; … … 514 501 515 502 // Running Dijkstra 516 s = excess_nodes[next_node];517 if ((t = dijkstra.run(s,delta)) == INVALID) {518 if ( delta > 1) {503 s = _excess_nodes[next_node]; 504 if ((t = _dijkstra.run(s, _delta)) == INVALID) { 505 if (_delta > 1) { 519 506 ++next_node; 520 507 continue; … … 524 511 525 512 // Augmenting along a shortest path from s to t. 526 Capacity d = excess[s] < excess[t] ? excess[s] : excess[t];513 Capacity d = _excess[s] < _excess[t] ? _excess[s] : _excess[t]; 527 514 Node u = t; 528 515 Edge e; 529 if (d > delta) {530 while ((e = pred[u]) != INVALID) {516 if (d > _delta) { 517 while ((e = _pred[u]) != INVALID) { 531 518 Capacity rc; 532 if (u == graph.target(e)) {533 rc = res_cap[e];534 u = graph.source(e);519 if (u == _graph.target(e)) { 520 rc = _res_cap[e]; 521 u = _graph.source(e); 535 522 } else { 536 rc = flow[e];537 u = graph.target(e);523 rc = _flow[e]; 524 u = _graph.target(e); 538 525 } 539 526 if (rc < d) d = rc; … … 541 528 } 542 529 u = t; 543 while ((e = pred[u]) != INVALID) {544 if (u == graph.target(e)) {545 flow[e] += d;546 res_cap[e] = d;547 u = graph.source(e);530 while ((e = _pred[u]) != INVALID) { 531 if (u == _graph.target(e)) { 532 _flow[e] += d; 533 _res_cap[e] = d; 534 u = _graph.source(e); 548 535 } else { 549 flow[e] = d;550 res_cap[e] += d;551 u = graph.target(e);536 _flow[e] = d; 537 _res_cap[e] += d; 538 u = _graph.target(e); 552 539 } 553 540 } 554 excess[s] = d;555 excess[t] += d;556 557 if ( excess[s] <delta) ++next_node;541 _excess[s] = d; 542 _excess[t] += d; 543 544 if (_excess[s] < _delta) ++next_node; 558 545 } 559 546 560 if ( delta == 1) break;561 if (++phase_cnt > phase_num / 4) factor = 2;562 delta = delta <= factor ? 1 :delta / factor;547 if (_delta == 1) break; 548 if (++phase_cnt > _phase_num / 4) factor = 2; 549 _delta = _delta <= factor ? 1 : _delta / factor; 563 550 } 564 551 565 552 // Handling nonzero lower bounds 566 if ( lower) {567 for (EdgeIt e( graph); e != INVALID; ++e)568 flow[e] += (*lower)[e];553 if (_lower) { 554 for (EdgeIt e(_graph); e != INVALID; ++e) 555 _flow[e] += (*_lower)[e]; 569 556 } 570 557 return true; 571 558 } 572 559 573 /// \brief Executes the successive shortest path algorithm without 574 /// capacity scaling. 560 /// Executes the successive shortest path algorithm. 575 561 bool startWithoutScaling() { 576 562 // Finding excess nodes 577 for (NodeIt n( graph); n != INVALID; ++n)578 if ( excess[n] > 0)excess_nodes.push_back(n);579 if ( excess_nodes.size() == 0) return true;563 for (NodeIt n(_graph); n != INVALID; ++n) 564 if (_excess[n] > 0) _excess_nodes.push_back(n); 565 if (_excess_nodes.size() == 0) return true; 580 566 int next_node = 0; 581 567 582 568 // Finding shortest paths 583 569 Node s, t; 584 while ( excess[excess_nodes[next_node]] > 0 585 ++next_node < excess_nodes.size() )570 while ( _excess[_excess_nodes[next_node]] > 0  571 ++next_node < int(_excess_nodes.size()) ) 586 572 { 587 573 // Running Dijkstra 588 s = excess_nodes[next_node];589 if ((t = dijkstra.run(s, 1)) == INVALID)574 s = _excess_nodes[next_node]; 575 if ((t = _dijkstra.run(s, 1)) == INVALID) 590 576 return false; 591 577 592 578 // Augmenting along a shortest path from s to t 593 Capacity d = excess[s] < excess[t] ? excess[s] : excess[t];579 Capacity d = _excess[s] < _excess[t] ? _excess[s] : _excess[t]; 594 580 Node u = t; 595 581 Edge e; 596 while ((e = pred[u]) != INVALID) {582 while ((e = _pred[u]) != INVALID) { 597 583 Capacity rc; 598 if (u == graph.target(e)) {599 rc = res_cap[e];600 u = graph.source(e);584 if (u == _graph.target(e)) { 585 rc = _res_cap[e]; 586 u = _graph.source(e); 601 587 } else { 602 rc = flow[e];603 u = graph.target(e);588 rc = _flow[e]; 589 u = _graph.target(e); 604 590 } 605 591 if (rc < d) d = rc; 606 592 } 607 593 u = t; 608 while ((e = pred[u]) != INVALID) {609 if (u == graph.target(e)) {610 flow[e] += d;611 res_cap[e] = d;612 u = graph.source(e);594 while ((e = _pred[u]) != INVALID) { 595 if (u == _graph.target(e)) { 596 _flow[e] += d; 597 _res_cap[e] = d; 598 u = _graph.source(e); 613 599 } else { 614 flow[e] = d;615 res_cap[e] += d;616 u = graph.target(e);600 _flow[e] = d; 601 _res_cap[e] += d; 602 u = _graph.target(e); 617 603 } 618 604 } 619 excess[s] = d;620 excess[t] += d;605 _excess[s] = d; 606 _excess[t] += d; 621 607 } 622 608 623 609 // Handling nonzero lower bounds 624 if ( lower) {625 for (EdgeIt e( graph); e != INVALID; ++e)626 flow[e] += (*lower)[e];610 if (_lower) { 611 for (EdgeIt e(_graph); e != INVALID; ++e) 612 _flow[e] += (*_lower)[e]; 627 613 } 628 614 return true;
Note: See TracChangeset
for help on using the changeset viewer.