Changeset 2629:84354c78b068 in lemon-0.x for lemon/network_simplex.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/network_simplex.h (modified) (8 diffs)

lemon/network_simplex.h

@@ -612 +612 @@
       _node_ref(graph), _edge_ref(graph)
     {
-      // Checking the sum of supply values
+      // Check the sum of supply values
       Supply sum = 0;
       for (typename Graph::NodeIt n(_graph_ref); n != INVALID; ++n)
@@ -618 +618 @@
       if (!(_valid_supply = sum == 0)) return;
 
-      // Copying _graph_ref to _graph
+      // Copy _graph_ref to _graph
       _graph.reserveNode(countNodes(_graph_ref) + 1);
       _graph.reserveEdge(countEdges(_graph_ref) + countNodes(_graph_ref));
       copyGraph(_graph, _graph_ref)
+        .edgeMap(_capacity, capacity)
         .edgeMap(_cost, cost)
+        .nodeMap(_supply, supply)
         .nodeRef(_node_ref)
         .edgeRef(_edge_ref)
         .run();
 
-      // Removing non-zero lower bounds
+      // Remove non-zero lower bounds
       for (typename Graph::EdgeIt e(_graph_ref); e != INVALID; ++e) {
+        if (lower[e] != 0) {
         _capacity[_edge_ref[e]] = capacity[e] - lower[e];
-      }
-      for (typename Graph::NodeIt n(_graph_ref); n != INVALID; ++n) {
-        Supply s = supply[n];
-        for (typename Graph::InEdgeIt e(_graph_ref, n); e != INVALID; ++e)
-          s += lower[e];
-        for (typename Graph::OutEdgeIt e(_graph_ref, n); e != INVALID; ++e)
-          s -= lower[e];
-        _supply[_node_ref[n]] = s;
+          _supply[_node_ref[_graph_ref.source(e)]] -= lower[e];
+          _supply[_node_ref[_graph_ref.target(e)]] += lower[e];
+      }
       }
     }
@@ -662 +660 @@
       _node_ref(graph), _edge_ref(graph)
     {
-      // Checking the sum of supply values
+      // Check the sum of supply values
       Supply sum = 0;
       for (typename Graph::NodeIt n(_graph_ref); n != INVALID; ++n)
@@ -668 +666 @@
       if (!(_valid_supply = sum == 0)) return;
 
-      // Copying _graph_ref to graph
+      // Copy _graph_ref to _graph
+      _graph.reserveNode(countNodes(_graph_ref) + 1);
+      _graph.reserveEdge(countEdges(_graph_ref) + countNodes(_graph_ref));
       copyGraph(_graph, _graph_ref)
         .edgeMap(_capacity, capacity)
@@ -698 +698 @@
                     typename SupplyMap::Value flow_value ) :
       _graph(), _graph_ref(graph), _lower(&lower), _capacity(_graph),
-      _cost(_graph), _supply(_graph), _flow(_graph),
+      _cost(_graph), _supply(_graph, 0), _flow(_graph),
       _potential(_graph), _depth(_graph), _parent(_graph),
       _pred_edge(_graph), _thread(_graph), _forward(_graph),
@@ -706 +706 @@
       _node_ref(graph), _edge_ref(graph)
     {
-      // Copying _graph_ref to graph
+      // Copy _graph_ref to graph
+      _graph.reserveNode(countNodes(_graph_ref) + 1);
+      _graph.reserveEdge(countEdges(_graph_ref) + countNodes(_graph_ref));
       copyGraph(_graph, _graph_ref)
+        .edgeMap(_capacity, capacity)
         .edgeMap(_cost, cost)
         .nodeRef(_node_ref)
@@ -713 +716 @@
         .run();
 
-      // Removing non-zero lower bounds
+      // Remove non-zero lower bounds
+      _supply[_node_ref[s]] =  flow_value;
+      _supply[_node_ref[t]] = -flow_value;
       for (typename Graph::EdgeIt e(_graph_ref); e != INVALID; ++e) {
+        if (lower[e] != 0) {
         _capacity[_edge_ref[e]] = capacity[e] - lower[e];
-      }
-      for (typename Graph::NodeIt n(_graph_ref); n != INVALID; ++n) {
-        Supply sum = 0;
-        if (n == s) sum =  flow_value;
-        if (n == t) sum = -flow_value;
-        for (typename Graph::InEdgeIt e(_graph_ref, n); e != INVALID; ++e)
-          sum += lower[e];
-        for (typename Graph::OutEdgeIt e(_graph_ref, n); e != INVALID; ++e)
-          sum -= lower[e];
-        _supply[_node_ref[n]] = sum;
+          _supply[_node_ref[_graph_ref.source(e)]] -= lower[e];
+          _supply[_node_ref[_graph_ref.target(e)]] += lower[e];
+      }
       }
       _valid_supply = true;
@@ -756 +755 @@
       _node_ref(graph), _edge_ref(graph)
     {
-      // Copying _graph_ref to graph
+      // Copy _graph_ref to graph
+      _graph.reserveNode(countNodes(_graph_ref) + 1);
+      _graph.reserveEdge(countEdges(_graph_ref) + countNodes(_graph_ref));
       copyGraph(_graph, _graph_ref)
         .edgeMap(_capacity, capacity)