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 CM CapacityMap; |
46 typedef CM 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 |
122 ///The type of the digraph the algorithm runs on. |
122 ///The type of the digraph the algorithm runs on. |
123 typedef typename Traits::Digraph Digraph; |
123 typedef typename Traits::Digraph Digraph; |
124 ///The type of the capacity map. |
124 ///The type of the capacity map. |
125 typedef typename Traits::CapacityMap CapacityMap; |
125 typedef typename Traits::CapacityMap CapacityMap; |
126 ///The type of the flow values. |
126 ///The type of the flow values. |
127 typedef typename Traits::Value Value; |
127 typedef typename Traits::Flow Flow; |
128 |
128 |
129 ///The type of the flow map. |
129 ///The type of the flow map. |
130 typedef typename Traits::FlowMap FlowMap; |
130 typedef typename Traits::FlowMap FlowMap; |
131 ///The type of the elevator. |
131 ///The type of the elevator. |
132 typedef typename Traits::Elevator Elevator; |
132 typedef typename Traits::Elevator Elevator; |
467 for (ArcIt e(_graph); e != INVALID; ++e) { |
467 for (ArcIt e(_graph); e != INVALID; ++e) { |
468 _flow->set(e, flowMap[e]); |
468 _flow->set(e, flowMap[e]); |
469 } |
469 } |
470 |
470 |
471 for (NodeIt n(_graph); n != INVALID; ++n) { |
471 for (NodeIt n(_graph); n != INVALID; ++n) { |
472 Value excess = 0; |
472 Flow excess = 0; |
473 for (InArcIt e(_graph, n); e != INVALID; ++e) { |
473 for (InArcIt e(_graph, n); e != INVALID; ++e) { |
474 excess += (*_flow)[e]; |
474 excess += (*_flow)[e]; |
475 } |
475 } |
476 for (OutArcIt e(_graph, n); e != INVALID; ++e) { |
476 for (OutArcIt e(_graph, n); e != INVALID; ++e) { |
477 excess -= (*_flow)[e]; |
477 excess -= (*_flow)[e]; |
516 queue.swap(nqueue); |
516 queue.swap(nqueue); |
517 } |
517 } |
518 _level->initFinish(); |
518 _level->initFinish(); |
519 |
519 |
520 for (OutArcIt e(_graph, _source); e != INVALID; ++e) { |
520 for (OutArcIt e(_graph, _source); e != INVALID; ++e) { |
521 Value rem = (*_capacity)[e] - (*_flow)[e]; |
521 Flow rem = (*_capacity)[e] - (*_flow)[e]; |
522 if (_tolerance.positive(rem)) { |
522 if (_tolerance.positive(rem)) { |
523 Node u = _graph.target(e); |
523 Node u = _graph.target(e); |
524 if ((*_level)[u] == _level->maxLevel()) continue; |
524 if ((*_level)[u] == _level->maxLevel()) continue; |
525 _flow->set(e, (*_capacity)[e]); |
525 _flow->set(e, (*_capacity)[e]); |
526 _excess->set(u, (*_excess)[u] + rem); |
526 _excess->set(u, (*_excess)[u] + rem); |
528 _level->activate(u); |
528 _level->activate(u); |
529 } |
529 } |
530 } |
530 } |
531 } |
531 } |
532 for (InArcIt e(_graph, _source); e != INVALID; ++e) { |
532 for (InArcIt e(_graph, _source); e != INVALID; ++e) { |
533 Value rem = (*_flow)[e]; |
533 Flow rem = (*_flow)[e]; |
534 if (_tolerance.positive(rem)) { |
534 if (_tolerance.positive(rem)) { |
535 Node v = _graph.source(e); |
535 Node v = _graph.source(e); |
536 if ((*_level)[v] == _level->maxLevel()) continue; |
536 if ((*_level)[v] == _level->maxLevel()) continue; |
537 _flow->set(e, 0); |
537 _flow->set(e, 0); |
538 _excess->set(v, (*_excess)[v] + rem); |
538 _excess->set(v, (*_excess)[v] + rem); |
561 int level = _level->highestActiveLevel(); |
561 int level = _level->highestActiveLevel(); |
562 while (n != INVALID) { |
562 while (n != INVALID) { |
563 int num = _node_num; |
563 int num = _node_num; |
564 |
564 |
565 while (num > 0 && n != INVALID) { |
565 while (num > 0 && n != INVALID) { |
566 Value excess = (*_excess)[n]; |
566 Flow excess = (*_excess)[n]; |
567 int new_level = _level->maxLevel(); |
567 int new_level = _level->maxLevel(); |
568 |
568 |
569 for (OutArcIt e(_graph, n); e != INVALID; ++e) { |
569 for (OutArcIt e(_graph, n); e != INVALID; ++e) { |
570 Value rem = (*_capacity)[e] - (*_flow)[e]; |
570 Flow rem = (*_capacity)[e] - (*_flow)[e]; |
571 if (!_tolerance.positive(rem)) continue; |
571 if (!_tolerance.positive(rem)) continue; |
572 Node v = _graph.target(e); |
572 Node v = _graph.target(e); |
573 if ((*_level)[v] < level) { |
573 if ((*_level)[v] < level) { |
574 if (!_level->active(v) && v != _target) { |
574 if (!_level->active(v) && v != _target) { |
575 _level->activate(v); |
575 _level->activate(v); |
588 new_level = (*_level)[v]; |
588 new_level = (*_level)[v]; |
589 } |
589 } |
590 } |
590 } |
591 |
591 |
592 for (InArcIt e(_graph, n); e != INVALID; ++e) { |
592 for (InArcIt e(_graph, n); e != INVALID; ++e) { |
593 Value rem = (*_flow)[e]; |
593 Flow rem = (*_flow)[e]; |
594 if (!_tolerance.positive(rem)) continue; |
594 if (!_tolerance.positive(rem)) continue; |
595 Node v = _graph.source(e); |
595 Node v = _graph.source(e); |
596 if ((*_level)[v] < level) { |
596 if ((*_level)[v] < level) { |
597 if (!_level->active(v) && v != _target) { |
597 if (!_level->active(v) && v != _target) { |
598 _level->activate(v); |
598 _level->activate(v); |
634 --num; |
634 --num; |
635 } |
635 } |
636 |
636 |
637 num = _node_num * 20; |
637 num = _node_num * 20; |
638 while (num > 0 && n != INVALID) { |
638 while (num > 0 && n != INVALID) { |
639 Value excess = (*_excess)[n]; |
639 Flow excess = (*_excess)[n]; |
640 int new_level = _level->maxLevel(); |
640 int new_level = _level->maxLevel(); |
641 |
641 |
642 for (OutArcIt e(_graph, n); e != INVALID; ++e) { |
642 for (OutArcIt e(_graph, n); e != INVALID; ++e) { |
643 Value rem = (*_capacity)[e] - (*_flow)[e]; |
643 Flow rem = (*_capacity)[e] - (*_flow)[e]; |
644 if (!_tolerance.positive(rem)) continue; |
644 if (!_tolerance.positive(rem)) continue; |
645 Node v = _graph.target(e); |
645 Node v = _graph.target(e); |
646 if ((*_level)[v] < level) { |
646 if ((*_level)[v] < level) { |
647 if (!_level->active(v) && v != _target) { |
647 if (!_level->active(v) && v != _target) { |
648 _level->activate(v); |
648 _level->activate(v); |
661 new_level = (*_level)[v]; |
661 new_level = (*_level)[v]; |
662 } |
662 } |
663 } |
663 } |
664 |
664 |
665 for (InArcIt e(_graph, n); e != INVALID; ++e) { |
665 for (InArcIt e(_graph, n); e != INVALID; ++e) { |
666 Value rem = (*_flow)[e]; |
666 Flow rem = (*_flow)[e]; |
667 if (!_tolerance.positive(rem)) continue; |
667 if (!_tolerance.positive(rem)) continue; |
668 Node v = _graph.source(e); |
668 Node v = _graph.source(e); |
669 if ((*_level)[v] < level) { |
669 if ((*_level)[v] < level) { |
670 if (!_level->active(v) && v != _target) { |
670 if (!_level->active(v) && v != _target) { |
671 _level->activate(v); |
671 _level->activate(v); |
775 } |
775 } |
776 } |
776 } |
777 |
777 |
778 Node n; |
778 Node n; |
779 while ((n = _level->highestActive()) != INVALID) { |
779 while ((n = _level->highestActive()) != INVALID) { |
780 Value excess = (*_excess)[n]; |
780 Flow excess = (*_excess)[n]; |
781 int level = _level->highestActiveLevel(); |
781 int level = _level->highestActiveLevel(); |
782 int new_level = _level->maxLevel(); |
782 int new_level = _level->maxLevel(); |
783 |
783 |
784 for (OutArcIt e(_graph, n); e != INVALID; ++e) { |
784 for (OutArcIt e(_graph, n); e != INVALID; ++e) { |
785 Value rem = (*_capacity)[e] - (*_flow)[e]; |
785 Flow rem = (*_capacity)[e] - (*_flow)[e]; |
786 if (!_tolerance.positive(rem)) continue; |
786 if (!_tolerance.positive(rem)) continue; |
787 Node v = _graph.target(e); |
787 Node v = _graph.target(e); |
788 if ((*_level)[v] < level) { |
788 if ((*_level)[v] < level) { |
789 if (!_level->active(v) && v != _source) { |
789 if (!_level->active(v) && v != _source) { |
790 _level->activate(v); |
790 _level->activate(v); |
803 new_level = (*_level)[v]; |
803 new_level = (*_level)[v]; |
804 } |
804 } |
805 } |
805 } |
806 |
806 |
807 for (InArcIt e(_graph, n); e != INVALID; ++e) { |
807 for (InArcIt e(_graph, n); e != INVALID; ++e) { |
808 Value rem = (*_flow)[e]; |
808 Flow rem = (*_flow)[e]; |
809 if (!_tolerance.positive(rem)) continue; |
809 if (!_tolerance.positive(rem)) continue; |
810 Node v = _graph.source(e); |
810 Node v = _graph.source(e); |
811 if ((*_level)[v] < level) { |
811 if ((*_level)[v] < level) { |
812 if (!_level->active(v) && v != _source) { |
812 if (!_level->active(v) && v != _source) { |
813 _level->activate(v); |
813 _level->activate(v); |
894 /// of the target node. This value equals to the value of |
894 /// of the target node. This value equals to the value of |
895 /// the maximum flow already after the first phase of the algorithm. |
895 /// the maximum flow already after the first phase of the algorithm. |
896 /// |
896 /// |
897 /// \pre Either \ref run() or \ref init() must be called before |
897 /// \pre Either \ref run() or \ref init() must be called before |
898 /// using this function. |
898 /// using this function. |
899 Value flowValue() const { |
899 Flow flowValue() const { |
900 return (*_excess)[_target]; |
900 return (*_excess)[_target]; |
901 } |
901 } |
902 |
902 |
903 /// \brief Returns the flow on the given arc. |
903 /// \brief Returns the flow on the given arc. |
904 /// |
904 /// |
905 /// Returns the flow on the given arc. This method can |
905 /// Returns the flow on the given arc. This method can |
906 /// be called after the second phase of the algorithm. |
906 /// be called after the second phase of the algorithm. |
907 /// |
907 /// |
908 /// \pre Either \ref run() or \ref init() must be called before |
908 /// \pre Either \ref run() or \ref init() must be called before |
909 /// using this function. |
909 /// using this function. |
910 Value flow(const Arc& arc) const { |
910 Flow flow(const Arc& arc) const { |
911 return (*_flow)[arc]; |
911 return (*_flow)[arc]; |
912 } |
912 } |
913 |
913 |
914 /// \brief Returns a const reference to the flow map. |
914 /// \brief Returns a const reference to the flow map. |
915 /// |
915 /// |