1.1 --- a/lemon/network_simplex.h	Thu Nov 13 10:54:42 2008 +0000
     1.2 +++ b/lemon/network_simplex.h	Thu Nov 13 15:29:04 2008 +0000
     1.3 @@ -611,32 +611,30 @@
     1.4        _local_flow(false), _local_potential(false),
     1.5        _node_ref(graph), _edge_ref(graph)
     1.6      {
     1.7 -      // Checking the sum of supply values
     1.8 +      // Check the sum of supply values
     1.9        Supply sum = 0;
    1.10        for (typename Graph::NodeIt n(_graph_ref); n != INVALID; ++n)
    1.11          sum += supply[n];
    1.12        if (!(_valid_supply = sum == 0)) return;
    1.13  
    1.14 -      // Copying _graph_ref to _graph
    1.15 +      // Copy _graph_ref to _graph
    1.16        _graph.reserveNode(countNodes(_graph_ref) + 1);
    1.17        _graph.reserveEdge(countEdges(_graph_ref) + countNodes(_graph_ref));
    1.18        copyGraph(_graph, _graph_ref)
    1.19 +        .edgeMap(_capacity, capacity)
    1.20          .edgeMap(_cost, cost)
    1.21 +        .nodeMap(_supply, supply)
    1.22          .nodeRef(_node_ref)
    1.23          .edgeRef(_edge_ref)
    1.24          .run();
    1.25  
    1.26 -      // Removing non-zero lower bounds
    1.27 +      // Remove non-zero lower bounds
    1.28        for (typename Graph::EdgeIt e(_graph_ref); e != INVALID; ++e) {
    1.29 +        if (lower[e] != 0) {
    1.30          _capacity[_edge_ref[e]] = capacity[e] - lower[e];
    1.31 +          _supply[_node_ref[_graph_ref.source(e)]] -= lower[e];
    1.32 +          _supply[_node_ref[_graph_ref.target(e)]] += lower[e];
    1.33        }
    1.34 -      for (typename Graph::NodeIt n(_graph_ref); n != INVALID; ++n) {
    1.35 -        Supply s = supply[n];
    1.36 -        for (typename Graph::InEdgeIt e(_graph_ref, n); e != INVALID; ++e)
    1.37 -          s += lower[e];
    1.38 -        for (typename Graph::OutEdgeIt e(_graph_ref, n); e != INVALID; ++e)
    1.39 -          s -= lower[e];
    1.40 -        _supply[_node_ref[n]] = s;
    1.41        }
    1.42      }
    1.43  
    1.44 @@ -661,13 +659,15 @@
    1.45        _local_flow(false), _local_potential(false),
    1.46        _node_ref(graph), _edge_ref(graph)
    1.47      {
    1.48 -      // Checking the sum of supply values
    1.49 +      // Check the sum of supply values
    1.50        Supply sum = 0;
    1.51        for (typename Graph::NodeIt n(_graph_ref); n != INVALID; ++n)
    1.52          sum += supply[n];
    1.53        if (!(_valid_supply = sum == 0)) return;
    1.54  
    1.55 -      // Copying _graph_ref to graph
    1.56 +      // Copy _graph_ref to _graph
    1.57 +      _graph.reserveNode(countNodes(_graph_ref) + 1);
    1.58 +      _graph.reserveEdge(countEdges(_graph_ref) + countNodes(_graph_ref));
    1.59        copyGraph(_graph, _graph_ref)
    1.60          .edgeMap(_capacity, capacity)
    1.61          .edgeMap(_cost, cost)
    1.62 @@ -697,7 +697,7 @@
    1.63                      typename Graph::Node t,
    1.64                      typename SupplyMap::Value flow_value ) :
    1.65        _graph(), _graph_ref(graph), _lower(&lower), _capacity(_graph),
    1.66 -      _cost(_graph), _supply(_graph), _flow(_graph),
    1.67 +      _cost(_graph), _supply(_graph, 0), _flow(_graph),
    1.68        _potential(_graph), _depth(_graph), _parent(_graph),
    1.69        _pred_edge(_graph), _thread(_graph), _forward(_graph),
    1.70        _state(_graph), _red_cost(_graph, _cost, _potential),
    1.71 @@ -705,26 +705,25 @@
    1.72        _local_flow(false), _local_potential(false),
    1.73        _node_ref(graph), _edge_ref(graph)
    1.74      {
    1.75 -      // Copying _graph_ref to graph
    1.76 +      // Copy _graph_ref to graph
    1.77 +      _graph.reserveNode(countNodes(_graph_ref) + 1);
    1.78 +      _graph.reserveEdge(countEdges(_graph_ref) + countNodes(_graph_ref));
    1.79        copyGraph(_graph, _graph_ref)
    1.80 +        .edgeMap(_capacity, capacity)
    1.81          .edgeMap(_cost, cost)
    1.82          .nodeRef(_node_ref)
    1.83          .edgeRef(_edge_ref)
    1.84          .run();
    1.85  
    1.86 -      // Removing non-zero lower bounds
    1.87 +      // Remove non-zero lower bounds
    1.88 +      _supply[_node_ref[s]] =  flow_value;
    1.89 +      _supply[_node_ref[t]] = -flow_value;
    1.90        for (typename Graph::EdgeIt e(_graph_ref); e != INVALID; ++e) {
    1.91 +        if (lower[e] != 0) {
    1.92          _capacity[_edge_ref[e]] = capacity[e] - lower[e];
    1.93 +          _supply[_node_ref[_graph_ref.source(e)]] -= lower[e];
    1.94 +          _supply[_node_ref[_graph_ref.target(e)]] += lower[e];
    1.95        }
    1.96 -      for (typename Graph::NodeIt n(_graph_ref); n != INVALID; ++n) {
    1.97 -        Supply sum = 0;
    1.98 -        if (n == s) sum =  flow_value;
    1.99 -        if (n == t) sum = -flow_value;
   1.100 -        for (typename Graph::InEdgeIt e(_graph_ref, n); e != INVALID; ++e)
   1.101 -          sum += lower[e];
   1.102 -        for (typename Graph::OutEdgeIt e(_graph_ref, n); e != INVALID; ++e)
   1.103 -          sum -= lower[e];
   1.104 -        _supply[_node_ref[n]] = sum;
   1.105        }
   1.106        _valid_supply = true;
   1.107      }
   1.108 @@ -755,7 +754,9 @@
   1.109        _local_flow(false), _local_potential(false),
   1.110        _node_ref(graph), _edge_ref(graph)
   1.111      {
   1.112 -      // Copying _graph_ref to graph
   1.113 +      // Copy _graph_ref to graph
   1.114 +      _graph.reserveNode(countNodes(_graph_ref) + 1);
   1.115 +      _graph.reserveEdge(countEdges(_graph_ref) + countNodes(_graph_ref));
   1.116        copyGraph(_graph, _graph_ref)
   1.117          .edgeMap(_capacity, capacity)
   1.118          .edgeMap(_cost, cost)