# HG changeset patch
# User kpeter
# Date 1226590144 0
# Node ID 84354c78b06851ec727f4d0d1fbabd828b48e5b1
# Parent  74520139e388af75a97744b2776d49413f85779c
Improved constructors for min cost flow classes
Removing the non-zero lower bounds is faster

diff -r 74520139e388 -r 84354c78b068 lemon/capacity_scaling.h
--- a/lemon/capacity_scaling.h	Thu Nov 13 10:54:42 2008 +0000
+++ b/lemon/capacity_scaling.h	Thu Nov 13 15:29:04 2008 +0000
@@ -254,25 +254,28 @@
                      const CapacityMap &capacity,
                      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;
+        }
       }
-      _valid_supply = sum == 0;
     }
 
     /// \brief General constructor (without lower bounds).
@@ -290,9 +293,9 @@
       _graph(graph), _lower(NULL), _capacity(capacity), _cost(cost),
       _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];
       _valid_supply = sum == 0;
@@ -316,23 +319,24 @@
                      const CostMap &cost,
                      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;
     }
@@ -356,10 +360,10 @@
       _graph(graph), _lower(NULL), _capacity(capacity), _cost(cost),
       _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;
     }
 
@@ -497,7 +501,6 @@
       }
       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,
                                         _excess, *_potential, _pred );
diff -r 74520139e388 -r 84354c78b068 lemon/cost_scaling.h
--- a/lemon/cost_scaling.h	Thu Nov 13 10:54:42 2008 +0000
+++ b/lemon/cost_scaling.h	Thu Nov 13 15:29:04 2008 +0000
@@ -200,24 +200,24 @@
                  const CapacityMap &capacity,
                  const CostMap &cost,
                  const SupplyMap &supply ) :
-      _graph(graph), _lower(&lower), _capacity(graph), _orig_cost(cost),
-      _cost(graph), _supply(graph), _flow(NULL), _local_flow(false),
+      _graph(graph), _lower(&lower), _capacity(capacity), _orig_cost(cost),
+      _cost(graph), _supply(supply), _flow(NULL), _local_flow(false),
       _potential(NULL), _local_potential(false), _res_cost(_cost),
       _res_graph(NULL), _red_cost(NULL), _excess(graph, 0)
     {
+      // Check the sum of supply values
+      Supply sum = 0;
+      for (NodeIt n(_graph); n != INVALID; ++n) sum += _supply[n];
+      _valid_supply = sum == 0;
+
       // Remove non-zero lower bounds
-      _capacity = subMap(capacity, lower);
-      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 (EdgeIt e(_graph); e != INVALID; ++e) {
+        if (lower[e] != 0) {
+          _capacity[e] -= lower[e];
+          _supply[_graph.source(e)] -= lower[e];
+          _supply[_graph.target(e)] += lower[e];
+        }
       }
-      _valid_supply = sum == 0;
     }
 
     /// \brief General constructor (without lower bounds).
@@ -261,22 +261,20 @@
                  const CostMap &cost,
                  Node s, Node t,
                  Supply flow_value ) :
-      _graph(graph), _lower(&lower), _capacity(graph), _orig_cost(cost),
-      _cost(graph), _supply(graph), _flow(NULL), _local_flow(false),
+      _graph(graph), _lower(&lower), _capacity(capacity), _orig_cost(cost),
+      _cost(graph), _supply(graph, 0), _flow(NULL), _local_flow(false),
       _potential(NULL), _local_potential(false), _res_cost(_cost),
       _res_graph(NULL), _red_cost(NULL), _excess(graph, 0)
     {
-      // Remove nonzero lower bounds
-      _capacity = subMap(capacity, lower);
-      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] =  flow_value;
+      _supply[t] = -flow_value;
+      for (EdgeIt e(_graph); e != INVALID; ++e) {
+        if (lower[e] != 0) {
+          _capacity[e] -= lower[e];
+          _supply[_graph.source(e)] -= lower[e];
+          _supply[_graph.target(e)] += lower[e];
+        }
       }
       _valid_supply = true;
     }
diff -r 74520139e388 -r 84354c78b068 lemon/cycle_canceling.h
--- a/lemon/cycle_canceling.h	Thu Nov 13 10:54:42 2008 +0000
+++ b/lemon/cycle_canceling.h	Thu Nov 13 15:29:04 2008 +0000
@@ -167,23 +167,24 @@
                     const CapacityMap &capacity,
                     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_graph(NULL),
       _res_cost(_cost)
     {
-      // Removing non-zero lower bounds
-      _capacity = subMap(capacity, lower);
+      // 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];
-        sum += (_supply[n] = s);
+      for (NodeIt n(_graph); n != INVALID; ++n) sum += _supply[n];
+      _valid_supply = sum == 0;
+
+      // Remove non-zero lower bounds
+      for (EdgeIt e(_graph); e != INVALID; ++e) {
+        if (lower[e] != 0) {
+          _capacity[e] -= lower[e];
+          _supply[_graph.source(e)] -= lower[e];
+          _supply[_graph.target(e)] += lower[e];
+        }
       }
-      _valid_supply = sum == 0;
     }
 
     /// \brief General constructor (without lower bounds).
@@ -203,7 +204,7 @@
       _potential(NULL), _local_potential(false), _res_graph(NULL),
       _res_cost(_cost)
     {
-      // 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];
       _valid_supply = sum == 0;
@@ -227,22 +228,20 @@
                     const CostMap &cost,
                     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_graph(NULL),
       _res_cost(_cost)
     {
-      // Removing non-zero lower bounds
-      _capacity = subMap(capacity, lower);
-      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] =  flow_value;
+      _supply[t] = -flow_value;
+      for (EdgeIt e(_graph); e != INVALID; ++e) {
+        if (lower[e] != 0) {
+          _capacity[e] -= lower[e];
+          _supply[_graph.source(e)] -= lower[e];
+          _supply[_graph.target(e)] += lower[e];
+        }
       }
       _valid_supply = true;
     }
diff -r 74520139e388 -r 84354c78b068 lemon/network_simplex.h
--- a/lemon/network_simplex.h	Thu Nov 13 10:54:42 2008 +0000
+++ b/lemon/network_simplex.h	Thu Nov 13 15:29:04 2008 +0000
@@ -611,32 +611,30 @@
       _local_flow(false), _local_potential(false),
       _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)
         sum += supply[n];
       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];
+          _supply[_node_ref[_graph_ref.source(e)]] -= lower[e];
+          _supply[_node_ref[_graph_ref.target(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;
       }
     }
 
@@ -661,13 +659,15 @@
       _local_flow(false), _local_potential(false),
       _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)
         sum += supply[n];
       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)
@@ -697,7 +697,7 @@
                     typename Graph::Node t,
                     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),
       _state(_graph), _red_cost(_graph, _cost, _potential),
@@ -705,26 +705,25 @@
       _local_flow(false), _local_potential(false),
       _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)
         .edgeRef(_edge_ref)
         .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];
+          _supply[_node_ref[_graph_ref.source(e)]] -= lower[e];
+          _supply[_node_ref[_graph_ref.target(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;
       }
       _valid_supply = true;
     }
@@ -755,7 +754,9 @@
       _local_flow(false), _local_potential(false),
       _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)