Changeset 2588:4d3bc1d04c1d in lemon-0.x for lemon/capacity_scaling.h

Timestamp:

02/29/08 16:57:52 (16 years ago)

Author:

Peter Kovacs

Branch:

default

Phase:

public

Convert:

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

Message:

Small improvements in min cost flow files.

File:

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

lemon/capacity_scaling.h

@@ -26 +26 @@
 
 #include <vector>
-
-#include <lemon/graph_adaptor.h>
 #include <lemon/bin_heap.h>
 
@@ -91 +89 @@
     class ResidualDijkstra
     {
-      typedef typename Graph::template NodeMap<Cost> CostNodeMap;
-      typedef typename Graph::template NodeMap<Edge> PredMap;
-
       typedef typename Graph::template NodeMap<int> HeapCrossRef;
       typedef BinHeap<Cost, HeapCrossRef> Heap;
@@ -110 +105 @@
 
       // The distance map
-      CostNodeMap _dist;
+      PotentialMap _dist;
       // The pred edge map
       PredMap &_pred;
@@ -132 +127 @@
 
       /// Runs the algorithm from the given source node.
-      Node run(Node s, Capacity delta) {
+      Node run(Node s, Capacity delta = 1) {
         HeapCrossRef heap_cross_ref(_graph, Heap::PRE_HEAP);
         Heap heap(heap_cross_ref);
@@ -455 +450 @@
     }
 
-    /// \brief Returns the flow on the edge.
-    ///
-    /// Returns the flow on the edge.
+    /// \brief Returns the flow on the given edge.
+    ///
+    /// Returns the flow on the given edge.
     ///
     /// \pre \ref run() must be called before using this function.
@@ -464 +459 @@
     }
 
-    /// \brief Returns the potential of the node.
-    ///
-    /// Returns the potential of the node.
+    /// \brief Returns the potential of the given node.
+    ///
+    /// Returns the potential of the given node.
     ///
     /// \pre \ref run() must be called before using this function.
@@ -518 +513 @@
           if (-_supply[n] > max_dem) max_dem = -_supply[n];
         }
-        if (max_dem < max_sup) max_sup = max_dem;
+        Capacity max_cap = 0;
+        for (EdgeIt e(_graph); e != INVALID; ++e) {
+          if (_capacity[e] > max_cap) max_cap = _capacity[e];
+        }
+        max_sup = std::min(std::min(max_sup, max_dem), max_cap);
         _phase_num = 0;
         for (_delta = 1; 2 * _delta <= max_sup; _delta *= 2)
@@ -596 +595 @@
 
           // Augmenting along a shortest path from s to t.
-          Capacity d = _excess[s] < -_excess[t] ? _excess[s] : -_excess[t];
+          Capacity d = std::min(_excess[s], -_excess[t]);
           Node u = t;
           Edge e;
@@ -658 +657 @@
         // Running Dijkstra
         s = _excess_nodes[next_node];
-        if ((t = _dijkstra->run(s, 1)) == INVALID)
-          return false;
+        if ((t = _dijkstra->run(s)) == INVALID) break;
 
         // Augmenting along a shortest path from s to t
-        Capacity d = _excess[s] < -_excess[t] ? _excess[s] : -_excess[t];
+        Capacity d = std::min(_excess[s], -_excess[t]);
         Node u = t;
         Edge e;
-        while ((e = _pred[u]) != INVALID) {
-          Capacity rc;
-          if (u == _graph.target(e)) {
-            rc = _res_cap[e];
-            u = _graph.source(e);
-          } else {
-            rc = (*_flow)[e];
-            u = _graph.target(e);
-          }
-          if (rc < d) d = rc;
+        if (d > 1) {
+          while ((e = _pred[u]) != INVALID) {
+            Capacity rc;
+            if (u == _graph.target(e)) {
+              rc = _res_cap[e];
+              u = _graph.source(e);
+            } else {
+              rc = (*_flow)[e];
+              u = _graph.target(e);
+            }
+            if (rc < d) d = rc;
+          }
         }
         u = t;