101 /// \e algorithm producing a flow of maximum value in a directed |
101 /// \e algorithm producing a flow of maximum value in a directed |
102 /// graph. The GoldbergTarjan algorithm is a theoretical improvement |
102 /// graph. The GoldbergTarjan algorithm is a theoretical improvement |
103 /// of the Goldberg's \ref Preflow "preflow" algorithm by using the \ref |
103 /// of the Goldberg's \ref Preflow "preflow" algorithm by using the \ref |
104 /// DynamicTree "dynamic tree" data structure of Sleator and Tarjan. |
104 /// DynamicTree "dynamic tree" data structure of Sleator and Tarjan. |
105 /// |
105 /// |
106 /// The original preflow algorithm with \e "highest label" or \e |
106 /// The original preflow algorithm with \e highest \e label |
107 /// FIFO heuristic has \f$O(n^3)\f$ time complexity. The current |
107 /// heuristic has \f$O(n^2\sqrt{e})\f$ or with \e FIFO heuristic has |
108 /// algorithm improved this complexity to |
108 /// \f$O(n^3)\f$ time complexity. The current algorithm improved |
109 /// \f$O(nm\log(\frac{n^2}{m}))\f$. The algorithm builds limited |
109 /// this complexity to \f$O(nm\log(\frac{n^2}{m}))\f$. The algorithm |
110 /// size dynamic trees on the residual graph, which can be used to |
110 /// builds limited size dynamic trees on the residual graph, which |
111 /// make multilevel push operations and gives a better bound on the |
111 /// can be used to make multilevel push operations and gives a |
112 /// number of non-saturating pushes. |
112 /// better bound on the number of non-saturating pushes. |
113 /// |
113 /// |
114 /// \param Graph The directed graph type the algorithm runs on. |
114 /// \param Graph The directed graph type the algorithm runs on. |
115 /// \param CapacityMap The capacity map type. |
115 /// \param CapacityMap The capacity map type. |
116 /// \param _Traits Traits class to set various data types used by |
116 /// \param _Traits Traits class to set various data types used by |
117 /// the algorithm. The default traits class is \ref |
117 /// the algorithm. The default traits class is \ref |
963 startFirstPhase(); |
963 startFirstPhase(); |
964 } |
964 } |
965 |
965 |
966 /// @} |
966 /// @} |
967 |
967 |
968 /// \name Query Functions |
968 /// \name Query Functions |
969 /// The result of the %Dijkstra algorithm can be obtained using these |
969 /// The result of the Goldberg-Tarjan algorithm can be obtained |
970 /// functions.\n |
970 /// using these functions. |
971 /// Before the use of these functions, |
971 /// \n |
972 /// either run() or start() must be called. |
972 /// Before the use of these functions, either run() or start() must |
|
973 /// be called. |
973 |
974 |
974 ///@{ |
975 ///@{ |
975 |
976 |
976 /// \brief Returns the value of the maximum flow. |
977 /// \brief Returns the value of the maximum flow. |
977 /// |
978 /// |