1.1 --- a/lemon/dinitz_sleator_tarjan.h	Sun Nov 25 22:56:44 2007 +0000
     1.2 +++ b/lemon/dinitz_sleator_tarjan.h	Tue Nov 27 15:41:43 2007 +0000
     1.3 @@ -701,9 +701,10 @@
     1.4  
     1.5      /// @}
     1.6  
     1.7 -    /// \name Query Functions
     1.8 -    /// The result of the %Dijkstra algorithm can be obtained using these
     1.9 -    /// functions.\n
    1.10 +    /// \name Query Functions 
    1.11 +    /// The result of the Dinitz-Sleator-Tarjan algorithm can be
    1.12 +    /// obtained using these functions.
    1.13 +    /// \n
    1.14      /// Before the use of these functions,
    1.15      /// either run() or start() must be called.
    1.16      

     2.1 --- a/lemon/edmonds_karp.h	Sun Nov 25 22:56:44 2007 +0000
     2.2 +++ b/lemon/edmonds_karp.h	Tue Nov 27 15:41:43 2007 +0000
     2.3 @@ -467,7 +467,7 @@
     2.4      /// @}
     2.5  
     2.6      /// \name Query Functions
     2.7 -    /// The result of the %Dijkstra algorithm can be obtained using these
     2.8 +    /// The result of the Edmonds-Karp algorithm can be obtained using these
     2.9      /// functions.\n
    2.10      /// Before the use of these functions,
    2.11      /// either run() or start() must be called.

     3.1 --- a/lemon/goldberg_tarjan.h	Sun Nov 25 22:56:44 2007 +0000
     3.2 +++ b/lemon/goldberg_tarjan.h	Tue Nov 27 15:41:43 2007 +0000
     3.3 @@ -103,13 +103,13 @@
     3.4    /// of the Goldberg's \ref Preflow "preflow" algorithm by using the \ref
     3.5    /// DynamicTree "dynamic tree" data structure of Sleator and Tarjan.
     3.6    /// 
     3.7 -  /// The original preflow algorithm with \e "highest label" or \e
     3.8 -  /// FIFO heuristic has \f$O(n^3)\f$ time complexity. The current
     3.9 -  /// algorithm improved this complexity to
    3.10 -  /// \f$O(nm\log(\frac{n^2}{m}))\f$. The algorithm builds limited
    3.11 -  /// size dynamic trees on the residual graph, which can be used to
    3.12 -  /// make multilevel push operations and gives a better bound on the
    3.13 -  /// number of non-saturating pushes.
    3.14 +  /// The original preflow algorithm with \e highest \e label
    3.15 +  /// heuristic has \f$O(n^2\sqrt{e})\f$ or with \e FIFO heuristic has
    3.16 +  /// \f$O(n^3)\f$ time complexity. The current algorithm improved
    3.17 +  /// this complexity to \f$O(nm\log(\frac{n^2}{m}))\f$. The algorithm
    3.18 +  /// builds limited size dynamic trees on the residual graph, which
    3.19 +  /// can be used to make multilevel push operations and gives a
    3.20 +  /// better bound on the number of non-saturating pushes.
    3.21    ///
    3.22    /// \param Graph The directed graph type the algorithm runs on.
    3.23    /// \param CapacityMap The capacity map type.
    3.24 @@ -965,11 +965,12 @@
    3.25  
    3.26      /// @}
    3.27  
    3.28 -    /// \name Query Functions
    3.29 -    /// The result of the %Dijkstra algorithm can be obtained using these
    3.30 -    /// functions.\n
    3.31 -    /// Before the use of these functions,
    3.32 -    /// either run() or start() must be called.
    3.33 +    /// \name Query Functions 
    3.34 +    /// The result of the Goldberg-Tarjan algorithm can be obtained
    3.35 +    /// using these functions.
    3.36 +    /// \n
    3.37 +    /// Before the use of these functions, either run() or start() must
    3.38 +    /// be called.
    3.39      
    3.40      ///@{
    3.41  

     4.1 --- a/lemon/preflow.h	Sun Nov 25 22:56:44 2007 +0000
     4.2 +++ b/lemon/preflow.h	Tue Nov 27 15:41:43 2007 +0000
     4.3 @@ -72,7 +72,7 @@
     4.4      ///
     4.5      /// \sa Elevator
     4.6      /// \sa LinkedElevator
     4.7 -    typedef LinkedElevator<Graph, typename Graph::Node> Elevator;
     4.8 +    typedef Elevator<Graph, typename Graph::Node> Elevator;
     4.9      
    4.10      /// \brief Instantiates an Elevator.
    4.11      ///
    4.12 @@ -100,7 +100,7 @@
    4.13    /// directed graph. The preflow algorithms are the fastest known max
    4.14    /// flow algorithms. The current implementation use a mixture of the
    4.15    /// \e "highest label" and the \e "bound decrease" heuristics.
    4.16 -  /// The worst case time complexity of the algorithm is \f$O(n^3)\f$.
    4.17 +  /// The worst case time complexity of the algorithm is \f$O(n^2\sqrt{e})\f$.
    4.18    ///
    4.19    /// The algorithm consists from two phases. After the first phase
    4.20    /// the maximal flow value and the minimum cut can be obtained. The
    4.21 @@ -407,6 +407,7 @@
    4.22        queue.push_back(_target);
    4.23        reached.set(_target, true);
    4.24        while (!queue.empty()) {
    4.25 +	_level->initNewLevel();
    4.26  	std::vector<Node> nqueue;
    4.27  	for (int i = 0; i < int(queue.size()); ++i) {
    4.28  	  Node n = queue[i];
    4.29 @@ -863,7 +864,7 @@
    4.30      /// @}
    4.31  
    4.32      /// \name Query Functions
    4.33 -    /// The result of the %Dijkstra algorithm can be obtained using these
    4.34 +    /// The result of the %Preflow algorithm can be obtained using these
    4.35      /// functions.\n
    4.36      /// Before the use of these functions,
    4.37      /// either run() or start() must be called.