equal
deleted
inserted
replaced
70 /// |
70 /// |
71 /// The elevator type used by Preflow algorithm. |
71 /// The elevator type used by Preflow algorithm. |
72 /// |
72 /// |
73 /// \sa Elevator |
73 /// \sa Elevator |
74 /// \sa LinkedElevator |
74 /// \sa LinkedElevator |
75 typedef LinkedElevator<Graph, typename Graph::Node> Elevator; |
75 typedef Elevator<Graph, typename Graph::Node> Elevator; |
76 |
76 |
77 /// \brief Instantiates an Elevator. |
77 /// \brief Instantiates an Elevator. |
78 /// |
78 /// |
79 /// This function instantiates a \ref Elevator. |
79 /// This function instantiates a \ref Elevator. |
80 /// \param graph The graph, to which we would like to define the elevator. |
80 /// \param graph The graph, to which we would like to define the elevator. |
98 /// This class provides an implementation of the Goldberg's \e |
98 /// This class provides an implementation of the Goldberg's \e |
99 /// preflow \e algorithm producing a flow of maximum value in a |
99 /// preflow \e algorithm producing a flow of maximum value in a |
100 /// directed graph. The preflow algorithms are the fastest known max |
100 /// directed graph. The preflow algorithms are the fastest known max |
101 /// flow algorithms. The current implementation use a mixture of the |
101 /// flow algorithms. The current implementation use a mixture of the |
102 /// \e "highest label" and the \e "bound decrease" heuristics. |
102 /// \e "highest label" and the \e "bound decrease" heuristics. |
103 /// The worst case time complexity of the algorithm is \f$O(n^3)\f$. |
103 /// The worst case time complexity of the algorithm is \f$O(n^2\sqrt{e})\f$. |
104 /// |
104 /// |
105 /// The algorithm consists from two phases. After the first phase |
105 /// The algorithm consists from two phases. After the first phase |
106 /// the maximal flow value and the minimum cut can be obtained. The |
106 /// the maximal flow value and the minimum cut can be obtained. The |
107 /// second phase constructs the feasible maximum flow on each edge. |
107 /// second phase constructs the feasible maximum flow on each edge. |
108 /// |
108 /// |
405 reached.set(_source, true); |
405 reached.set(_source, true); |
406 |
406 |
407 queue.push_back(_target); |
407 queue.push_back(_target); |
408 reached.set(_target, true); |
408 reached.set(_target, true); |
409 while (!queue.empty()) { |
409 while (!queue.empty()) { |
|
410 _level->initNewLevel(); |
410 std::vector<Node> nqueue; |
411 std::vector<Node> nqueue; |
411 for (int i = 0; i < int(queue.size()); ++i) { |
412 for (int i = 0; i < int(queue.size()); ++i) { |
412 Node n = queue[i]; |
413 Node n = queue[i]; |
413 for (InEdgeIt e(_graph, n); e != INVALID; ++e) { |
414 for (InEdgeIt e(_graph, n); e != INVALID; ++e) { |
414 Node u = _graph.source(e); |
415 Node u = _graph.source(e); |
861 } |
862 } |
862 |
863 |
863 /// @} |
864 /// @} |
864 |
865 |
865 /// \name Query Functions |
866 /// \name Query Functions |
866 /// The result of the %Dijkstra algorithm can be obtained using these |
867 /// The result of the %Preflow algorithm can be obtained using these |
867 /// functions.\n |
868 /// functions.\n |
868 /// Before the use of these functions, |
869 /// Before the use of these functions, |
869 /// either run() or start() must be called. |
870 /// either run() or start() must be called. |
870 |
871 |
871 ///@{ |
872 ///@{ |