Changeset 2522:616c019215c4 in lemon-0.x for lemon/preflow.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/preflow.h (modified) (4 diffs)

lemon/preflow.h

@@ -73 +73 @@
     /// \sa Elevator
     /// \sa LinkedElevator
-    typedef LinkedElevator<Graph, typename Graph::Node> Elevator;
+    typedef Elevator<Graph, typename Graph::Node> Elevator;
     
     /// \brief Instantiates an Elevator.
@@ -101 +101 @@
   /// flow algorithms. The current implementation use a mixture of the
   /// \e "highest label" and the \e "bound decrease" heuristics.
-  /// The worst case time complexity of the algorithm is \f$O(n^3)\f$.
+  /// The worst case time complexity of the algorithm is \f$O(n^2\sqrt{e})\f$.
   ///
   /// The algorithm consists from two phases. After the first phase
@@ -408 +408 @@
       reached.set(_target, true);
       while (!queue.empty()) {
+        _level->initNewLevel();
         std::vector<Node> nqueue;
         for (int i = 0; i < int(queue.size()); ++i) {
@@ -864 +865 @@
 
     /// \name Query Functions
-    /// The result of the %Dijkstra algorithm can be obtained using these
+    /// The result of the %Preflow algorithm can be obtained using these
     /// functions.\n
     /// Before the use of these functions,