Changeset 2629:84354c78b068 in lemon-0.x for lemon/capacity_scaling.h

Timestamp:

11/13/08 16:29:04 (15 years ago)

Author:

Peter Kovacs

Branch:

default

Phase:

public

Convert:

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

Message:

Improved constructors for min cost flow classes
Removing the non-zero lower bounds is faster

File:

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

lemon/capacity_scaling.h

@@ -255 +255 @@
                      const CostMap &cost,
                      const SupplyMap &supply ) :
-      _graph(graph), _lower(&lower), _capacity(graph), _cost(cost),
-      _supply(graph), _flow(NULL), _local_flow(false),
+      _graph(graph), _lower(&lower), _capacity(capacity), _cost(cost),
+      _supply(supply), _flow(NULL), _local_flow(false),
       _potential(NULL), _local_potential(false),
-      _res_cap(graph), _excess(graph), _pred(graph), _dijkstra(NULL)
+      _res_cap(capacity), _excess(supply), _pred(graph), _dijkstra(NULL)
     {
-      // Removing non-zero lower bounds
-      _capacity = subMap(capacity, lower);
-      _res_cap = _capacity;
+      // Check the sum of supply values
       Supply sum = 0;
-      for (NodeIt n(_graph); n != INVALID; ++n) {
-        Supply s = supply[n];
-        for (InEdgeIt e(_graph, n); e != INVALID; ++e)
-          s += lower[e];
-        for (OutEdgeIt e(_graph, n); e != INVALID; ++e)
-          s -= lower[e];
-        _supply[n] = s;
-        sum += s;
-      }
+      for (NodeIt n(_graph); n != INVALID; ++n) sum += _supply[n];
       _valid_supply = sum == 0;
+
+      // Remove non-zero lower bounds
+      typename LowerMap::Value lcap;
+      for (EdgeIt e(_graph); e != INVALID; ++e) {
+        if ((lcap = lower[e]) != 0) {
+          _capacity[e] -= lcap;
+          _res_cap[e] -= lcap;
+          _supply[_graph.source(e)] -= lcap;
+          _supply[_graph.target(e)] += lcap;
+          _excess[_graph.source(e)] -= lcap;
+          _excess[_graph.target(e)] += lcap;
+        }
+      }
     }
 
@@ -291 +294 @@
       _supply(supply), _flow(NULL), _local_flow(false),
       _potential(NULL), _local_potential(false),
-      _res_cap(capacity), _excess(graph), _pred(graph), _dijkstra(NULL)
+      _res_cap(capacity), _excess(supply), _pred(graph), _dijkstra(NULL)
     {
-      // Checking the sum of supply values
+      // Check the sum of supply values
       Supply sum = 0;
       for (NodeIt n(_graph); n != INVALID; ++n) sum += _supply[n];
@@ -317 +320 @@
                      Node s, Node t,
                      Supply flow_value ) :
-      _graph(graph), _lower(&lower), _capacity(graph), _cost(cost),
-      _supply(graph), _flow(NULL), _local_flow(false),
+      _graph(graph), _lower(&lower), _capacity(capacity), _cost(cost),
+      _supply(graph, 0), _flow(NULL), _local_flow(false),
       _potential(NULL), _local_potential(false),
-      _res_cap(graph), _excess(graph), _pred(graph), _dijkstra(NULL)
+      _res_cap(capacity), _excess(graph, 0), _pred(graph), _dijkstra(NULL)
     {
-      // Removing non-zero lower bounds
-      _capacity = subMap(capacity, lower);
-      _res_cap = _capacity;
-      for (NodeIt n(_graph); n != INVALID; ++n) {
-        Supply sum = 0;
-        if (n == s) sum =  flow_value;
-        if (n == t) sum = -flow_value;
-        for (InEdgeIt e(_graph, n); e != INVALID; ++e)
-          sum += lower[e];
-        for (OutEdgeIt e(_graph, n); e != INVALID; ++e)
-          sum -= lower[e];
-        _supply[n] = sum;
+      // Remove non-zero lower bounds
+      _supply[s] = _excess[s] =  flow_value;
+      _supply[t] = _excess[t] = -flow_value;
+      typename LowerMap::Value lcap;
+      for (EdgeIt e(_graph); e != INVALID; ++e) {
+        if ((lcap = lower[e]) != 0) {
+          _capacity[e] -= lcap;
+          _res_cap[e] -= lcap;
+          _supply[_graph.source(e)] -= lcap;
+          _supply[_graph.target(e)] += lcap;
+          _excess[_graph.source(e)] -= lcap;
+          _excess[_graph.target(e)] += lcap;
+        }
       }
       _valid_supply = true;
@@ -357 +361 @@
       _supply(graph, 0), _flow(NULL), _local_flow(false),
       _potential(NULL), _local_potential(false),
-      _res_cap(capacity), _excess(graph), _pred(graph), _dijkstra(NULL)
+      _res_cap(capacity), _excess(graph, 0), _pred(graph), _dijkstra(NULL)
     {
-      _supply[s] =  flow_value;
-      _supply[t] = -flow_value;
+      _supply[s] = _excess[s] =  flow_value;
+      _supply[t] = _excess[t] = -flow_value;
       _valid_supply = true;
     }
@@ -498 +502 @@
       for (EdgeIt e(_graph); e != INVALID; ++e) (*_flow)[e] = 0;
       for (NodeIt n(_graph); n != INVALID; ++n) (*_potential)[n] = 0;
-      _excess = _supply;
 
       _dijkstra = new ResidualDijkstra( _graph, *_flow, _res_cap, _cost,