Changeset 2581:054566ac0934 in lemon0.x
 Timestamp:
 02/28/08 03:54:27 (14 years ago)
 Branch:
 default
 Phase:
 public
 Convert:
 svn:c9d7d8f590d60310b91f818b3a526b0e/lemon/trunk@3463
 Location:
 lemon
 Files:

 5 edited
Legend:
 Unmodified
 Added
 Removed

lemon/capacity_scaling.h
r2574 r2581 51 51 ///  Edge capacities and costs should be \e nonnegative \e integers. 52 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. 53 ///  The value types of the maps should be convertible to each other. 54 ///  \c CostMap::Value must be signed type. 58 55 /// 59 56 /// \author Peter Kovacs … … 121 118 public: 122 119 123 /// The constructor of the class.120 /// Constructor. 124 121 ResidualDijkstra( const Graph &graph, 125 122 const FlowMap &flow, … … 222 219 223 220 // Edge map of the current flow 224 FlowMap _flow; 221 FlowMap *_flow; 222 bool _local_flow; 225 223 // Node map of the current potentials 226 PotentialMap _potential; 224 PotentialMap *_potential; 225 bool _local_potential; 227 226 228 227 // The residual capacity map … … 244 243 // Implementation of the Dijkstra algorithm for finding augmenting 245 244 // shortest paths in the residual network 246 ResidualDijkstra _dijkstra;247 248 public 249 250 /// \brief General constructor of the class(with lower bounds).251 /// 252 /// General constructor of the class(with lower bounds).245 ResidualDijkstra *_dijkstra; 246 247 public: 248 249 /// \brief General constructor (with lower bounds). 250 /// 251 /// General constructor (with lower bounds). 253 252 /// 254 253 /// \param graph The directed graph the algorithm runs on. … … 263 262 const SupplyMap &supply ) : 264 263 _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)264 _supply(graph), _flow(0), _local_flow(false), 265 _potential(0), _local_potential(false), 266 _res_cap(graph), _excess(graph), _pred(graph) 268 267 { 269 268 // Removing nonzero lower bounds … … 283 282 } 284 283 285 /// \brief General constructor of the class(without lower bounds).286 /// 287 /// General constructor of the class(without lower bounds).284 /// \brief General constructor (without lower bounds). 285 /// 286 /// General constructor (without lower bounds). 288 287 /// 289 288 /// \param graph The directed graph the algorithm runs on. … … 296 295 const SupplyMap &supply ) : 297 296 _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)297 _supply(supply), _flow(0), _local_flow(false), 298 _potential(0), _local_potential(false), 299 _res_cap(capacity), _excess(graph), _pred(graph) 301 300 { 302 301 // Checking the sum of supply values … … 306 305 } 307 306 308 /// \brief Simple constructor of the class(with lower bounds).309 /// 310 /// Simple constructor of the class(with lower bounds).307 /// \brief Simple constructor (with lower bounds). 308 /// 309 /// Simple constructor (with lower bounds). 311 310 /// 312 311 /// \param graph The directed graph the algorithm runs on. … … 325 324 Supply flow_value ) : 326 325 _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)326 _supply(graph), _flow(0), _local_flow(false), 327 _potential(0), _local_potential(false), 328 _res_cap(graph), _excess(graph), _pred(graph) 330 329 { 331 330 // Removing nonzero lower bounds … … 345 344 } 346 345 347 /// \brief Simple constructor of the class(without lower bounds).348 /// 349 /// Simple constructor of the class(without lower bounds).346 /// \brief Simple constructor (without lower bounds). 347 /// 348 /// Simple constructor (without lower bounds). 350 349 /// 351 350 /// \param graph The directed graph the algorithm runs on. … … 362 361 Supply flow_value ) : 363 362 _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)363 _supply(graph, 0), _flow(0), _local_flow(false), 364 _potential(0), _local_potential(false), 365 _res_cap(capacity), _excess(graph), _pred(graph) 367 366 { 368 367 _supply[s] = flow_value; … … 371 370 } 372 371 372 /// Destructor. 373 ~CapacityScaling() { 374 if (_local_flow) delete _flow; 375 if (_local_potential) delete _potential; 376 delete _dijkstra; 377 } 378 379 /// \brief Sets the flow map. 380 /// 381 /// Sets the flow map. 382 /// 383 /// \return \c (*this) 384 CapacityScaling& flowMap(FlowMap &map) { 385 if (_local_flow) { 386 delete _flow; 387 _local_flow = false; 388 } 389 _flow = ↦ 390 return *this; 391 } 392 393 /// \brief Sets the potential map. 394 /// 395 /// Sets the potential map. 396 /// 397 /// \return \c (*this) 398 CapacityScaling& potentialMap(PotentialMap &map) { 399 if (_local_potential) { 400 delete _potential; 401 _local_potential = false; 402 } 403 _potential = ↦ 404 return *this; 405 } 406 407 /// \name Execution control 408 /// The only way to execute the algorithm is to call the run() 409 /// function. 410 411 /// @{ 412 373 413 /// \brief Runs the algorithm. 374 414 /// … … 385 425 } 386 426 427 /// @} 428 429 /// \name Query Functions 430 /// The result of the algorithm can be obtained using these 431 /// functions. 432 /// \n run() must be called before using them. 433 434 /// @{ 435 387 436 /// \brief Returns a const reference to the edge map storing the 388 437 /// found flow. … … 392 441 /// \pre \ref run() must be called before using this function. 393 442 const FlowMap& flowMap() const { 394 return _flow;443 return *_flow; 395 444 } 396 445 … … 403 452 /// \pre \ref run() must be called before using this function. 404 453 const PotentialMap& potentialMap() const { 405 return _potential; 454 return *_potential; 455 } 456 457 /// \brief Returns the flow on the edge. 458 /// 459 /// Returns the flow on the edge. 460 /// 461 /// \pre \ref run() must be called before using this function. 462 Capacity flow(const Edge& edge) const { 463 return (*_flow)[edge]; 464 } 465 466 /// \brief Returns the potential of the node. 467 /// 468 /// Returns the potential of the node. 469 /// 470 /// \pre \ref run() must be called before using this function. 471 Cost potential(const Node& node) const { 472 return (*_potential)[node]; 406 473 } 407 474 … … 415 482 Cost c = 0; 416 483 for (EdgeIt e(_graph); e != INVALID; ++e) 417 c += _flow[e] * _cost[e];484 c += (*_flow)[e] * _cost[e]; 418 485 return c; 419 486 } 487 488 /// @} 420 489 421 490 private: … … 424 493 bool init(bool scaling) { 425 494 if (!_valid_supply) return false; 495 496 // Initializing maps 497 if (!_flow) { 498 _flow = new FlowMap(_graph); 499 _local_flow = true; 500 } 501 if (!_potential) { 502 _potential = new PotentialMap(_graph); 503 _local_potential = true; 504 } 505 for (EdgeIt e(_graph); e != INVALID; ++e) (*_flow)[e] = 0; 506 for (NodeIt n(_graph); n != INVALID; ++n) (*_potential)[n] = 0; 426 507 _excess = _supply; 427 508 428 // Initilaizing delta value 509 _dijkstra = new ResidualDijkstra( _graph, *_flow, _res_cap, _cost, 510 _excess, *_potential, _pred ); 511 512 // Initializing delta value 429 513 if (scaling) { 430 514 // With scaling … … 442 526 _delta = 1; 443 527 } 528 444 529 return true; 445 530 } … … 462 547 for (EdgeIt e(_graph); e != INVALID; ++e) { 463 548 Node u = _graph.source(e), v = _graph.target(e); 464 Cost c = _cost[e] + _potential[u]  _potential[v];549 Cost c = _cost[e] + (*_potential)[u]  (*_potential)[v]; 465 550 if (c < 0 && _res_cap[e] >= _delta) { 466 551 _excess[u] = _res_cap[e]; 467 552 _excess[v] += _res_cap[e]; 468 _flow[e] = _capacity[e];553 (*_flow)[e] = _capacity[e]; 469 554 _res_cap[e] = 0; 470 555 } 471 else if (c > 0 && _flow[e] >= _delta) {472 _excess[u] += _flow[e];473 _excess[v] = _flow[e];474 _flow[e] = 0;556 else if (c > 0 && (*_flow)[e] >= _delta) { 557 _excess[u] += (*_flow)[e]; 558 _excess[v] = (*_flow)[e]; 559 (*_flow)[e] = 0; 475 560 _res_cap[e] = _capacity[e]; 476 561 } … … 502 587 // Running Dijkstra 503 588 s = _excess_nodes[next_node]; 504 if ((t = _dijkstra .run(s, _delta)) == INVALID) {589 if ((t = _dijkstra>run(s, _delta)) == INVALID) { 505 590 if (_delta > 1) { 506 591 ++next_node; … … 521 606 u = _graph.source(e); 522 607 } else { 523 rc = _flow[e];608 rc = (*_flow)[e]; 524 609 u = _graph.target(e); 525 610 } … … 530 615 while ((e = _pred[u]) != INVALID) { 531 616 if (u == _graph.target(e)) { 532 _flow[e] += d;617 (*_flow)[e] += d; 533 618 _res_cap[e] = d; 534 619 u = _graph.source(e); 535 620 } else { 536 _flow[e] = d;621 (*_flow)[e] = d; 537 622 _res_cap[e] += d; 538 623 u = _graph.target(e); … … 553 638 if (_lower) { 554 639 for (EdgeIt e(_graph); e != INVALID; ++e) 555 _flow[e] += (*_lower)[e];640 (*_flow)[e] += (*_lower)[e]; 556 641 } 557 642 return true; … … 573 658 // Running Dijkstra 574 659 s = _excess_nodes[next_node]; 575 if ((t = _dijkstra .run(s, 1)) == INVALID)660 if ((t = _dijkstra>run(s, 1)) == INVALID) 576 661 return false; 577 662 … … 586 671 u = _graph.source(e); 587 672 } else { 588 rc = _flow[e];673 rc = (*_flow)[e]; 589 674 u = _graph.target(e); 590 675 } … … 594 679 while ((e = _pred[u]) != INVALID) { 595 680 if (u == _graph.target(e)) { 596 _flow[e] += d;681 (*_flow)[e] += d; 597 682 _res_cap[e] = d; 598 683 u = _graph.source(e); 599 684 } else { 600 _flow[e] = d;685 (*_flow)[e] = d; 601 686 _res_cap[e] += d; 602 687 u = _graph.target(e); … … 610 695 if (_lower) { 611 696 for (EdgeIt e(_graph); e != INVALID; ++e) 612 _flow[e] += (*_lower)[e];697 (*_flow)[e] += (*_lower)[e]; 613 698 } 614 699 return true; 
lemon/cost_scaling.h
r2577 r2581 55 55 ///  Edge capacities and costs should be \e nonnegative \e integers. 56 56 ///  Supply values should be \e signed \e integers. 57 ///  \c LowerMap::Value must be convertible to \c CapacityMap::Value. 58 ///  \c CapacityMap::Value and \c SupplyMap::Value must be 59 /// convertible to each other. 60 ///  All value types must be convertible to \c CostMap::Value, which 61 /// must be signed type. 57 ///  The value types of the maps should be convertible to each other. 58 ///  \c CostMap::Value must be signed type. 62 59 /// 63 60 /// \note Edge costs are multiplied with the number of nodes during … … 98 95 99 96 /// The type of the flow map. 100 typedef CapacityEdgeMapFlowMap;97 typedef typename Graph::template EdgeMap<Capacity> FlowMap; 101 98 /// The type of the potential map. 102 99 typedef typename Graph::template NodeMap<LCost> PotentialMap; … … 108 105 /// \ref ResidualCostMap is a map adaptor class for handling 109 106 /// residual edge costs. 110 class ResidualCostMap : public MapBase<ResEdge, LCost> 107 template <typename Map> 108 class ResidualCostMap : public MapBase<ResEdge, typename Map::Value> 111 109 { 112 110 private: 113 111 114 const LargeCostMap &_cost_map;112 const Map &_cost_map; 115 113 116 114 public: 117 115 118 116 ///\e 119 ResidualCostMap(const LargeCostMap &cost_map) :117 ResidualCostMap(const Map &cost_map) : 120 118 _cost_map(cost_map) {} 121 119 122 120 ///\e 123 LCostoperator[](const ResEdge &e) const {121 typename Map::Value operator[](const ResEdge &e) const { 124 122 return ResGraph::forward(e) ? _cost_map[e] : _cost_map[e]; 125 123 } … … 161 159 162 160 // Paramters for heuristics 163 static const int BF_HEURISTIC_EPSILON_BOUND 164 static const int BF_HEURISTIC_BOUND_FACTOR = 3;161 static const int BF_HEURISTIC_EPSILON_BOUND = 5000; 162 static const int BF_HEURISTIC_BOUND_FACTOR = 3; 165 163 166 164 private: … … 181 179 182 180 // Edge map of the current flow 183 FlowMap _flow; 181 FlowMap *_flow; 182 bool _local_flow; 184 183 // Node map of the current potentials 185 PotentialMap _potential; 184 PotentialMap *_potential; 185 bool _local_potential; 186 186 187 187 // The residual graph 188 ResGraph _res_graph;188 ResGraph *_res_graph; 189 189 // The residual cost map 190 ResidualCostMap _res_cost;190 ResidualCostMap<LargeCostMap> _res_cost; 191 191 // The reduced cost map 192 ReducedCostMap _red_cost;192 ReducedCostMap *_red_cost; 193 193 // The excess map 194 194 SupplyNodeMap _excess; … … 198 198 public: 199 199 200 /// \brief General constructor of the class(with lower bounds).201 /// 202 /// General constructor of the class(with lower bounds).200 /// \brief General constructor (with lower bounds). 201 /// 202 /// General constructor (with lower bounds). 203 203 /// 204 204 /// \param graph The directed graph the algorithm runs on. … … 213 213 const SupplyMap &supply ) : 214 214 _graph(graph), _lower(&lower), _capacity(graph), _orig_cost(cost), 215 _cost(graph), _supply(graph), _flow( graph, 0), _potential(graph, 0),216 _ res_graph(graph, _capacity, _flow), _res_cost(_cost),217 _ red_cost(graph, _cost, _potential), _excess(graph, 0)215 _cost(graph), _supply(graph), _flow(0), _local_flow(false), 216 _potential(0), _local_potential(false), _res_cost(_cost), 217 _excess(graph, 0) 218 218 { 219 219 // Removing nonzero lower bounds … … 232 232 } 233 233 234 /// \brief General constructor of the class(without lower bounds).235 /// 236 /// General constructor of the class(without lower bounds).234 /// \brief General constructor (without lower bounds). 235 /// 236 /// General constructor (without lower bounds). 237 237 /// 238 238 /// \param graph The directed graph the algorithm runs on. … … 245 245 const SupplyMap &supply ) : 246 246 _graph(graph), _lower(NULL), _capacity(capacity), _orig_cost(cost), 247 _cost(graph), _supply(supply), _flow( graph, 0), _potential(graph, 0),248 _ res_graph(graph, _capacity, _flow), _res_cost(_cost),249 _ red_cost(graph, _cost, _potential), _excess(graph, 0)247 _cost(graph), _supply(supply), _flow(0), _local_flow(false), 248 _potential(0), _local_potential(false), _res_cost(_cost), 249 _excess(graph, 0) 250 250 { 251 251 // Checking the sum of supply values … … 255 255 } 256 256 257 /// \brief Simple constructor of the class(with lower bounds).258 /// 259 /// Simple constructor of the class(with lower bounds).257 /// \brief Simple constructor (with lower bounds). 258 /// 259 /// Simple constructor (with lower bounds). 260 260 /// 261 261 /// \param graph The directed graph the algorithm runs on. … … 274 274 Supply flow_value ) : 275 275 _graph(graph), _lower(&lower), _capacity(graph), _orig_cost(cost), 276 _cost(graph), _supply(graph), _flow( graph, 0), _potential(graph, 0),277 _ res_graph(graph, _capacity, _flow), _res_cost(_cost),278 _ red_cost(graph, _cost, _potential), _excess(graph, 0)276 _cost(graph), _supply(graph), _flow(0), _local_flow(false), 277 _potential(0), _local_potential(false), _res_cost(_cost), 278 _excess(graph, 0) 279 279 { 280 280 // Removing nonzero lower bounds … … 293 293 } 294 294 295 /// \brief Simple constructor of the class(without lower bounds).296 /// 297 /// Simple constructor of the class(without lower bounds).295 /// \brief Simple constructor (without lower bounds). 296 /// 297 /// Simple constructor (without lower bounds). 298 298 /// 299 299 /// \param graph The directed graph the algorithm runs on. … … 310 310 Supply flow_value ) : 311 311 _graph(graph), _lower(NULL), _capacity(capacity), _orig_cost(cost), 312 _cost(graph), _supply(graph, 0), _flow( graph, 0), _potential(graph, 0),313 _ res_graph(graph, _capacity, _flow), _res_cost(_cost),314 _ red_cost(graph, _cost, _potential), _excess(graph, 0)312 _cost(graph), _supply(graph, 0), _flow(0), _local_flow(false), 313 _potential(0), _local_potential(false), _res_cost(_cost), 314 _excess(graph, 0) 315 315 { 316 316 _supply[s] = flow_value; … … 319 319 } 320 320 321 /// Destructor. 322 ~CostScaling() { 323 if (_local_flow) delete _flow; 324 if (_local_potential) delete _potential; 325 delete _res_graph; 326 delete _red_cost; 327 } 328 329 /// \brief Sets the flow map. 330 /// 331 /// Sets the flow map. 332 /// 333 /// \return \c (*this) 334 CostScaling& flowMap(FlowMap &map) { 335 if (_local_flow) { 336 delete _flow; 337 _local_flow = false; 338 } 339 _flow = ↦ 340 return *this; 341 } 342 343 /// \brief Sets the potential map. 344 /// 345 /// Sets the potential map. 346 /// 347 /// \return \c (*this) 348 CostScaling& potentialMap(PotentialMap &map) { 349 if (_local_potential) { 350 delete _potential; 351 _local_potential = false; 352 } 353 _potential = ↦ 354 return *this; 355 } 356 357 /// \name Execution control 358 /// The only way to execute the algorithm is to call the run() 359 /// function. 360 361 /// @{ 362 321 363 /// \brief Runs the algorithm. 322 364 /// … … 325 367 /// \return \c true if a feasible flow can be found. 326 368 bool run() { 327 init() && start(); 328 } 369 return init() && start(); 370 } 371 372 /// @} 373 374 /// \name Query Functions 375 /// The result of the algorithm can be obtained using these 376 /// functions. 377 /// \n run() must be called before using them. 378 379 /// @{ 329 380 330 381 /// \brief Returns a const reference to the edge map storing the … … 335 386 /// \pre \ref run() must be called before using this function. 336 387 const FlowMap& flowMap() const { 337 return _flow;388 return *_flow; 338 389 } 339 390 … … 346 397 /// \pre \ref run() must be called before using this function. 347 398 const PotentialMap& potentialMap() const { 348 return _potential; 399 return *_potential; 400 } 401 402 /// \brief Returns the flow on the edge. 403 /// 404 /// Returns the flow on the edge. 405 /// 406 /// \pre \ref run() must be called before using this function. 407 Capacity flow(const Edge& edge) const { 408 return (*_flow)[edge]; 409 } 410 411 /// \brief Returns the potential of the node. 412 /// 413 /// Returns the potential of the node. 414 /// 415 /// \pre \ref run() must be called before using this function. 416 Cost potential(const Node& node) const { 417 return (*_potential)[node]; 349 418 } 350 419 … … 358 427 Cost c = 0; 359 428 for (EdgeIt e(_graph); e != INVALID; ++e) 360 c += _flow[e] * _orig_cost[e];429 c += (*_flow)[e] * _orig_cost[e]; 361 430 return c; 362 431 } 432 433 /// @} 363 434 364 435 private: … … 367 438 bool init() { 368 439 if (!_valid_supply) return false; 440 441 // Initializing flow and potential maps 442 if (!_flow) { 443 _flow = new FlowMap(_graph); 444 _local_flow = true; 445 } 446 if (!_potential) { 447 _potential = new PotentialMap(_graph); 448 _local_potential = true; 449 } 450 451 _red_cost = new ReducedCostMap(_graph, _cost, *_potential); 452 _res_graph = new ResGraph(_graph, _capacity, *_flow); 369 453 370 454 // Initializing the scaled cost map and the epsilon parameter … … 380 464 Circulation< Graph, ConstMap<Edge, Capacity>, CapacityEdgeMap, 381 465 SupplyMap > 382 circulation( _graph, constMap<Edge>( (Capacity)0), _capacity,466 circulation( _graph, constMap<Edge>(Capacity(0)), _capacity, 383 467 _supply ); 384 return circulation.flowMap( _flow).run();468 return circulation.flowMap(*_flow).run(); 385 469 } 386 470 … … 398 482 // algorithm 399 483 if (_epsilon <= BF_HEURISTIC_EPSILON_BOUND) { 400 typedef ShiftMap< ResidualCostMap> ShiftCostMap;484 typedef ShiftMap< ResidualCostMap<LargeCostMap> > ShiftCostMap; 401 485 ShiftCostMap shift_cost(_res_cost, _epsilon); 402 BellmanFord<ResGraph, ShiftCostMap> bf( _res_graph, shift_cost);486 BellmanFord<ResGraph, ShiftCostMap> bf(*_res_graph, shift_cost); 403 487 bf.init(0); 404 488 bool done = false; … … 408 492 if (done) { 409 493 for (NodeIt n(_graph); n != INVALID; ++n) 410 _potential[n] = bf.dist(n);494 (*_potential)[n] = bf.dist(n); 411 495 continue; 412 496 } … … 416 500 Capacity delta; 417 501 for (EdgeIt e(_graph); e != INVALID; ++e) { 418 if (_capacity[e]  _flow[e] > 0 && _red_cost[e] < 0) {419 delta = _capacity[e]  _flow[e];502 if (_capacity[e]  (*_flow)[e] > 0 && (*_red_cost)[e] < 0) { 503 delta = _capacity[e]  (*_flow)[e]; 420 504 _excess[_graph.source(e)] = delta; 421 505 _excess[_graph.target(e)] += delta; 422 _flow[e] = _capacity[e];506 (*_flow)[e] = _capacity[e]; 423 507 } 424 if ( _flow[e] > 0 && _red_cost[e] < 0) {425 _excess[_graph.target(e)] = _flow[e];426 _excess[_graph.source(e)] += _flow[e];427 _flow[e] = 0;508 if ((*_flow)[e] > 0 && (*_red_cost)[e] < 0) { 509 _excess[_graph.target(e)] = (*_flow)[e]; 510 _excess[_graph.source(e)] += (*_flow)[e]; 511 (*_flow)[e] = 0; 428 512 } 429 513 } … … 441 525 if (_excess[n] > 0) { 442 526 for (OutEdgeIt e(_graph, n); e != INVALID; ++e) { 443 if (_capacity[e]  _flow[e] > 0 && _red_cost[e] < 0) {444 delta = _capacity[e]  _flow[e] <= _excess[n] ?445 _capacity[e]  _flow[e] : _excess[n];527 if (_capacity[e]  (*_flow)[e] > 0 && (*_red_cost)[e] < 0) { 528 delta = _capacity[e]  (*_flow)[e] <= _excess[n] ? 529 _capacity[e]  (*_flow)[e] : _excess[n]; 446 530 t = _graph.target(e); 447 531 … … 449 533 Capacity ahead = _excess[t]; 450 534 for (OutEdgeIt oe(_graph, t); oe != INVALID; ++oe) { 451 if (_capacity[oe]  _flow[oe] > 0 && _red_cost[oe] < 0)452 ahead += _capacity[oe]  _flow[oe];535 if (_capacity[oe]  (*_flow)[oe] > 0 && (*_red_cost)[oe] < 0) 536 ahead += _capacity[oe]  (*_flow)[oe]; 453 537 } 454 538 for (InEdgeIt ie(_graph, t); ie != INVALID; ++ie) { 455 if ( _flow[ie] > 0 && _red_cost[ie] < 0)456 ahead += _flow[ie];539 if ((*_flow)[ie] > 0 && (*_red_cost)[ie] < 0) 540 ahead += (*_flow)[ie]; 457 541 } 458 542 if (ahead < 0) ahead = 0; … … 460 544 // Pushing flow along the edge 461 545 if (ahead < delta) { 462 _flow[e] += ahead;546 (*_flow)[e] += ahead; 463 547 _excess[n] = ahead; 464 548 _excess[t] += ahead; … … 468 552 break; 469 553 } else { 470 _flow[e] += delta;554 (*_flow)[e] += delta; 471 555 _excess[n] = delta; 472 556 _excess[t] += delta; … … 482 566 if (_excess[n] > 0) { 483 567 for (InEdgeIt e(_graph, n); e != INVALID; ++e) { 484 if ( _flow[e] > 0 && _red_cost[e] < 0) {485 delta = _flow[e] <= _excess[n] ? _flow[e] : _excess[n];568 if ((*_flow)[e] > 0 && (*_red_cost)[e] < 0) { 569 delta = (*_flow)[e] <= _excess[n] ? (*_flow)[e] : _excess[n]; 486 570 t = _graph.source(e); 487 571 … … 489 573 Capacity ahead = _excess[t]; 490 574 for (OutEdgeIt oe(_graph, t); oe != INVALID; ++oe) { 491 if (_capacity[oe]  _flow[oe] > 0 && _red_cost[oe] < 0)492 ahead += _capacity[oe]  _flow[oe];575 if (_capacity[oe]  (*_flow)[oe] > 0 && (*_red_cost)[oe] < 0) 576 ahead += _capacity[oe]  (*_flow)[oe]; 493 577 } 494 578 for (InEdgeIt ie(_graph, t); ie != INVALID; ++ie) { 495 if ( _flow[ie] > 0 && _red_cost[ie] < 0)496 ahead += _flow[ie];579 if ((*_flow)[ie] > 0 && (*_red_cost)[ie] < 0) 580 ahead += (*_flow)[ie]; 497 581 } 498 582 if (ahead < 0) ahead = 0; … … 500 584 // Pushing flow along the edge 501 585 if (ahead < delta) { 502 _flow[e] = ahead;586 (*_flow)[e] = ahead; 503 587 _excess[n] = ahead; 504 588 _excess[t] += ahead; … … 508 592 break; 509 593 } else { 510 _flow[e] = delta;594 (*_flow)[e] = delta; 511 595 _excess[n] = delta; 512 596 _excess[t] += delta; … … 524 608 LCost min_red_cost = std::numeric_limits<LCost>::max(); 525 609 for (OutEdgeIt oe(_graph, n); oe != INVALID; ++oe) { 526 if ( _capacity[oe]  _flow[oe] > 0 &&527 _red_cost[oe] < min_red_cost )528 min_red_cost = _red_cost[oe];610 if ( _capacity[oe]  (*_flow)[oe] > 0 && 611 (*_red_cost)[oe] < min_red_cost ) 612 min_red_cost = (*_red_cost)[oe]; 529 613 } 530 614 for (InEdgeIt ie(_graph, n); ie != INVALID; ++ie) { 531 if ( _flow[ie] > 0 && _red_cost[ie] < min_red_cost)532 min_red_cost =  _red_cost[ie];615 if ((*_flow)[ie] > 0 && (*_red_cost)[ie] < min_red_cost) 616 min_red_cost = (*_red_cost)[ie]; 533 617 } 534 _potential[n] = min_red_cost + _epsilon;618 (*_potential)[n] = min_red_cost + _epsilon; 535 619 hyper[n] = false; 536 620 } … … 545 629 } 546 630 631 // Computing node potentials for the original costs 632 ResidualCostMap<CostMap> res_cost(_orig_cost); 633 BellmanFord< ResGraph, ResidualCostMap<CostMap> > 634 bf(*_res_graph, res_cost); 635 bf.init(0); bf.start(); 636 for (NodeIt n(_graph); n != INVALID; ++n) 637 (*_potential)[n] = bf.dist(n); 638 547 639 // Handling nonzero lower bounds 548 640 if (_lower) { 549 641 for (EdgeIt e(_graph); e != INVALID; ++e) 550 _flow[e] += (*_lower)[e];642 (*_flow)[e] += (*_lower)[e]; 551 643 } 552 644 return true; 
lemon/cycle_canceling.h
r2573 r2581 53 53 ///  Edge capacities and costs should be \e nonnegative \e integers. 54 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. 55 ///  The value types of the maps should be convertible to each other. 56 ///  \c CostMap::Value must be signed type. 60 57 /// 61 58 /// \note By default the \ref BellmanFord "BellmanFord" algorithm is … … 95 92 /// The type of the flow map. 96 93 typedef typename Graph::template EdgeMap<Capacity> FlowMap; 94 /// The type of the potential map. 95 typedef typename Graph::template NodeMap<Cost> PotentialMap; 97 96 98 97 private: … … 144 143 145 144 // Edge map of the current flow 146 FlowMap _flow; 145 FlowMap *_flow; 146 bool _local_flow; 147 // Node map of the current potentials 148 PotentialMap *_potential; 149 bool _local_potential; 147 150 148 151 // The residual graph 149 ResGraph _res_graph;152 ResGraph *_res_graph; 150 153 // The residual cost map 151 154 ResidualCostMap _res_cost; … … 153 156 public: 154 157 155 /// \brief General constructor of the class(with lower bounds).156 /// 157 /// General constructor of the class(with lower bounds).158 /// \brief General constructor (with lower bounds). 159 /// 160 /// General constructor (with lower bounds). 158 161 /// 159 162 /// \param graph The directed graph the algorithm runs on. … … 168 171 const SupplyMap &supply ) : 169 172 _graph(graph), _lower(&lower), _capacity(graph), _cost(cost), 170 _supply(graph), _flow( graph, 0),171 _ res_graph(graph, _capacity, _flow), _res_cost(_cost)173 _supply(graph), _flow(0), _local_flow(false), 174 _potential(0), _local_potential(false), _res_cost(_cost) 172 175 { 173 176 // Removing nonzero lower bounds … … 185 188 } 186 189 187 /// \brief General constructor of the class(without lower bounds).188 /// 189 /// General constructor of the class(without lower bounds).190 /// \brief General constructor (without lower bounds). 191 /// 192 /// General constructor (without lower bounds). 190 193 /// 191 194 /// \param graph The directed graph the algorithm runs on. … … 198 201 const SupplyMap &supply ) : 199 202 _graph(graph), _lower(NULL), _capacity(capacity), _cost(cost), 200 _supply(supply), _flow( graph, 0),201 _ res_graph(graph, _capacity, _flow), _res_cost(_cost)203 _supply(supply), _flow(0), _local_flow(false), 204 _potential(0), _local_potential(false), _res_cost(_cost) 202 205 { 203 206 // Checking the sum of supply values … … 207 210 } 208 211 209 /// \brief Simple constructor of the class(with lower bounds).210 /// 211 /// Simple constructor of the class(with lower bounds).212 /// \brief Simple constructor (with lower bounds). 213 /// 214 /// Simple constructor (with lower bounds). 212 215 /// 213 216 /// \param graph The directed graph the algorithm runs on. … … 226 229 Supply flow_value ) : 227 230 _graph(graph), _lower(&lower), _capacity(graph), _cost(cost), 228 _supply(graph), _flow( graph, 0),229 _ res_graph(graph, _capacity, _flow), _res_cost(_cost)231 _supply(graph), _flow(0), _local_flow(false), 232 _potential(0), _local_potential(false), _res_cost(_cost) 230 233 { 231 234 // Removing nonzero lower bounds … … 244 247 } 245 248 246 /// \brief Simple constructor of the class(without lower bounds).247 /// 248 /// Simple constructor of the class(without lower bounds).249 /// \brief Simple constructor (without lower bounds). 250 /// 251 /// Simple constructor (without lower bounds). 249 252 /// 250 253 /// \param graph The directed graph the algorithm runs on. … … 261 264 Supply flow_value ) : 262 265 _graph(graph), _lower(NULL), _capacity(capacity), _cost(cost), 263 _supply(graph, 0), _flow( graph, 0),264 _ res_graph(graph, _capacity, _flow), _res_cost(_cost)266 _supply(graph, 0), _flow(0), _local_flow(false), 267 _potential(0), _local_potential(false), _res_cost(_cost) 265 268 { 266 269 _supply[s] = flow_value; … … 269 272 } 270 273 274 /// Destructor. 275 ~CycleCanceling() { 276 if (_local_flow) delete _flow; 277 if (_local_potential) delete _potential; 278 delete _res_graph; 279 } 280 281 /// \brief Sets the flow map. 282 /// 283 /// Sets the flow map. 284 /// 285 /// \return \c (*this) 286 CycleCanceling& flowMap(FlowMap &map) { 287 if (_local_flow) { 288 delete _flow; 289 _local_flow = false; 290 } 291 _flow = ↦ 292 return *this; 293 } 294 295 /// \brief Sets the potential map. 296 /// 297 /// Sets the potential map. 298 /// 299 /// \return \c (*this) 300 CycleCanceling& potentialMap(PotentialMap &map) { 301 if (_local_potential) { 302 delete _potential; 303 _local_potential = false; 304 } 305 _potential = ↦ 306 return *this; 307 } 308 309 /// \name Execution control 310 /// The only way to execute the algorithm is to call the run() 311 /// function. 312 313 /// @{ 314 271 315 /// \brief Runs the algorithm. 272 316 /// … … 282 326 } 283 327 328 /// @} 329 330 /// \name Query Functions 331 /// The result of the algorithm can be obtained using these 332 /// functions. 333 /// \n run() must be called before using them. 334 335 /// @{ 336 284 337 /// \brief Returns a const reference to the edge map storing the 285 338 /// found flow. … … 289 342 /// \pre \ref run() must be called before using this function. 290 343 const FlowMap& flowMap() const { 291 return _flow; 344 return *_flow; 345 } 346 347 /// \brief Returns a const reference to the node map storing the 348 /// found potentials (the dual solution). 349 /// 350 /// Returns a const reference to the node map storing the found 351 /// potentials (the dual solution). 352 /// 353 /// \pre \ref run() must be called before using this function. 354 const PotentialMap& potentialMap() const { 355 return *_potential; 356 } 357 358 /// \brief Returns the flow on the edge. 359 /// 360 /// Returns the flow on the edge. 361 /// 362 /// \pre \ref run() must be called before using this function. 363 Capacity flow(const Edge& edge) const { 364 return (*_flow)[edge]; 365 } 366 367 /// \brief Returns the potential of the node. 368 /// 369 /// Returns the potential of the node. 370 /// 371 /// \pre \ref run() must be called before using this function. 372 Cost potential(const Node& node) const { 373 return (*_potential)[node]; 292 374 } 293 375 … … 301 383 Cost c = 0; 302 384 for (EdgeIt e(_graph); e != INVALID; ++e) 303 c += _flow[e] * _cost[e];385 c += (*_flow)[e] * _cost[e]; 304 386 return c; 305 387 } 388 389 /// @} 306 390 307 391 private: … … 311 395 if (!_valid_supply) return false; 312 396 397 // Initializing flow and potential maps 398 if (!_flow) { 399 _flow = new FlowMap(_graph); 400 _local_flow = true; 401 } 402 if (!_potential) { 403 _potential = new PotentialMap(_graph); 404 _local_potential = true; 405 } 406 407 _res_graph = new ResGraph(_graph, _capacity, *_flow); 408 313 409 // Finding a feasible flow using Circulation 314 410 Circulation< Graph, ConstMap<Edge, Capacity>, CapacityEdgeMap, 315 411 SupplyMap > 316 circulation( _graph, constMap<Edge>( (Capacity)0), _capacity,412 circulation( _graph, constMap<Edge>(Capacity(0)), _capacity, 317 413 _supply ); 318 return circulation.flowMap( _flow).run();414 return circulation.flowMap(*_flow).run(); 319 415 } 320 416 321 417 bool start(bool min_mean_cc) { 322 418 if (min_mean_cc) 323 returnstartMinMean();419 startMinMean(); 324 420 else 325 return start(); 421 start(); 422 423 // Handling nonzero lower bounds 424 if (_lower) { 425 for (EdgeIt e(_graph); e != INVALID; ++e) 426 (*_flow)[e] += (*_lower)[e]; 427 } 428 return true; 326 429 } 327 430 … … 331 434 /// "BellmanFord" algorithm for negative cycle detection with 332 435 /// successively larger limit for the number of iterations. 333 boolstart() {334 typename BellmanFord<ResGraph, ResidualCostMap>::PredMap pred( _res_graph);335 typename ResGraph::template NodeMap<int> visited( _res_graph);436 void start() { 437 typename BellmanFord<ResGraph, ResidualCostMap>::PredMap pred(*_res_graph); 438 typename ResGraph::template NodeMap<int> visited(*_res_graph); 336 439 std::vector<ResEdge> cycle; 337 440 int node_num = countNodes(_graph); … … 340 443 bool optimal = false; 341 444 while (!optimal) { 342 BellmanFord<ResGraph, ResidualCostMap> bf( _res_graph, _res_cost);445 BellmanFord<ResGraph, ResidualCostMap> bf(*_res_graph, _res_cost); 343 446 bf.predMap(pred); 344 447 bf.init(0); … … 357 460 } 358 461 if (real_iter_num < curr_iter_num) { 462 // Optimal flow is found 359 463 optimal = true; 464 // Setting node potentials 465 for (NodeIt n(_graph); n != INVALID; ++n) 466 (*_potential)[n] = bf.dist(n); 360 467 break; 361 468 } else { 362 469 // Searching for node disjoint negative cycles 363 for (ResNodeIt n( _res_graph); n != INVALID; ++n)470 for (ResNodeIt n(*_res_graph); n != INVALID; ++n) 364 471 visited[n] = 0; 365 472 int id = 0; 366 for (ResNodeIt n( _res_graph); n != INVALID; ++n) {473 for (ResNodeIt n(*_res_graph); n != INVALID; ++n) { 367 474 if (visited[n] > 0) continue; 368 475 visited[n] = ++id; 369 476 ResNode u = pred[n] == INVALID ? 370 INVALID : _res_graph .source(pred[n]);477 INVALID : _res_graph>source(pred[n]); 371 478 while (u != INVALID && visited[u] == 0) { 372 479 visited[u] = id; 373 480 u = pred[u] == INVALID ? 374 INVALID : _res_graph .source(pred[u]);481 INVALID : _res_graph>source(pred[u]); 375 482 } 376 483 if (u != INVALID && visited[u] == id) { … … 380 487 ResEdge e = pred[u]; 381 488 cycle.push_back(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);489 Capacity d = _res_graph>rescap(e); 490 while (_res_graph>source(e) != u) { 491 cycle.push_back(e = pred[_res_graph>source(e)]); 492 if (_res_graph>rescap(e) < d) 493 d = _res_graph>rescap(e); 387 494 } 388 495 389 496 // Augmenting along the cycle 390 497 for (int i = 0; i < int(cycle.size()); ++i) 391 _res_graph .augment(cycle[i], d);498 _res_graph>augment(cycle[i], d); 392 499 } 393 500 } … … 398 505 } 399 506 } 400 401 // Handling nonzero lower bounds402 if (_lower) {403 for (EdgeIt e(_graph); e != INVALID; ++e)404 _flow[e] += (*_lower)[e];405 }406 return true;407 507 } 408 508 … … 411 511 /// Executes the algorithm using \ref MinMeanCycle for negative 412 512 /// cycle detection. 413 boolstartMinMean() {513 void startMinMean() { 414 514 typedef Path<ResGraph> ResPath; 415 MinMeanCycle<ResGraph, ResidualCostMap> mmc( _res_graph, _res_cost);515 MinMeanCycle<ResGraph, ResidualCostMap> mmc(*_res_graph, _res_cost); 416 516 ResPath cycle; 417 517 … … 426 526 Capacity delta = 0; 427 527 for (typename ResPath::EdgeIt e(cycle); e != INVALID; ++e) { 428 if (delta == 0  _res_graph .rescap(e) < delta)429 delta = _res_graph .rescap(e);528 if (delta == 0  _res_graph>rescap(e) < delta) 529 delta = _res_graph>rescap(e); 430 530 } 431 531 432 532 // Augmenting along the cycle 433 533 for (typename ResPath::EdgeIt e(cycle); e != INVALID; ++e) 434 _res_graph .augment(e, delta);534 _res_graph>augment(e, delta); 435 535 436 536 // Finding the minimum cycle mean for the modified residual … … 441 541 } 442 542 443 // Handling nonzero lower bounds 444 if (_lower) { 445 for (EdgeIt e(_graph); e != INVALID; ++e) 446 _flow[e] += (*_lower)[e]; 447 } 448 return true; 543 // Computing node potentials 544 BellmanFord<ResGraph, ResidualCostMap> bf(*_res_graph, _res_cost); 545 bf.init(0); bf.start(); 546 for (NodeIt n(_graph); n != INVALID; ++n) 547 (*_potential)[n] = bf.dist(n); 449 548 } 450 549 
lemon/min_cost_flow.h
r2579 r2581 44 44 /// 45 45 /// There are four implementations for the minimum cost flow problem, 46 /// which can be used exactly the same way except for the fact that 47 /// \ref CycleCanceling does not provide dual solution (node 48 /// potentials) since it is a pure primal method. 46 /// which can be used exactly the same way. 49 47 ///  \ref CapacityScaling The capacity scaling algorithm. 50 48 ///  \ref CostScaling The cost scaling algorithm. … … 61 59 ///  Edge capacities and costs should be \e nonnegative \e integers. 62 60 ///  Supply values should be \e signed \e integers. 63 ///  \c LowerMap::Value must be convertible to \c CapacityMap::Value. 64 ///  \c CapacityMap::Value and \c SupplyMap::Value must be 65 /// convertible to each other. 66 ///  All value types must be convertible to \c CostMap::Value, which 67 /// must be signed type. 61 ///  The value types of the maps should be convertible to each other. 62 ///  \c CostMap::Value must be signed type. 68 63 /// 69 64 /// \author Peter Kovacs … … 71 66 template < typename Graph, 72 67 typename LowerMap = typename Graph::template EdgeMap<int>, 73 typename CapacityMap = LowerMap,68 typename CapacityMap = typename Graph::template EdgeMap<int>, 74 69 typename CostMap = typename Graph::template EdgeMap<int>, 75 typename SupplyMap = typename Graph::template NodeMap 76 <typename CapacityMap::Value> > 70 typename SupplyMap = typename Graph::template NodeMap<int> > 77 71 class MinCostFlow : 78 72 public NetworkSimplex< Graph, LowerMap, CapacityMap, … … 86 80 public: 87 81 88 /// General constructor of the class(with lower bounds).82 /// General constructor (with lower bounds). 89 83 MinCostFlow( const Graph &graph, 90 84 const LowerMap &lower, … … 101 95 MinCostFlowImpl(graph, capacity, cost, supply) {} 102 96 103 /// Simple constructor of the class(with lower bounds).97 /// Simple constructor (with lower bounds). 104 98 MinCostFlow( const Graph &graph, 105 99 const LowerMap &lower, … … 111 105 s, t, flow_value ) {} 112 106 113 /// Simple constructor of the class(without lower bounds).107 /// Simple constructor (without lower bounds). 114 108 MinCostFlow( const Graph &graph, 115 109 const CapacityMap &capacity, 
lemon/network_simplex.h
r2579 r2581 53 53 ///  Edge capacities and costs should be \e nonnegative \e integers. 54 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. 55 ///  The value types of the maps should be convertible to each other. 56 ///  \c CostMap::Value must be signed type. 60 57 /// 61 58 /// \note \ref NetworkSimplex provides six different pivot rule … … 470 467 471 468 // Members for handling the original graph 472 FlowMap _flow_result; 473 PotentialMap _potential_result; 469 FlowMap *_flow_result; 470 PotentialMap *_potential_result; 471 bool _local_flow; 472 bool _local_potential; 474 473 NodeRefMap _node_ref; 475 474 EdgeRefMap _edge_ref; … … 488 487 public : 489 488 490 /// \brief General constructor of the class(with lower bounds).491 /// 492 /// General constructor of the class(with lower bounds).489 /// \brief General constructor (with lower bounds). 490 /// 491 /// General constructor (with lower bounds). 493 492 /// 494 493 /// \param graph The directed graph the algorithm runs on. … … 507 506 _pred_edge(_graph), _thread(_graph), _forward(_graph), 508 507 _state(_graph), _red_cost(_graph, _cost, _potential), 509 _flow_result(graph), _potential_result(graph), 508 _flow_result(0), _potential_result(0), 509 _local_flow(false), _local_potential(false), 510 510 _node_ref(graph), _edge_ref(graph) 511 511 { … … 539 539 } 540 540 541 /// \brief General constructor of the class(without lower bounds).542 /// 543 /// General constructor of the class(without lower bounds).541 /// \brief General constructor (without lower bounds). 542 /// 543 /// General constructor (without lower bounds). 544 544 /// 545 545 /// \param graph The directed graph the algorithm runs on. … … 556 556 _pred_edge(_graph), _thread(_graph), _forward(_graph), 557 557 _state(_graph), _red_cost(_graph, _cost, _potential), 558 _flow_result(graph), _potential_result(graph), 558 _flow_result(0), _potential_result(0), 559 _local_flow(false), _local_potential(false), 559 560 _node_ref(graph), _edge_ref(graph) 560 561 { … … 575 576 } 576 577 577 /// \brief Simple constructor of the class(with lower bounds).578 /// 579 /// Simple constructor of the class(with lower bounds).578 /// \brief Simple constructor (with lower bounds). 579 /// 580 /// Simple constructor (with lower bounds). 580 581 /// 581 582 /// \param graph The directed graph the algorithm runs on. … … 599 600 _pred_edge(_graph), _thread(_graph), _forward(_graph), 600 601 _state(_graph), _red_cost(_graph, _cost, _potential), 601 _flow_result(graph), _potential_result(graph), 602 _flow_result(0), _potential_result(0), 603 _local_flow(false), _local_potential(false), 602 604 _node_ref(graph), _edge_ref(graph) 603 605 { … … 626 628 } 627 629 628 /// \brief Simple constructor of the class(without lower bounds).629 /// 630 /// Simple constructor of the class(without lower bounds).630 /// \brief Simple constructor (without lower bounds). 631 /// 632 /// Simple constructor (without lower bounds). 631 633 /// 632 634 /// \param graph The directed graph the algorithm runs on. … … 648 650 _pred_edge(_graph), _thread(_graph), _forward(_graph), 649 651 _state(_graph), _red_cost(_graph, _cost, _potential), 650 _flow_result(graph), _potential_result(graph), 652 _flow_result(0), _potential_result(0), 653 _local_flow(false), _local_potential(false), 651 654 _node_ref(graph), _edge_ref(graph) 652 655 { … … 663 666 } 664 667 668 /// Destructor. 669 ~NetworkSimplex() { 670 if (_local_flow) delete _flow_result; 671 if (_local_potential) delete _potential_result; 672 } 673 674 /// \brief Sets the flow map. 675 /// 676 /// Sets the flow map. 677 /// 678 /// \return \c (*this) 679 NetworkSimplex& flowMap(FlowMap &map) { 680 if (_local_flow) { 681 delete _flow_result; 682 _local_flow = false; 683 } 684 _flow_result = ↦ 685 return *this; 686 } 687 688 /// \brief Sets the potential map. 689 /// 690 /// Sets the potential map. 691 /// 692 /// \return \c (*this) 693 NetworkSimplex& potentialMap(PotentialMap &map) { 694 if (_local_potential) { 695 delete _potential_result; 696 _local_potential = false; 697 } 698 _potential_result = ↦ 699 return *this; 700 } 701 702 /// \name Execution control 703 /// The only way to execute the algorithm is to call the run() 704 /// function. 705 706 /// @{ 707 665 708 /// \brief Runs the algorithm. 666 709 /// … … 704 747 } 705 748 749 /// @} 750 751 /// \name Query Functions 752 /// The result of the algorithm can be obtained using these 753 /// functions. 754 /// \n run() must be called before using them. 755 756 /// @{ 757 706 758 /// \brief Returns a const reference to the edge map storing the 707 759 /// found flow. … … 711 763 /// \pre \ref run() must be called before using this function. 712 764 const FlowMap& flowMap() const { 713 return _flow_result;765 return *_flow_result; 714 766 } 715 767 … … 722 774 /// \pre \ref run() must be called before using this function. 723 775 const PotentialMap& potentialMap() const { 724 return _potential_result; 776 return *_potential_result; 777 } 778 779 /// \brief Returns the flow on the edge. 780 /// 781 /// Returns the flow on the edge. 782 /// 783 /// \pre \ref run() must be called before using this function. 784 Capacity flow(const typename Graph::Edge& edge) const { 785 return (*_flow_result)[edge]; 786 } 787 788 /// \brief Returns the potential of the node. 789 /// 790 /// Returns the potential of the node. 791 /// 792 /// \pre \ref run() must be called before using this function. 793 Cost potential(const typename Graph::Node& node) const { 794 return (*_potential_result)[node]; 725 795 } 726 796 … … 734 804 Cost c = 0; 735 805 for (typename Graph::EdgeIt e(_graph_ref); e != INVALID; ++e) 736 c += _flow_result[e] * _cost[_edge_ref[e]];806 c += (*_flow_result)[e] * _cost[_edge_ref[e]]; 737 807 return c; 738 808 } 809 810 /// @} 739 811 740 812 private: … … 744 816 bool init() { 745 817 if (!_valid_supply) return false; 818 819 // Initializing result maps 820 if (!_flow_result) { 821 _flow_result = new FlowMap(_graph_ref); 822 _local_flow = true; 823 } 824 if (!_potential_result) { 825 _potential_result = new PotentialMap(_graph_ref); 826 _local_potential = true; 827 } 746 828 747 829 // Initializing state and flow maps … … 1016 1098 if (_lower) { 1017 1099 for (typename Graph::EdgeIt e(_graph_ref); e != INVALID; ++e) 1018 _flow_result[e] = (*_lower)[e] + _flow[_edge_ref[e]];1100 (*_flow_result)[e] = (*_lower)[e] + _flow[_edge_ref[e]]; 1019 1101 } else { 1020 1102 for (typename Graph::EdgeIt e(_graph_ref); e != INVALID; ++e) 1021 _flow_result[e] = _flow[_edge_ref[e]];1103 (*_flow_result)[e] = _flow[_edge_ref[e]]; 1022 1104 } 1023 1105 // Copying potential values to _potential_result 1024 1106 for (typename Graph::NodeIt n(_graph_ref); n != INVALID; ++n) 1025 _potential_result[n] = _potential[_node_ref[n]];1107 (*_potential_result)[n] = _potential[_node_ref[n]]; 1026 1108 1027 1109 return true;
Note: See TracChangeset
for help on using the changeset viewer.