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

 1 edited
Legend:
 Unmodified
 Added
 Removed

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;
Note: See TracChangeset
for help on using the changeset viewer.