Changeset 611:85cb3aa71cce in lemon1.2 for lemon/preflow.h
 Timestamp:
 04/21/09 16:18:54 (11 years ago)
 Branch:
 default
 Children:
 612:0c8e5c688440, 613:b1811c363299, 619:ec817dfc2cb7
 Parents:
 600:0ba8dfce7259 (diff), 610:dacc2cee2b4c (diff)
Note: this is a merge changeset, the changes displayed below correspond to the merge itself.
Use the (diff) links above to see all the changes relative to each parent.  Phase:
 public
 Files:

 2 edited
Legend:
 Unmodified
 Added
 Removed

lemon/preflow.h
r581 r611 47 47 48 48 /// \brief The type of the flow values. 49 typedef typename CapacityMap::Value Value;49 typedef typename CapacityMap::Value Flow; 50 50 51 51 /// \brief The type of the map that stores the flow values. … … 53 53 /// The type of the map that stores the flow values. 54 54 /// It must meet the \ref concepts::ReadWriteMap "ReadWriteMap" concept. 55 typedef typename Digraph::template ArcMap< Value> FlowMap;55 typedef typename Digraph::template ArcMap<Flow> FlowMap; 56 56 57 57 /// \brief Instantiates a FlowMap. 58 58 /// 59 59 /// This function instantiates a \ref FlowMap. 60 /// \param digraph The digraph , towhich we would like to define60 /// \param digraph The digraph for which we would like to define 61 61 /// the flow map. 62 62 static FlowMap* createFlowMap(const Digraph& digraph) { … … 75 75 /// 76 76 /// This function instantiates an \ref Elevator. 77 /// \param digraph The digraph , towhich we would like to define77 /// \param digraph The digraph for which we would like to define 78 78 /// the elevator. 79 79 /// \param max_level The maximum level of the elevator. … … 85 85 /// 86 86 /// The tolerance used by the algorithm to handle inexact computation. 87 typedef lemon::Tolerance< Value> Tolerance;87 typedef lemon::Tolerance<Flow> Tolerance; 88 88 89 89 }; … … 126 126 typedef typename Traits::CapacityMap CapacityMap; 127 127 ///The type of the flow values. 128 typedef typename Traits:: Value Value;128 typedef typename Traits::Flow Flow; 129 129 130 130 ///The type of the flow map. … … 152 152 bool _local_level; 153 153 154 typedef typename Digraph::template NodeMap< Value> ExcessMap;154 typedef typename Digraph::template NodeMap<Flow> ExcessMap; 155 155 ExcessMap* _excess; 156 156 … … 471 471 472 472 for (NodeIt n(_graph); n != INVALID; ++n) { 473 Valueexcess = 0;473 Flow excess = 0; 474 474 for (InArcIt e(_graph, n); e != INVALID; ++e) { 475 475 excess += (*_flow)[e]; … … 520 520 521 521 for (OutArcIt e(_graph, _source); e != INVALID; ++e) { 522 Valuerem = (*_capacity)[e]  (*_flow)[e];522 Flow rem = (*_capacity)[e]  (*_flow)[e]; 523 523 if (_tolerance.positive(rem)) { 524 524 Node u = _graph.target(e); … … 532 532 } 533 533 for (InArcIt e(_graph, _source); e != INVALID; ++e) { 534 Valuerem = (*_flow)[e];534 Flow rem = (*_flow)[e]; 535 535 if (_tolerance.positive(rem)) { 536 536 Node v = _graph.source(e); … … 565 565 566 566 while (num > 0 && n != INVALID) { 567 Valueexcess = (*_excess)[n];567 Flow excess = (*_excess)[n]; 568 568 int new_level = _level>maxLevel(); 569 569 570 570 for (OutArcIt e(_graph, n); e != INVALID; ++e) { 571 Valuerem = (*_capacity)[e]  (*_flow)[e];571 Flow rem = (*_capacity)[e]  (*_flow)[e]; 572 572 if (!_tolerance.positive(rem)) continue; 573 573 Node v = _graph.target(e); … … 592 592 593 593 for (InArcIt e(_graph, n); e != INVALID; ++e) { 594 Valuerem = (*_flow)[e];594 Flow rem = (*_flow)[e]; 595 595 if (!_tolerance.positive(rem)) continue; 596 596 Node v = _graph.source(e); … … 638 638 num = _node_num * 20; 639 639 while (num > 0 && n != INVALID) { 640 Valueexcess = (*_excess)[n];640 Flow excess = (*_excess)[n]; 641 641 int new_level = _level>maxLevel(); 642 642 643 643 for (OutArcIt e(_graph, n); e != INVALID; ++e) { 644 Valuerem = (*_capacity)[e]  (*_flow)[e];644 Flow rem = (*_capacity)[e]  (*_flow)[e]; 645 645 if (!_tolerance.positive(rem)) continue; 646 646 Node v = _graph.target(e); … … 665 665 666 666 for (InArcIt e(_graph, n); e != INVALID; ++e) { 667 Valuerem = (*_flow)[e];667 Flow rem = (*_flow)[e]; 668 668 if (!_tolerance.positive(rem)) continue; 669 669 Node v = _graph.source(e); … … 779 779 Node n; 780 780 while ((n = _level>highestActive()) != INVALID) { 781 Valueexcess = (*_excess)[n];781 Flow excess = (*_excess)[n]; 782 782 int level = _level>highestActiveLevel(); 783 783 int new_level = _level>maxLevel(); 784 784 785 785 for (OutArcIt e(_graph, n); e != INVALID; ++e) { 786 Valuerem = (*_capacity)[e]  (*_flow)[e];786 Flow rem = (*_capacity)[e]  (*_flow)[e]; 787 787 if (!_tolerance.positive(rem)) continue; 788 788 Node v = _graph.target(e); … … 807 807 808 808 for (InArcIt e(_graph, n); e != INVALID; ++e) { 809 Valuerem = (*_flow)[e];809 Flow rem = (*_flow)[e]; 810 810 if (!_tolerance.positive(rem)) continue; 811 811 Node v = _graph.source(e); … … 898 898 /// \pre Either \ref run() or \ref init() must be called before 899 899 /// using this function. 900 ValueflowValue() const {900 Flow flowValue() const { 901 901 return (*_excess)[_target]; 902 902 } … … 909 909 /// \pre Either \ref run() or \ref init() must be called before 910 910 /// using this function. 911 Valueflow(const Arc& arc) const {911 Flow flow(const Arc& arc) const { 912 912 return (*_flow)[arc]; 913 913 } 
lemon/preflow.h
r610 r611 33 33 /// Default traits class of Preflow class. 34 34 /// \tparam GR Digraph type. 35 /// \tparam C MCapacity map type.36 template <typename GR, typename C M>35 /// \tparam CAP Capacity map type. 36 template <typename GR, typename CAP> 37 37 struct PreflowDefaultTraits { 38 38 … … 44 44 /// The type of the map that stores the arc capacities. 45 45 /// It must meet the \ref concepts::ReadMap "ReadMap" concept. 46 typedef C MCapacityMap;46 typedef CAP CapacityMap; 47 47 48 48 /// \brief The type of the flow values. … … 95 95 /// 96 96 /// This class provides an implementation of GoldbergTarjan's \e preflow 97 /// \e pushrelabel algorithm producing a flow of maximum value in a 98 /// digraph. The preflow algorithms are the fastest known maximum 97 /// \e pushrelabel algorithm producing a \ref max_flow 98 /// "flow of maximum value" in a digraph. 99 /// The preflow algorithms are the fastest known maximum 99 100 /// flow algorithms. The current implementation use a mixture of the 100 101 /// \e "highest label" and the \e "bound decrease" heuristics. … … 106 107 /// 107 108 /// \tparam GR The type of the digraph the algorithm runs on. 108 /// \tparam C MThe type of the capacity map. The default map109 /// \tparam CAP The type of the capacity map. The default map 109 110 /// type is \ref concepts::Digraph::ArcMap "GR::ArcMap<int>". 110 111 #ifdef DOXYGEN 111 template <typename GR, typename C M, typename TR>112 template <typename GR, typename CAP, typename TR> 112 113 #else 113 114 template <typename GR, 114 typename C M= typename GR::template ArcMap<int>,115 typename TR = PreflowDefaultTraits<GR, C M> >115 typename CAP = typename GR::template ArcMap<int>, 116 typename TR = PreflowDefaultTraits<GR, CAP> > 116 117 #endif 117 118 class Preflow { … … 195 196 ///@{ 196 197 197 template <typename _FlowMap>198 template <typename T> 198 199 struct SetFlowMapTraits : public Traits { 199 typedef _FlowMapFlowMap;200 typedef T FlowMap; 200 201 static FlowMap *createFlowMap(const Digraph&) { 201 202 LEMON_ASSERT(false, "FlowMap is not initialized"); … … 209 210 /// \ref namedtemplparam "Named parameter" for setting FlowMap 210 211 /// type. 211 template <typename _FlowMap>212 template <typename T> 212 213 struct SetFlowMap 213 : public Preflow<Digraph, CapacityMap, SetFlowMapTraits< _FlowMap> > {214 : public Preflow<Digraph, CapacityMap, SetFlowMapTraits<T> > { 214 215 typedef Preflow<Digraph, CapacityMap, 215 SetFlowMapTraits< _FlowMap> > Create;216 SetFlowMapTraits<T> > Create; 216 217 }; 217 218 218 template <typename _Elevator>219 template <typename T> 219 220 struct SetElevatorTraits : public Traits { 220 typedef _ElevatorElevator;221 typedef T Elevator; 221 222 static Elevator *createElevator(const Digraph&, int) { 222 223 LEMON_ASSERT(false, "Elevator is not initialized"); … … 234 235 /// \ref run() or \ref init(). 235 236 /// \sa SetStandardElevator 236 template <typename _Elevator>237 template <typename T> 237 238 struct SetElevator 238 : public Preflow<Digraph, CapacityMap, SetElevatorTraits< _Elevator> > {239 : public Preflow<Digraph, CapacityMap, SetElevatorTraits<T> > { 239 240 typedef Preflow<Digraph, CapacityMap, 240 SetElevatorTraits< _Elevator> > Create;241 SetElevatorTraits<T> > Create; 241 242 }; 242 243 243 template <typename _Elevator>244 template <typename T> 244 245 struct SetStandardElevatorTraits : public Traits { 245 typedef _ElevatorElevator;246 typedef T Elevator; 246 247 static Elevator *createElevator(const Digraph& digraph, int max_level) { 247 248 return new Elevator(digraph, max_level); … … 261 262 /// before calling \ref run() or \ref init(). 262 263 /// \sa SetElevator 263 template <typename _Elevator>264 template <typename T> 264 265 struct SetStandardElevator 265 266 : public Preflow<Digraph, CapacityMap, 266 SetStandardElevatorTraits< _Elevator> > {267 SetStandardElevatorTraits<T> > { 267 268 typedef Preflow<Digraph, CapacityMap, 268 SetStandardElevatorTraits< _Elevator> > Create;269 SetStandardElevatorTraits<T> > Create; 269 270 }; 270 271 … … 404 405 _phase = true; 405 406 for (NodeIt n(_graph); n != INVALID; ++n) { 406 _excess>set(n, 0);407 (*_excess)[n] = 0; 407 408 } 408 409 … … 417 418 418 419 std::vector<Node> queue; 419 reached .set(_source, true);420 reached[_source] = true; 420 421 421 422 queue.push_back(_target); 422 reached .set(_target, true);423 reached[_target] = true; 423 424 while (!queue.empty()) { 424 425 _level>initNewLevel(); … … 429 430 Node u = _graph.source(e); 430 431 if (!reached[u] && _tolerance.positive((*_capacity)[e])) { 431 reached .set(u, true);432 reached[u] = true; 432 433 _level>initAddItem(u); 433 434 nqueue.push_back(u); … … 444 445 if ((*_level)[u] == _level>maxLevel()) continue; 445 446 _flow>set(e, (*_capacity)[e]); 446 _excess>set(u, (*_excess)[u] + (*_capacity)[e]);447 (*_excess)[u] += (*_capacity)[e]; 447 448 if (u != _target && !_level>active(u)) { 448 449 _level>activate(u); … … 478 479 } 479 480 if (excess < 0 && n != _source) return false; 480 _excess>set(n, excess);481 (*_excess)[n] = excess; 481 482 } 482 483 … … 487 488 488 489 std::vector<Node> queue; 489 reached .set(_source, true);490 reached[_source] = true; 490 491 491 492 queue.push_back(_target); 492 reached .set(_target, true);493 reached[_target] = true; 493 494 while (!queue.empty()) { 494 495 _level>initNewLevel(); … … 500 501 if (!reached[u] && 501 502 _tolerance.positive((*_capacity)[e]  (*_flow)[e])) { 502 reached .set(u, true);503 reached[u] = true; 503 504 _level>initAddItem(u); 504 505 nqueue.push_back(u); … … 508 509 Node v = _graph.target(e); 509 510 if (!reached[v] && _tolerance.positive((*_flow)[e])) { 510 reached .set(v, true);511 reached[v] = true; 511 512 _level>initAddItem(v); 512 513 nqueue.push_back(v); … … 524 525 if ((*_level)[u] == _level>maxLevel()) continue; 525 526 _flow>set(e, (*_capacity)[e]); 526 _excess>set(u, (*_excess)[u] + rem);527 (*_excess)[u] += rem; 527 528 if (u != _target && !_level>active(u)) { 528 529 _level>activate(u); … … 536 537 if ((*_level)[v] == _level>maxLevel()) continue; 537 538 _flow>set(e, 0); 538 _excess>set(v, (*_excess)[v] + rem);539 (*_excess)[v] += rem; 539 540 if (v != _target && !_level>active(v)) { 540 541 _level>activate(v); … … 577 578 if (!_tolerance.less(rem, excess)) { 578 579 _flow>set(e, (*_flow)[e] + excess); 579 _excess>set(v, (*_excess)[v] + excess);580 (*_excess)[v] += excess; 580 581 excess = 0; 581 582 goto no_more_push_1; 582 583 } else { 583 584 excess = rem; 584 _excess>set(v, (*_excess)[v] + rem);585 (*_excess)[v] += rem; 585 586 _flow>set(e, (*_capacity)[e]); 586 587 } … … 600 601 if (!_tolerance.less(rem, excess)) { 601 602 _flow>set(e, (*_flow)[e]  excess); 602 _excess>set(v, (*_excess)[v] + excess);603 (*_excess)[v] += excess; 603 604 excess = 0; 604 605 goto no_more_push_1; 605 606 } else { 606 607 excess = rem; 607 _excess>set(v, (*_excess)[v] + rem);608 (*_excess)[v] += rem; 608 609 _flow>set(e, 0); 609 610 } … … 615 616 no_more_push_1: 616 617 617 _excess>set(n, excess);618 (*_excess)[n] = excess; 618 619 619 620 if (excess != 0) { … … 650 651 if (!_tolerance.less(rem, excess)) { 651 652 _flow>set(e, (*_flow)[e] + excess); 652 _excess>set(v, (*_excess)[v] + excess);653 (*_excess)[v] += excess; 653 654 excess = 0; 654 655 goto no_more_push_2; 655 656 } else { 656 657 excess = rem; 657 _excess>set(v, (*_excess)[v] + rem);658 (*_excess)[v] += rem; 658 659 _flow>set(e, (*_capacity)[e]); 659 660 } … … 673 674 if (!_tolerance.less(rem, excess)) { 674 675 _flow>set(e, (*_flow)[e]  excess); 675 _excess>set(v, (*_excess)[v] + excess);676 (*_excess)[v] += excess; 676 677 excess = 0; 677 678 goto no_more_push_2; 678 679 } else { 679 680 excess = rem; 680 _excess>set(v, (*_excess)[v] + rem);681 (*_excess)[v] += rem; 681 682 _flow>set(e, 0); 682 683 } … … 688 689 no_more_push_2: 689 690 690 _excess>set(n, excess);691 (*_excess)[n] = excess; 691 692 692 693 if (excess != 0) { … … 731 732 typename Digraph::template NodeMap<bool> reached(_graph); 732 733 for (NodeIt n(_graph); n != INVALID; ++n) { 733 reached .set(n, (*_level)[n] < _level>maxLevel());734 reached[n] = (*_level)[n] < _level>maxLevel(); 734 735 } 735 736 … … 739 740 std::vector<Node> queue; 740 741 queue.push_back(_source); 741 reached .set(_source, true);742 reached[_source] = true; 742 743 743 744 while (!queue.empty()) { … … 749 750 Node v = _graph.target(e); 750 751 if (!reached[v] && _tolerance.positive((*_flow)[e])) { 751 reached .set(v, true);752 reached[v] = true; 752 753 _level>initAddItem(v); 753 754 nqueue.push_back(v); … … 758 759 if (!reached[u] && 759 760 _tolerance.positive((*_capacity)[e]  (*_flow)[e])) { 760 reached .set(u, true);761 reached[u] = true; 761 762 _level>initAddItem(u); 762 763 nqueue.push_back(u); … … 792 793 if (!_tolerance.less(rem, excess)) { 793 794 _flow>set(e, (*_flow)[e] + excess); 794 _excess>set(v, (*_excess)[v] + excess);795 (*_excess)[v] += excess; 795 796 excess = 0; 796 797 goto no_more_push; 797 798 } else { 798 799 excess = rem; 799 _excess>set(v, (*_excess)[v] + rem);800 (*_excess)[v] += rem; 800 801 _flow>set(e, (*_capacity)[e]); 801 802 } … … 815 816 if (!_tolerance.less(rem, excess)) { 816 817 _flow>set(e, (*_flow)[e]  excess); 817 _excess>set(v, (*_excess)[v] + excess);818 (*_excess)[v] += excess; 818 819 excess = 0; 819 820 goto no_more_push; 820 821 } else { 821 822 excess = rem; 822 _excess>set(v, (*_excess)[v] + rem);823 (*_excess)[v] += rem; 823 824 _flow>set(e, 0); 824 825 } … … 830 831 no_more_push: 831 832 832 _excess>set(n, excess);833 (*_excess)[n] = excess; 833 834 834 835 if (excess != 0) { … … 947 948 /// 948 949 /// \note This function calls \ref minCut() for each node, so it runs in 949 /// \f$O(n)\f$time.950 /// O(n) time. 950 951 /// 951 952 /// \pre Either \ref run() or \ref init() must be called before
Note: See TracChangeset
for help on using the changeset viewer.