Changeset 2457:8c791ee69a45 in lemon-0.x for lemon/capacity_scaling.h

Timestamp:

06/15/07 16:36:24 (17 years ago)

Author:

Balazs Dezso

Branch:

default

Phase:

public

Convert:

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

Message:

Improvments in min cost flow algorithms

• improved cycle cancelling

File:

• lemon/capacity_scaling.h (modified) (10 diffs)

lemon/capacity_scaling.h

@@ -32 +32 @@
 #define WITH_SCALING
 
+//#define _DEBUG_ITER_
+
 namespace lemon {
 
@@ -38 +40 @@
 
   /// \brief Implementation of the capacity scaling version of the
-  /// succesive shortest path algorithm for finding a minimum cost flow.
+  /// successive shortest path algorithm for finding a minimum cost flow.
   ///
   /// \ref lemon::CapacityScaling "CapacityScaling" implements a
@@ -299 +301 @@
     /// \brief Map for identifing deficit nodes.
     DeficitBoolMap delta_deficit;
+
+    /// \brief The deficit nodes.
+    std::vector<ResNode> deficit_nodes;
 
 #else //WITHOUT_CAPACITY_SCALING
@@ -511 +516 @@
     }
 
-    /// \brief Runs the successive shortest path algorithm.
-    ///
-    /// Runs the successive shortest path algorithm.
+    /// \brief Runs the algorithm.
+    ///
+    /// Runs the algorithm.
     ///
     /// \return \c true if a feasible flow can be found.
@@ -532 +537 @@
 #ifdef WITH_SCALING
       // Initilaizing delta value
-      Capacity max_cap = 0;
-      for (EdgeIt e(graph); e != INVALID; ++e) {
-        if (capacity[e] > max_cap) max_cap = capacity[e];
-      }
-      for (delta = 1; 2 * delta < max_cap; delta *= 2) ;
+      Supply max_sup = 0, max_dem = 0;
+      for (NodeIt n(graph); n != INVALID; ++n) {
+        if (supply[n] >  max_sup) max_sup =  supply[n];
+        if (supply[n] < -max_dem) max_dem = -supply[n];
+      }
+      if (max_dem < max_sup) max_sup = max_dem;
+      for (delta = 1; 2 * delta < max_sup; delta *= 2) ;
 #endif
       return true;
@@ -547 +554 @@
       typedef typename DeltaResGraph::EdgeIt DeltaResEdgeIt;
       typedef typename DeltaResGraph::Edge DeltaResEdge;
+#ifdef _DEBUG_ITER_
+      int dijk_num = 0;
+#endif
 
       // Processing capacity scaling phases
@@ -565 +575 @@
         // Finding excess nodes
         excess_nodes.clear();
+        deficit_nodes.clear();
         for (ResNodeIt n(res_graph); n != INVALID; ++n) {
-          if (imbalance[n] >= delta) excess_nodes.push_back(n);
+          if (imbalance[n] >=  delta) excess_nodes.push_back(n);
+          if (imbalance[n] <= -delta) deficit_nodes.push_back(n);
         }
         next_node = 0;
 
-        // Finding successive shortest paths
+        // Finding shortest paths
         while (next_node < excess_nodes.size()) {
+          // Checking deficit nodes
+          if (delta > 1) {
+            bool delta_def = false;
+            for (int i = 0; i < deficit_nodes.size(); ++i) {
+              if (imbalance[deficit_nodes[i]] <= -delta) {
+                delta_def = true;
+                break;
+              }
+            }
+            if (!delta_def) break;
+          }
+
           // Running Dijkstra
           s = excess_nodes[next_node];
@@ -577 +601 @@
           dijkstra.init();
           dijkstra.addSource(s);
+#ifdef _DEBUG_ITER_
+          ++dijk_num;
+#endif
           if ((t = dijkstra.start(delta_deficit)) == INVALID) {
             if (delta > 1) {
@@ -609 +636 @@
         }
       }
+#ifdef _DEBUG_ITER_
+      std::cout << "Cost Scaling algorithm finished with running Dijkstra algorithm "
+        << dijk_num << " times." << std::endl;
+#endif
 
       // Handling nonzero lower bounds
@@ -629 +660 @@
       next_node = 0;
 
-      // Finding successive shortest paths
+      // Finding shortest paths
       ResNode s, t;
       while ( imbalance[excess_nodes[next_node]] > 0 ||