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 );