COIN-OR::LEMON - Graph Library

Changeset 2629:84354c78b068 in lemon-0.x for lemon/cycle_canceling.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/cycle_canceling.h

    r2623 r2629  
    168168                    const CostMap &cost,
    169169                    const SupplyMap &supply ) :
    170       _graph(graph), _lower(&lower), _capacity(graph), _cost(cost),
    171       _supply(graph), _flow(NULL), _local_flow(false),
     170      _graph(graph), _lower(&lower), _capacity(capacity), _cost(cost),
     171      _supply(supply), _flow(NULL), _local_flow(false),
    172172      _potential(NULL), _local_potential(false), _res_graph(NULL),
    173173      _res_cost(_cost)
    174174    {
    175       // Removing non-zero lower bounds
    176       _capacity = subMap(capacity, lower);
     175      // Check the sum of supply values
    177176      Supply sum = 0;
    178       for (NodeIt n(_graph); n != INVALID; ++n) {
    179         Supply s = supply[n];
    180         for (InEdgeIt e(_graph, n); e != INVALID; ++e)
    181           s += lower[e];
    182         for (OutEdgeIt e(_graph, n); e != INVALID; ++e)
    183           s -= lower[e];
    184         sum += (_supply[n] = s);
    185       }
     177      for (NodeIt n(_graph); n != INVALID; ++n) sum += _supply[n];
    186178      _valid_supply = sum == 0;
     179
     180      // Remove non-zero lower bounds
     181      for (EdgeIt e(_graph); e != INVALID; ++e) {
     182        if (lower[e] != 0) {
     183          _capacity[e] -= lower[e];
     184          _supply[_graph.source(e)] -= lower[e];
     185          _supply[_graph.target(e)] += lower[e];
     186        }
     187      }
    187188    }
    188189
     
    204205      _res_cost(_cost)
    205206    {
    206       // Checking the sum of supply values
     207      // Check the sum of supply values
    207208      Supply sum = 0;
    208209      for (NodeIt n(_graph); n != INVALID; ++n) sum += _supply[n];
     
    228229                    Node s, Node t,
    229230                    Supply flow_value ) :
    230       _graph(graph), _lower(&lower), _capacity(graph), _cost(cost),
    231       _supply(graph), _flow(NULL), _local_flow(false),
     231      _graph(graph), _lower(&lower), _capacity(capacity), _cost(cost),
     232      _supply(graph, 0), _flow(NULL), _local_flow(false),
    232233      _potential(NULL), _local_potential(false), _res_graph(NULL),
    233234      _res_cost(_cost)
    234235    {
    235       // Removing non-zero lower bounds
    236       _capacity = subMap(capacity, lower);
    237       for (NodeIt n(_graph); n != INVALID; ++n) {
    238         Supply sum = 0;
    239         if (n == s) sum =  flow_value;
    240         if (n == t) sum = -flow_value;
    241         for (InEdgeIt e(_graph, n); e != INVALID; ++e)
    242           sum += lower[e];
    243         for (OutEdgeIt e(_graph, n); e != INVALID; ++e)
    244           sum -= lower[e];
    245         _supply[n] = sum;
     236      // Remove non-zero lower bounds
     237      _supply[s] =  flow_value;
     238      _supply[t] = -flow_value;
     239      for (EdgeIt e(_graph); e != INVALID; ++e) {
     240        if (lower[e] != 0) {
     241          _capacity[e] -= lower[e];
     242          _supply[_graph.source(e)] -= lower[e];
     243          _supply[_graph.target(e)] += lower[e];
     244        }
    246245      }
    247246      _valid_supply = true;
Note: See TracChangeset for help on using the changeset viewer.