Changeset 2522:616c019215c4 in lemon-0.x for lemon/goldberg_tarjan.h

Timestamp:

11/27/07 16:41:43 (16 years ago)

Author:

Balazs Dezso

Branch:

default

Phase:

public

Convert:

svn:c9d7d8f5-90d6-0310-b91f-818b3a526b0e/lemon/trunk@3398

Message:

Performance bug in Preflow
The initial relabeling moved each node to the lowest level
Doc bug fix

File:

• lemon/goldberg_tarjan.h (modified) (2 diffs)

lemon/goldberg_tarjan.h

@@ -104 +104 @@
   /// DynamicTree "dynamic tree" data structure of Sleator and Tarjan.
   /// 
-  /// The original preflow algorithm with \e "highest label" or \e
-  /// FIFO heuristic has \f$O(n^3)\f$ time complexity. The current
-  /// algorithm improved this complexity to
-  /// \f$O(nm\log(\frac{n^2}{m}))\f$. The algorithm builds limited
-  /// size dynamic trees on the residual graph, which can be used to
-  /// make multilevel push operations and gives a better bound on the
-  /// number of non-saturating pushes.
+  /// The original preflow algorithm with \e highest \e label
+  /// heuristic has \f$O(n^2\sqrt{e})\f$ or with \e FIFO heuristic has
+  /// \f$O(n^3)\f$ time complexity. The current algorithm improved
+  /// this complexity to \f$O(nm\log(\frac{n^2}{m}))\f$. The algorithm
+  /// builds limited size dynamic trees on the residual graph, which
+  /// can be used to make multilevel push operations and gives a
+  /// better bound on the number of non-saturating pushes.
   ///
   /// \param Graph The directed graph type the algorithm runs on.
@@ -966 +966 @@
     /// @}
 
-    /// \name Query Functions
-    /// The result of the %Dijkstra algorithm can be obtained using these
-    /// functions.\n
-    /// Before the use of these functions,
-    /// either run() or start() must be called.
+    /// \name Query Functions 
+    /// The result of the Goldberg-Tarjan algorithm can be obtained
+    /// using these functions.
+    /// \n
+    /// Before the use of these functions, either run() or start() must
+    /// be called.
     
     ///@{