COIN-OR::LEMON - Graph Library

Changeset 2629:84354c78b068 in lemon-0.x for lemon/cost_scaling.h


Ignore:
Timestamp:
11/13/08 16:29:04 (12 years ago)
Author:
Peter Kovacs
Branch:
default
Phase:
public
Convert:
svn:c9d7d8f5-90d6-0310-b91f-818b3a526b0e/lemon/trunk@3514
Message:

Improved constructors for min cost flow classes
Removing the non-zero lower bounds is faster

File:
1 edited

Legend:

Unmodified
Added
Removed
  • lemon/cost_scaling.h

    r2625 r2629  
    201201                 const CostMap &cost,
    202202                 const SupplyMap &supply ) :
    203       _graph(graph), _lower(&lower), _capacity(graph), _orig_cost(cost),
    204       _cost(graph), _supply(graph), _flow(NULL), _local_flow(false),
     203      _graph(graph), _lower(&lower), _capacity(capacity), _orig_cost(cost),
     204      _cost(graph), _supply(supply), _flow(NULL), _local_flow(false),
    205205      _potential(NULL), _local_potential(false), _res_cost(_cost),
    206206      _res_graph(NULL), _red_cost(NULL), _excess(graph, 0)
    207207    {
     208      // Check the sum of supply values
     209      Supply sum = 0;
     210      for (NodeIt n(_graph); n != INVALID; ++n) sum += _supply[n];
     211      _valid_supply = sum == 0;
     212
    208213      // Remove non-zero lower bounds
    209       _capacity = subMap(capacity, lower);
    210       Supply sum = 0;
    211       for (NodeIt n(_graph); n != INVALID; ++n) {
    212         Supply s = supply[n];
    213         for (InEdgeIt e(_graph, n); e != INVALID; ++e)
    214           s += lower[e];
    215         for (OutEdgeIt e(_graph, n); e != INVALID; ++e)
    216           s -= lower[e];
    217         _supply[n] = s;
    218         sum += s;
    219       }
    220       _valid_supply = sum == 0;
     214      for (EdgeIt e(_graph); e != INVALID; ++e) {
     215        if (lower[e] != 0) {
     216          _capacity[e] -= lower[e];
     217          _supply[_graph.source(e)] -= lower[e];
     218          _supply[_graph.target(e)] += lower[e];
     219        }
     220      }
    221221    }
    222222
     
    262262                 Node s, Node t,
    263263                 Supply flow_value ) :
    264       _graph(graph), _lower(&lower), _capacity(graph), _orig_cost(cost),
    265       _cost(graph), _supply(graph), _flow(NULL), _local_flow(false),
     264      _graph(graph), _lower(&lower), _capacity(capacity), _orig_cost(cost),
     265      _cost(graph), _supply(graph, 0), _flow(NULL), _local_flow(false),
    266266      _potential(NULL), _local_potential(false), _res_cost(_cost),
    267267      _res_graph(NULL), _red_cost(NULL), _excess(graph, 0)
    268268    {
    269       // Remove nonzero lower bounds
    270       _capacity = subMap(capacity, lower);
    271       for (NodeIt n(_graph); n != INVALID; ++n) {
    272         Supply sum = 0;
    273         if (n == s) sum =  flow_value;
    274         if (n == t) sum = -flow_value;
    275         for (InEdgeIt e(_graph, n); e != INVALID; ++e)
    276           sum += lower[e];
    277         for (OutEdgeIt e(_graph, n); e != INVALID; ++e)
    278           sum -= lower[e];
    279         _supply[n] = sum;
     269      // Remove non-zero lower bounds
     270      _supply[s] =  flow_value;
     271      _supply[t] = -flow_value;
     272      for (EdgeIt e(_graph); e != INVALID; ++e) {
     273        if (lower[e] != 0) {
     274          _capacity[e] -= lower[e];
     275          _supply[_graph.source(e)] -= lower[e];
     276          _supply[_graph.target(e)] += lower[e];
     277        }
    280278      }
    281279      _valid_supply = true;
Note: See TracChangeset for help on using the changeset viewer.