44 /// The type of the map that stores the arc capacities. |
44 /// The type of the map that stores the arc capacities. |
45 /// It must meet the \ref concepts::ReadMap "ReadMap" concept. |
45 /// It must meet the \ref concepts::ReadMap "ReadMap" concept. |
46 typedef CAP CapacityMap; |
46 typedef CAP CapacityMap; |
47 |
47 |
48 /// \brief The type of the flow values. |
48 /// \brief The type of the flow values. |
49 typedef typename CapacityMap::Value Value; |
49 typedef typename CapacityMap::Value Flow; |
50 |
50 |
51 /// \brief The type of the map that stores the flow values. |
51 /// \brief The type of the map that stores the flow values. |
52 /// |
52 /// |
53 /// The type of the map that stores the flow values. |
53 /// The type of the map that stores the flow values. |
54 /// It must meet the \ref concepts::ReadWriteMap "ReadWriteMap" concept. |
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 /// \brief Instantiates a FlowMap. |
57 /// \brief Instantiates a FlowMap. |
58 /// |
58 /// |
59 /// This function instantiates a \ref FlowMap. |
59 /// This function instantiates a \ref FlowMap. |
60 /// \param digraph The digraph, to which we would like to define |
60 /// \param digraph The digraph for which we would like to define |
61 /// the flow map. |
61 /// the flow map. |
62 static FlowMap* createFlowMap(const Digraph& digraph) { |
62 static FlowMap* createFlowMap(const Digraph& digraph) { |
63 return new FlowMap(digraph); |
63 return new FlowMap(digraph); |
64 } |
64 } |
65 |
65 |
72 typedef LinkedElevator<Digraph, typename Digraph::Node> Elevator; |
72 typedef LinkedElevator<Digraph, typename Digraph::Node> Elevator; |
73 |
73 |
74 /// \brief Instantiates an Elevator. |
74 /// \brief Instantiates an Elevator. |
75 /// |
75 /// |
76 /// This function instantiates an \ref Elevator. |
76 /// This function instantiates an \ref Elevator. |
77 /// \param digraph The digraph, to which we would like to define |
77 /// \param digraph The digraph for which we would like to define |
78 /// the elevator. |
78 /// the elevator. |
79 /// \param max_level The maximum level of the elevator. |
79 /// \param max_level The maximum level of the elevator. |
80 static Elevator* createElevator(const Digraph& digraph, int max_level) { |
80 static Elevator* createElevator(const Digraph& digraph, int max_level) { |
81 return new Elevator(digraph, max_level); |
81 return new Elevator(digraph, max_level); |
82 } |
82 } |
83 |
83 |
84 /// \brief The tolerance used by the algorithm |
84 /// \brief The tolerance used by the algorithm |
85 /// |
85 /// |
86 /// The tolerance used by the algorithm to handle inexact computation. |
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 }; |
90 |
90 |
91 |
91 |
92 /// \ingroup max_flow |
92 /// \ingroup max_flow |
123 ///The type of the digraph the algorithm runs on. |
123 ///The type of the digraph the algorithm runs on. |
124 typedef typename Traits::Digraph Digraph; |
124 typedef typename Traits::Digraph Digraph; |
125 ///The type of the capacity map. |
125 ///The type of the capacity map. |
126 typedef typename Traits::CapacityMap CapacityMap; |
126 typedef typename Traits::CapacityMap CapacityMap; |
127 ///The type of the flow values. |
127 ///The type of the flow values. |
128 typedef typename Traits::Value Value; |
128 typedef typename Traits::Flow Flow; |
129 |
129 |
130 ///The type of the flow map. |
130 ///The type of the flow map. |
131 typedef typename Traits::FlowMap FlowMap; |
131 typedef typename Traits::FlowMap FlowMap; |
132 ///The type of the elevator. |
132 ///The type of the elevator. |
133 typedef typename Traits::Elevator Elevator; |
133 typedef typename Traits::Elevator Elevator; |
468 for (ArcIt e(_graph); e != INVALID; ++e) { |
468 for (ArcIt e(_graph); e != INVALID; ++e) { |
469 _flow->set(e, flowMap[e]); |
469 _flow->set(e, flowMap[e]); |
470 } |
470 } |
471 |
471 |
472 for (NodeIt n(_graph); n != INVALID; ++n) { |
472 for (NodeIt n(_graph); n != INVALID; ++n) { |
473 Value excess = 0; |
473 Flow excess = 0; |
474 for (InArcIt e(_graph, n); e != INVALID; ++e) { |
474 for (InArcIt e(_graph, n); e != INVALID; ++e) { |
475 excess += (*_flow)[e]; |
475 excess += (*_flow)[e]; |
476 } |
476 } |
477 for (OutArcIt e(_graph, n); e != INVALID; ++e) { |
477 for (OutArcIt e(_graph, n); e != INVALID; ++e) { |
478 excess -= (*_flow)[e]; |
478 excess -= (*_flow)[e]; |
517 queue.swap(nqueue); |
517 queue.swap(nqueue); |
518 } |
518 } |
519 _level->initFinish(); |
519 _level->initFinish(); |
520 |
520 |
521 for (OutArcIt e(_graph, _source); e != INVALID; ++e) { |
521 for (OutArcIt e(_graph, _source); e != INVALID; ++e) { |
522 Value rem = (*_capacity)[e] - (*_flow)[e]; |
522 Flow rem = (*_capacity)[e] - (*_flow)[e]; |
523 if (_tolerance.positive(rem)) { |
523 if (_tolerance.positive(rem)) { |
524 Node u = _graph.target(e); |
524 Node u = _graph.target(e); |
525 if ((*_level)[u] == _level->maxLevel()) continue; |
525 if ((*_level)[u] == _level->maxLevel()) continue; |
526 _flow->set(e, (*_capacity)[e]); |
526 _flow->set(e, (*_capacity)[e]); |
527 (*_excess)[u] += rem; |
527 (*_excess)[u] += rem; |
529 _level->activate(u); |
529 _level->activate(u); |
530 } |
530 } |
531 } |
531 } |
532 } |
532 } |
533 for (InArcIt e(_graph, _source); e != INVALID; ++e) { |
533 for (InArcIt e(_graph, _source); e != INVALID; ++e) { |
534 Value rem = (*_flow)[e]; |
534 Flow rem = (*_flow)[e]; |
535 if (_tolerance.positive(rem)) { |
535 if (_tolerance.positive(rem)) { |
536 Node v = _graph.source(e); |
536 Node v = _graph.source(e); |
537 if ((*_level)[v] == _level->maxLevel()) continue; |
537 if ((*_level)[v] == _level->maxLevel()) continue; |
538 _flow->set(e, 0); |
538 _flow->set(e, 0); |
539 (*_excess)[v] += rem; |
539 (*_excess)[v] += rem; |
562 int level = _level->highestActiveLevel(); |
562 int level = _level->highestActiveLevel(); |
563 while (n != INVALID) { |
563 while (n != INVALID) { |
564 int num = _node_num; |
564 int num = _node_num; |
565 |
565 |
566 while (num > 0 && n != INVALID) { |
566 while (num > 0 && n != INVALID) { |
567 Value excess = (*_excess)[n]; |
567 Flow excess = (*_excess)[n]; |
568 int new_level = _level->maxLevel(); |
568 int new_level = _level->maxLevel(); |
569 |
569 |
570 for (OutArcIt e(_graph, n); e != INVALID; ++e) { |
570 for (OutArcIt e(_graph, n); e != INVALID; ++e) { |
571 Value rem = (*_capacity)[e] - (*_flow)[e]; |
571 Flow rem = (*_capacity)[e] - (*_flow)[e]; |
572 if (!_tolerance.positive(rem)) continue; |
572 if (!_tolerance.positive(rem)) continue; |
573 Node v = _graph.target(e); |
573 Node v = _graph.target(e); |
574 if ((*_level)[v] < level) { |
574 if ((*_level)[v] < level) { |
575 if (!_level->active(v) && v != _target) { |
575 if (!_level->active(v) && v != _target) { |
576 _level->activate(v); |
576 _level->activate(v); |
589 new_level = (*_level)[v]; |
589 new_level = (*_level)[v]; |
590 } |
590 } |
591 } |
591 } |
592 |
592 |
593 for (InArcIt e(_graph, n); e != INVALID; ++e) { |
593 for (InArcIt e(_graph, n); e != INVALID; ++e) { |
594 Value rem = (*_flow)[e]; |
594 Flow rem = (*_flow)[e]; |
595 if (!_tolerance.positive(rem)) continue; |
595 if (!_tolerance.positive(rem)) continue; |
596 Node v = _graph.source(e); |
596 Node v = _graph.source(e); |
597 if ((*_level)[v] < level) { |
597 if ((*_level)[v] < level) { |
598 if (!_level->active(v) && v != _target) { |
598 if (!_level->active(v) && v != _target) { |
599 _level->activate(v); |
599 _level->activate(v); |
635 --num; |
635 --num; |
636 } |
636 } |
637 |
637 |
638 num = _node_num * 20; |
638 num = _node_num * 20; |
639 while (num > 0 && n != INVALID) { |
639 while (num > 0 && n != INVALID) { |
640 Value excess = (*_excess)[n]; |
640 Flow excess = (*_excess)[n]; |
641 int new_level = _level->maxLevel(); |
641 int new_level = _level->maxLevel(); |
642 |
642 |
643 for (OutArcIt e(_graph, n); e != INVALID; ++e) { |
643 for (OutArcIt e(_graph, n); e != INVALID; ++e) { |
644 Value rem = (*_capacity)[e] - (*_flow)[e]; |
644 Flow rem = (*_capacity)[e] - (*_flow)[e]; |
645 if (!_tolerance.positive(rem)) continue; |
645 if (!_tolerance.positive(rem)) continue; |
646 Node v = _graph.target(e); |
646 Node v = _graph.target(e); |
647 if ((*_level)[v] < level) { |
647 if ((*_level)[v] < level) { |
648 if (!_level->active(v) && v != _target) { |
648 if (!_level->active(v) && v != _target) { |
649 _level->activate(v); |
649 _level->activate(v); |
662 new_level = (*_level)[v]; |
662 new_level = (*_level)[v]; |
663 } |
663 } |
664 } |
664 } |
665 |
665 |
666 for (InArcIt e(_graph, n); e != INVALID; ++e) { |
666 for (InArcIt e(_graph, n); e != INVALID; ++e) { |
667 Value rem = (*_flow)[e]; |
667 Flow rem = (*_flow)[e]; |
668 if (!_tolerance.positive(rem)) continue; |
668 if (!_tolerance.positive(rem)) continue; |
669 Node v = _graph.source(e); |
669 Node v = _graph.source(e); |
670 if ((*_level)[v] < level) { |
670 if ((*_level)[v] < level) { |
671 if (!_level->active(v) && v != _target) { |
671 if (!_level->active(v) && v != _target) { |
672 _level->activate(v); |
672 _level->activate(v); |
776 } |
776 } |
777 } |
777 } |
778 |
778 |
779 Node n; |
779 Node n; |
780 while ((n = _level->highestActive()) != INVALID) { |
780 while ((n = _level->highestActive()) != INVALID) { |
781 Value excess = (*_excess)[n]; |
781 Flow excess = (*_excess)[n]; |
782 int level = _level->highestActiveLevel(); |
782 int level = _level->highestActiveLevel(); |
783 int new_level = _level->maxLevel(); |
783 int new_level = _level->maxLevel(); |
784 |
784 |
785 for (OutArcIt e(_graph, n); e != INVALID; ++e) { |
785 for (OutArcIt e(_graph, n); e != INVALID; ++e) { |
786 Value rem = (*_capacity)[e] - (*_flow)[e]; |
786 Flow rem = (*_capacity)[e] - (*_flow)[e]; |
787 if (!_tolerance.positive(rem)) continue; |
787 if (!_tolerance.positive(rem)) continue; |
788 Node v = _graph.target(e); |
788 Node v = _graph.target(e); |
789 if ((*_level)[v] < level) { |
789 if ((*_level)[v] < level) { |
790 if (!_level->active(v) && v != _source) { |
790 if (!_level->active(v) && v != _source) { |
791 _level->activate(v); |
791 _level->activate(v); |
804 new_level = (*_level)[v]; |
804 new_level = (*_level)[v]; |
805 } |
805 } |
806 } |
806 } |
807 |
807 |
808 for (InArcIt e(_graph, n); e != INVALID; ++e) { |
808 for (InArcIt e(_graph, n); e != INVALID; ++e) { |
809 Value rem = (*_flow)[e]; |
809 Flow rem = (*_flow)[e]; |
810 if (!_tolerance.positive(rem)) continue; |
810 if (!_tolerance.positive(rem)) continue; |
811 Node v = _graph.source(e); |
811 Node v = _graph.source(e); |
812 if ((*_level)[v] < level) { |
812 if ((*_level)[v] < level) { |
813 if (!_level->active(v) && v != _source) { |
813 if (!_level->active(v) && v != _source) { |
814 _level->activate(v); |
814 _level->activate(v); |
895 /// of the target node. This value equals to the value of |
895 /// of the target node. This value equals to the value of |
896 /// the maximum flow already after the first phase of the algorithm. |
896 /// the maximum flow already after the first phase of the algorithm. |
897 /// |
897 /// |
898 /// \pre Either \ref run() or \ref init() must be called before |
898 /// \pre Either \ref run() or \ref init() must be called before |
899 /// using this function. |
899 /// using this function. |
900 Value flowValue() const { |
900 Flow flowValue() const { |
901 return (*_excess)[_target]; |
901 return (*_excess)[_target]; |
902 } |
902 } |
903 |
903 |
904 /// \brief Returns the flow on the given arc. |
904 /// \brief Returns the flow on the given arc. |
905 /// |
905 /// |
906 /// Returns the flow on the given arc. This method can |
906 /// Returns the flow on the given arc. This method can |
907 /// be called after the second phase of the algorithm. |
907 /// be called after the second phase of the algorithm. |
908 /// |
908 /// |
909 /// \pre Either \ref run() or \ref init() must be called before |
909 /// \pre Either \ref run() or \ref init() must be called before |
910 /// using this function. |
910 /// using this function. |
911 Value flow(const Arc& arc) const { |
911 Flow flow(const Arc& arc) const { |
912 return (*_flow)[arc]; |
912 return (*_flow)[arc]; |
913 } |
913 } |
914 |
914 |
915 /// \brief Returns a const reference to the flow map. |
915 /// \brief Returns a const reference to the flow map. |
916 /// |
916 /// |