Changeset 2620:8f41a3129746 in lemon-0.x for lemon/capacity_scaling.h
- Timestamp:
- 10/05/08 15:37:17 (16 years ago)
- Branch:
- default
- Phase:
- public
- Convert:
- svn:c9d7d8f5-90d6-0310-b91f-818b3a526b0e/lemon/trunk@3505
- File:
-
- 1 edited
Legend:
- Unmodified
- Added
- Removed
-
lemon/capacity_scaling.h
r2589 r2620 53 53 /// 54 54 /// \author Peter Kovacs 55 56 55 template < typename Graph, 57 56 typename LowerMap = typename Graph::template EdgeMap<int>, … … 126 125 {} 127 126 128 /// Run sthe algorithm from the given source node.127 /// Run the algorithm from the given source node. 129 128 Node run(Node s, Capacity delta = 1) { 130 129 HeapCrossRef heap_cross_ref(_graph, Heap::PRE_HEAP); … … 372 371 } 373 372 374 /// \brief Set sthe flow map.375 /// 376 /// Set sthe flow map.373 /// \brief Set the flow map. 374 /// 375 /// Set the flow map. 377 376 /// 378 377 /// \return \c (*this) … … 386 385 } 387 386 388 /// \brief Set sthe potential map.389 /// 390 /// Set sthe potential map.387 /// \brief Set the potential map. 388 /// 389 /// Set the potential map. 391 390 /// 392 391 /// \return \c (*this) … … 401 400 402 401 /// \name Execution control 403 /// The only way to execute the algorithm is to call the run()404 /// function.405 402 406 403 /// @{ 407 404 408 /// \brief Run sthe algorithm.409 /// 410 /// Runs the algorithm.405 /// \brief Run the algorithm. 406 /// 407 /// This function runs the algorithm. 411 408 /// 412 409 /// \param scaling Enable or disable capacity scaling. … … 423 420 424 421 /// \name Query Functions 425 /// The result of the algorithm can be obtained using these 426 /// functions. 427 /// \n run() must be called before using them. 422 /// The results of the algorithm can be obtained using these 423 /// functions.\n 424 /// \ref lemon::CapacityScaling::run() "run()" must be called before 425 /// using them. 428 426 429 427 /// @{ 430 428 431 /// \brief Return sa const reference to the edge map storing the429 /// \brief Return a const reference to the edge map storing the 432 430 /// found flow. 433 431 /// 434 /// Return sa const reference to the edge map storing the found flow.432 /// Return a const reference to the edge map storing the found flow. 435 433 /// 436 434 /// \pre \ref run() must be called before using this function. … … 439 437 } 440 438 441 /// \brief Return sa const reference to the node map storing the439 /// \brief Return a const reference to the node map storing the 442 440 /// found potentials (the dual solution). 443 441 /// 444 /// Return sa const reference to the node map storing the found442 /// Return a const reference to the node map storing the found 445 443 /// potentials (the dual solution). 446 444 /// … … 450 448 } 451 449 452 /// \brief Return sthe flow on the given edge.453 /// 454 /// Return sthe flow on the given edge.450 /// \brief Return the flow on the given edge. 451 /// 452 /// Return the flow on the given edge. 455 453 /// 456 454 /// \pre \ref run() must be called before using this function. … … 459 457 } 460 458 461 /// \brief Return sthe potential of the given node.462 /// 463 /// Return sthe potential of the given node.459 /// \brief Return the potential of the given node. 460 /// 461 /// Return the potential of the given node. 464 462 /// 465 463 /// \pre \ref run() must be called before using this function. … … 468 466 } 469 467 470 /// \brief Return sthe total cost of the found flow.471 /// 472 /// Return sthe total cost of the found flow. The complexity of the468 /// \brief Return the total cost of the found flow. 469 /// 470 /// Return the total cost of the found flow. The complexity of the 473 471 /// function is \f$ O(e) \f$. 474 472 /// … … 485 483 private: 486 484 487 /// Initialize sthe algorithm.485 /// Initialize the algorithm. 488 486 bool init(bool scaling) { 489 487 if (!_valid_supply) return false; … … 536 534 } 537 535 538 /// Execute sthe capacity scaling algorithm.536 /// Execute the capacity scaling algorithm. 539 537 bool startWithScaling() { 540 538 // Processing capacity scaling phases … … 568 566 if (_excess[n] <= -_delta) _deficit_nodes.push_back(n); 569 567 } 570 int next_node = 0 ;568 int next_node = 0, next_def_node = 0; 571 569 572 570 // Finding augmenting shortest paths … … 575 573 if (_delta > 1) { 576 574 bool delta_deficit = false; 577 for (int i = 0; i < int(_deficit_nodes.size()); ++i) { 578 if (_excess[_deficit_nodes[i]] <= -_delta) { 575 for ( ; next_def_node < int(_deficit_nodes.size()); 576 ++next_def_node ) { 577 if (_excess[_deficit_nodes[next_def_node]] <= -_delta) { 579 578 delta_deficit = true; 580 579 break; … … 642 641 } 643 642 644 /// Execute sthe successive shortest path algorithm.643 /// Execute the successive shortest path algorithm. 645 644 bool startWithoutScaling() { 646 645 // Finding excess nodes
Note: See TracChangeset
for help on using the changeset viewer.