1.1 --- a/lemon/capacity_scaling.h	Thu Nov 13 10:54:42 2008 +0000
     1.2 +++ b/lemon/capacity_scaling.h	Thu Nov 13 15:29:04 2008 +0000
     1.3 @@ -254,25 +254,28 @@
     1.4                       const CapacityMap &capacity,
     1.5                       const CostMap &cost,
     1.6                       const SupplyMap &supply ) :
     1.7 -      _graph(graph), _lower(&lower), _capacity(graph), _cost(cost),
     1.8 -      _supply(graph), _flow(NULL), _local_flow(false),
     1.9 +      _graph(graph), _lower(&lower), _capacity(capacity), _cost(cost),
    1.10 +      _supply(supply), _flow(NULL), _local_flow(false),
    1.11        _potential(NULL), _local_potential(false),
    1.12 -      _res_cap(graph), _excess(graph), _pred(graph), _dijkstra(NULL)
    1.13 +      _res_cap(capacity), _excess(supply), _pred(graph), _dijkstra(NULL)
    1.14      {
    1.15 -      // Removing non-zero lower bounds
    1.16 -      _capacity = subMap(capacity, lower);
    1.17 -      _res_cap = _capacity;
    1.18 +      // Check the sum of supply values
    1.19        Supply sum = 0;
    1.20 -      for (NodeIt n(_graph); n != INVALID; ++n) {
    1.21 -        Supply s = supply[n];
    1.22 -        for (InEdgeIt e(_graph, n); e != INVALID; ++e)
    1.23 -          s += lower[e];
    1.24 -        for (OutEdgeIt e(_graph, n); e != INVALID; ++e)
    1.25 -          s -= lower[e];
    1.26 -        _supply[n] = s;
    1.27 -        sum += s;
    1.28 +      for (NodeIt n(_graph); n != INVALID; ++n) sum += _supply[n];
    1.29 +      _valid_supply = sum == 0;
    1.30 +
    1.31 +      // Remove non-zero lower bounds
    1.32 +      typename LowerMap::Value lcap;
    1.33 +      for (EdgeIt e(_graph); e != INVALID; ++e) {
    1.34 +        if ((lcap = lower[e]) != 0) {
    1.35 +          _capacity[e] -= lcap;
    1.36 +          _res_cap[e] -= lcap;
    1.37 +          _supply[_graph.source(e)] -= lcap;
    1.38 +          _supply[_graph.target(e)] += lcap;
    1.39 +          _excess[_graph.source(e)] -= lcap;
    1.40 +          _excess[_graph.target(e)] += lcap;
    1.41 +        }
    1.42        }
    1.43 -      _valid_supply = sum == 0;
    1.44      }
    1.45  
    1.46      /// \brief General constructor (without lower bounds).
    1.47 @@ -290,9 +293,9 @@
    1.48        _graph(graph), _lower(NULL), _capacity(capacity), _cost(cost),
    1.49        _supply(supply), _flow(NULL), _local_flow(false),
    1.50        _potential(NULL), _local_potential(false),
    1.51 -      _res_cap(capacity), _excess(graph), _pred(graph), _dijkstra(NULL)
    1.52 +      _res_cap(capacity), _excess(supply), _pred(graph), _dijkstra(NULL)
    1.53      {
    1.54 -      // Checking the sum of supply values
    1.55 +      // Check the sum of supply values
    1.56        Supply sum = 0;
    1.57        for (NodeIt n(_graph); n != INVALID; ++n) sum += _supply[n];
    1.58        _valid_supply = sum == 0;
    1.59 @@ -316,23 +319,24 @@
    1.60                       const CostMap &cost,
    1.61                       Node s, Node t,
    1.62                       Supply flow_value ) :
    1.63 -      _graph(graph), _lower(&lower), _capacity(graph), _cost(cost),
    1.64 -      _supply(graph), _flow(NULL), _local_flow(false),
    1.65 +      _graph(graph), _lower(&lower), _capacity(capacity), _cost(cost),
    1.66 +      _supply(graph, 0), _flow(NULL), _local_flow(false),
    1.67        _potential(NULL), _local_potential(false),
    1.68 -      _res_cap(graph), _excess(graph), _pred(graph), _dijkstra(NULL)
    1.69 +      _res_cap(capacity), _excess(graph, 0), _pred(graph), _dijkstra(NULL)
    1.70      {
    1.71 -      // Removing non-zero lower bounds
    1.72 -      _capacity = subMap(capacity, lower);
    1.73 -      _res_cap = _capacity;
    1.74 -      for (NodeIt n(_graph); n != INVALID; ++n) {
    1.75 -        Supply sum = 0;
    1.76 -        if (n == s) sum =  flow_value;
    1.77 -        if (n == t) sum = -flow_value;
    1.78 -        for (InEdgeIt e(_graph, n); e != INVALID; ++e)
    1.79 -          sum += lower[e];
    1.80 -        for (OutEdgeIt e(_graph, n); e != INVALID; ++e)
    1.81 -          sum -= lower[e];
    1.82 -        _supply[n] = sum;
    1.83 +      // Remove non-zero lower bounds
    1.84 +      _supply[s] = _excess[s] =  flow_value;
    1.85 +      _supply[t] = _excess[t] = -flow_value;
    1.86 +      typename LowerMap::Value lcap;
    1.87 +      for (EdgeIt e(_graph); e != INVALID; ++e) {
    1.88 +        if ((lcap = lower[e]) != 0) {
    1.89 +          _capacity[e] -= lcap;
    1.90 +          _res_cap[e] -= lcap;
    1.91 +          _supply[_graph.source(e)] -= lcap;
    1.92 +          _supply[_graph.target(e)] += lcap;
    1.93 +          _excess[_graph.source(e)] -= lcap;
    1.94 +          _excess[_graph.target(e)] += lcap;
    1.95 +        }
    1.96        }
    1.97        _valid_supply = true;
    1.98      }
    1.99 @@ -356,10 +360,10 @@
   1.100        _graph(graph), _lower(NULL), _capacity(capacity), _cost(cost),
   1.101        _supply(graph, 0), _flow(NULL), _local_flow(false),
   1.102        _potential(NULL), _local_potential(false),
   1.103 -      _res_cap(capacity), _excess(graph), _pred(graph), _dijkstra(NULL)
   1.104 +      _res_cap(capacity), _excess(graph, 0), _pred(graph), _dijkstra(NULL)
   1.105      {
   1.106 -      _supply[s] =  flow_value;
   1.107 -      _supply[t] = -flow_value;
   1.108 +      _supply[s] = _excess[s] =  flow_value;
   1.109 +      _supply[t] = _excess[t] = -flow_value;
   1.110        _valid_supply = true;
   1.111      }
   1.112  
   1.113 @@ -497,7 +501,6 @@
   1.114        }
   1.115        for (EdgeIt e(_graph); e != INVALID; ++e) (*_flow)[e] = 0;
   1.116        for (NodeIt n(_graph); n != INVALID; ++n) (*_potential)[n] = 0;
   1.117 -      _excess = _supply;
   1.118  
   1.119        _dijkstra = new ResidualDijkstra( _graph, *_flow, _res_cap, _cost,
   1.120                                          _excess, *_potential, _pred );

     2.1 --- a/lemon/cost_scaling.h	Thu Nov 13 10:54:42 2008 +0000
     2.2 +++ b/lemon/cost_scaling.h	Thu Nov 13 15:29:04 2008 +0000
     2.3 @@ -200,24 +200,24 @@
     2.4                   const CapacityMap &capacity,
     2.5                   const CostMap &cost,
     2.6                   const SupplyMap &supply ) :
     2.7 -      _graph(graph), _lower(&lower), _capacity(graph), _orig_cost(cost),
     2.8 -      _cost(graph), _supply(graph), _flow(NULL), _local_flow(false),
     2.9 +      _graph(graph), _lower(&lower), _capacity(capacity), _orig_cost(cost),
    2.10 +      _cost(graph), _supply(supply), _flow(NULL), _local_flow(false),
    2.11        _potential(NULL), _local_potential(false), _res_cost(_cost),
    2.12        _res_graph(NULL), _red_cost(NULL), _excess(graph, 0)
    2.13      {
    2.14 +      // Check the sum of supply values
    2.15 +      Supply sum = 0;
    2.16 +      for (NodeIt n(_graph); n != INVALID; ++n) sum += _supply[n];
    2.17 +      _valid_supply = sum == 0;
    2.18 +
    2.19        // Remove non-zero lower bounds
    2.20 -      _capacity = subMap(capacity, lower);
    2.21 -      Supply sum = 0;
    2.22 -      for (NodeIt n(_graph); n != INVALID; ++n) {
    2.23 -        Supply s = supply[n];
    2.24 -        for (InEdgeIt e(_graph, n); e != INVALID; ++e)
    2.25 -          s += lower[e];
    2.26 -        for (OutEdgeIt e(_graph, n); e != INVALID; ++e)
    2.27 -          s -= lower[e];
    2.28 -        _supply[n] = s;
    2.29 -        sum += s;
    2.30 +      for (EdgeIt e(_graph); e != INVALID; ++e) {
    2.31 +        if (lower[e] != 0) {
    2.32 +          _capacity[e] -= lower[e];
    2.33 +          _supply[_graph.source(e)] -= lower[e];
    2.34 +          _supply[_graph.target(e)] += lower[e];
    2.35 +        }
    2.36        }
    2.37 -      _valid_supply = sum == 0;
    2.38      }
    2.39  
    2.40      /// \brief General constructor (without lower bounds).
    2.41 @@ -261,22 +261,20 @@
    2.42                   const CostMap &cost,
    2.43                   Node s, Node t,
    2.44                   Supply flow_value ) :
    2.45 -      _graph(graph), _lower(&lower), _capacity(graph), _orig_cost(cost),
    2.46 -      _cost(graph), _supply(graph), _flow(NULL), _local_flow(false),
    2.47 +      _graph(graph), _lower(&lower), _capacity(capacity), _orig_cost(cost),
    2.48 +      _cost(graph), _supply(graph, 0), _flow(NULL), _local_flow(false),
    2.49        _potential(NULL), _local_potential(false), _res_cost(_cost),
    2.50        _res_graph(NULL), _red_cost(NULL), _excess(graph, 0)
    2.51      {
    2.52 -      // Remove nonzero lower bounds
    2.53 -      _capacity = subMap(capacity, lower);
    2.54 -      for (NodeIt n(_graph); n != INVALID; ++n) {
    2.55 -        Supply sum = 0;
    2.56 -        if (n == s) sum =  flow_value;
    2.57 -        if (n == t) sum = -flow_value;
    2.58 -        for (InEdgeIt e(_graph, n); e != INVALID; ++e)
    2.59 -          sum += lower[e];
    2.60 -        for (OutEdgeIt e(_graph, n); e != INVALID; ++e)
    2.61 -          sum -= lower[e];
    2.62 -        _supply[n] = sum;
    2.63 +      // Remove non-zero lower bounds
    2.64 +      _supply[s] =  flow_value;
    2.65 +      _supply[t] = -flow_value;
    2.66 +      for (EdgeIt e(_graph); e != INVALID; ++e) {
    2.67 +        if (lower[e] != 0) {
    2.68 +          _capacity[e] -= lower[e];
    2.69 +          _supply[_graph.source(e)] -= lower[e];
    2.70 +          _supply[_graph.target(e)] += lower[e];
    2.71 +        }
    2.72        }
    2.73        _valid_supply = true;
    2.74      }

     3.1 --- a/lemon/cycle_canceling.h	Thu Nov 13 10:54:42 2008 +0000
     3.2 +++ b/lemon/cycle_canceling.h	Thu Nov 13 15:29:04 2008 +0000
     3.3 @@ -167,23 +167,24 @@
     3.4                      const CapacityMap &capacity,
     3.5                      const CostMap &cost,
     3.6                      const SupplyMap &supply ) :
     3.7 -      _graph(graph), _lower(&lower), _capacity(graph), _cost(cost),
     3.8 -      _supply(graph), _flow(NULL), _local_flow(false),
     3.9 +      _graph(graph), _lower(&lower), _capacity(capacity), _cost(cost),
    3.10 +      _supply(supply), _flow(NULL), _local_flow(false),
    3.11        _potential(NULL), _local_potential(false), _res_graph(NULL),
    3.12        _res_cost(_cost)
    3.13      {
    3.14 -      // Removing non-zero lower bounds
    3.15 -      _capacity = subMap(capacity, lower);
    3.16 +      // Check the sum of supply values
    3.17        Supply sum = 0;
    3.18 -      for (NodeIt n(_graph); n != INVALID; ++n) {
    3.19 -        Supply s = supply[n];
    3.20 -        for (InEdgeIt e(_graph, n); e != INVALID; ++e)
    3.21 -          s += lower[e];
    3.22 -        for (OutEdgeIt e(_graph, n); e != INVALID; ++e)
    3.23 -          s -= lower[e];
    3.24 -        sum += (_supply[n] = s);
    3.25 +      for (NodeIt n(_graph); n != INVALID; ++n) sum += _supply[n];
    3.26 +      _valid_supply = sum == 0;
    3.27 +
    3.28 +      // Remove non-zero lower bounds
    3.29 +      for (EdgeIt e(_graph); e != INVALID; ++e) {
    3.30 +        if (lower[e] != 0) {
    3.31 +          _capacity[e] -= lower[e];
    3.32 +          _supply[_graph.source(e)] -= lower[e];
    3.33 +          _supply[_graph.target(e)] += lower[e];
    3.34 +        }
    3.35        }
    3.36 -      _valid_supply = sum == 0;
    3.37      }
    3.38  
    3.39      /// \brief General constructor (without lower bounds).
    3.40 @@ -203,7 +204,7 @@
    3.41        _potential(NULL), _local_potential(false), _res_graph(NULL),
    3.42        _res_cost(_cost)
    3.43      {
    3.44 -      // Checking the sum of supply values
    3.45 +      // Check the sum of supply values
    3.46        Supply sum = 0;
    3.47        for (NodeIt n(_graph); n != INVALID; ++n) sum += _supply[n];
    3.48        _valid_supply = sum == 0;
    3.49 @@ -227,22 +228,20 @@
    3.50                      const CostMap &cost,
    3.51                      Node s, Node t,
    3.52                      Supply flow_value ) :
    3.53 -      _graph(graph), _lower(&lower), _capacity(graph), _cost(cost),
    3.54 -      _supply(graph), _flow(NULL), _local_flow(false),
    3.55 +      _graph(graph), _lower(&lower), _capacity(capacity), _cost(cost),
    3.56 +      _supply(graph, 0), _flow(NULL), _local_flow(false),
    3.57        _potential(NULL), _local_potential(false), _res_graph(NULL),
    3.58        _res_cost(_cost)
    3.59      {
    3.60 -      // Removing non-zero lower bounds
    3.61 -      _capacity = subMap(capacity, lower);
    3.62 -      for (NodeIt n(_graph); n != INVALID; ++n) {
    3.63 -        Supply sum = 0;
    3.64 -        if (n == s) sum =  flow_value;
    3.65 -        if (n == t) sum = -flow_value;
    3.66 -        for (InEdgeIt e(_graph, n); e != INVALID; ++e)
    3.67 -          sum += lower[e];
    3.68 -        for (OutEdgeIt e(_graph, n); e != INVALID; ++e)
    3.69 -          sum -= lower[e];
    3.70 -        _supply[n] = sum;
    3.71 +      // Remove non-zero lower bounds
    3.72 +      _supply[s] =  flow_value;
    3.73 +      _supply[t] = -flow_value;
    3.74 +      for (EdgeIt e(_graph); e != INVALID; ++e) {
    3.75 +        if (lower[e] != 0) {
    3.76 +          _capacity[e] -= lower[e];
    3.77 +          _supply[_graph.source(e)] -= lower[e];
    3.78 +          _supply[_graph.target(e)] += lower[e];
    3.79 +        }
    3.80        }
    3.81        _valid_supply = true;
    3.82      }

     4.1 --- a/lemon/network_simplex.h	Thu Nov 13 10:54:42 2008 +0000
     4.2 +++ b/lemon/network_simplex.h	Thu Nov 13 15:29:04 2008 +0000
     4.3 @@ -611,32 +611,30 @@
     4.4        _local_flow(false), _local_potential(false),
     4.5        _node_ref(graph), _edge_ref(graph)
     4.6      {
     4.7 -      // Checking the sum of supply values
     4.8 +      // Check the sum of supply values
     4.9        Supply sum = 0;
    4.10        for (typename Graph::NodeIt n(_graph_ref); n != INVALID; ++n)
    4.11          sum += supply[n];
    4.12        if (!(_valid_supply = sum == 0)) return;
    4.13  
    4.14 -      // Copying _graph_ref to _graph
    4.15 +      // Copy _graph_ref to _graph
    4.16        _graph.reserveNode(countNodes(_graph_ref) + 1);
    4.17        _graph.reserveEdge(countEdges(_graph_ref) + countNodes(_graph_ref));
    4.18        copyGraph(_graph, _graph_ref)
    4.19 +        .edgeMap(_capacity, capacity)
    4.20          .edgeMap(_cost, cost)
    4.21 +        .nodeMap(_supply, supply)
    4.22          .nodeRef(_node_ref)
    4.23          .edgeRef(_edge_ref)
    4.24          .run();
    4.25  
    4.26 -      // Removing non-zero lower bounds
    4.27 +      // Remove non-zero lower bounds
    4.28        for (typename Graph::EdgeIt e(_graph_ref); e != INVALID; ++e) {
    4.29 +        if (lower[e] != 0) {
    4.30          _capacity[_edge_ref[e]] = capacity[e] - lower[e];
    4.31 +          _supply[_node_ref[_graph_ref.source(e)]] -= lower[e];
    4.32 +          _supply[_node_ref[_graph_ref.target(e)]] += lower[e];
    4.33        }
    4.34 -      for (typename Graph::NodeIt n(_graph_ref); n != INVALID; ++n) {
    4.35 -        Supply s = supply[n];
    4.36 -        for (typename Graph::InEdgeIt e(_graph_ref, n); e != INVALID; ++e)
    4.37 -          s += lower[e];
    4.38 -        for (typename Graph::OutEdgeIt e(_graph_ref, n); e != INVALID; ++e)
    4.39 -          s -= lower[e];
    4.40 -        _supply[_node_ref[n]] = s;
    4.41        }
    4.42      }
    4.43  
    4.44 @@ -661,13 +659,15 @@
    4.45        _local_flow(false), _local_potential(false),
    4.46        _node_ref(graph), _edge_ref(graph)
    4.47      {
    4.48 -      // Checking the sum of supply values
    4.49 +      // Check the sum of supply values
    4.50        Supply sum = 0;
    4.51        for (typename Graph::NodeIt n(_graph_ref); n != INVALID; ++n)
    4.52          sum += supply[n];
    4.53        if (!(_valid_supply = sum == 0)) return;
    4.54  
    4.55 -      // Copying _graph_ref to graph
    4.56 +      // Copy _graph_ref to _graph
    4.57 +      _graph.reserveNode(countNodes(_graph_ref) + 1);
    4.58 +      _graph.reserveEdge(countEdges(_graph_ref) + countNodes(_graph_ref));
    4.59        copyGraph(_graph, _graph_ref)
    4.60          .edgeMap(_capacity, capacity)
    4.61          .edgeMap(_cost, cost)
    4.62 @@ -697,7 +697,7 @@
    4.63                      typename Graph::Node t,
    4.64                      typename SupplyMap::Value flow_value ) :
    4.65        _graph(), _graph_ref(graph), _lower(&lower), _capacity(_graph),
    4.66 -      _cost(_graph), _supply(_graph), _flow(_graph),
    4.67 +      _cost(_graph), _supply(_graph, 0), _flow(_graph),
    4.68        _potential(_graph), _depth(_graph), _parent(_graph),
    4.69        _pred_edge(_graph), _thread(_graph), _forward(_graph),
    4.70        _state(_graph), _red_cost(_graph, _cost, _potential),
    4.71 @@ -705,26 +705,25 @@
    4.72        _local_flow(false), _local_potential(false),
    4.73        _node_ref(graph), _edge_ref(graph)
    4.74      {
    4.75 -      // Copying _graph_ref to graph
    4.76 +      // Copy _graph_ref to graph
    4.77 +      _graph.reserveNode(countNodes(_graph_ref) + 1);
    4.78 +      _graph.reserveEdge(countEdges(_graph_ref) + countNodes(_graph_ref));
    4.79        copyGraph(_graph, _graph_ref)
    4.80 +        .edgeMap(_capacity, capacity)
    4.81          .edgeMap(_cost, cost)
    4.82          .nodeRef(_node_ref)
    4.83          .edgeRef(_edge_ref)
    4.84          .run();
    4.85  
    4.86 -      // Removing non-zero lower bounds
    4.87 +      // Remove non-zero lower bounds
    4.88 +      _supply[_node_ref[s]] =  flow_value;
    4.89 +      _supply[_node_ref[t]] = -flow_value;
    4.90        for (typename Graph::EdgeIt e(_graph_ref); e != INVALID; ++e) {
    4.91 +        if (lower[e] != 0) {
    4.92          _capacity[_edge_ref[e]] = capacity[e] - lower[e];
    4.93 +          _supply[_node_ref[_graph_ref.source(e)]] -= lower[e];
    4.94 +          _supply[_node_ref[_graph_ref.target(e)]] += lower[e];
    4.95        }
    4.96 -      for (typename Graph::NodeIt n(_graph_ref); n != INVALID; ++n) {
    4.97 -        Supply sum = 0;
    4.98 -        if (n == s) sum =  flow_value;
    4.99 -        if (n == t) sum = -flow_value;
   4.100 -        for (typename Graph::InEdgeIt e(_graph_ref, n); e != INVALID; ++e)
   4.101 -          sum += lower[e];
   4.102 -        for (typename Graph::OutEdgeIt e(_graph_ref, n); e != INVALID; ++e)
   4.103 -          sum -= lower[e];
   4.104 -        _supply[_node_ref[n]] = sum;
   4.105        }
   4.106        _valid_supply = true;
   4.107      }
   4.108 @@ -755,7 +754,9 @@
   4.109        _local_flow(false), _local_potential(false),
   4.110        _node_ref(graph), _edge_ref(graph)
   4.111      {
   4.112 -      // Copying _graph_ref to graph
   4.113 +      // Copy _graph_ref to graph
   4.114 +      _graph.reserveNode(countNodes(_graph_ref) + 1);
   4.115 +      _graph.reserveEdge(countEdges(_graph_ref) + countNodes(_graph_ref));
   4.116        copyGraph(_graph, _graph_ref)
   4.117          .edgeMap(_capacity, capacity)
   4.118          .edgeMap(_cost, cost)