lemon/capacity_scaling.h
changeset 2629 84354c78b068
parent 2623 90defb96ee61
     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 );