COIN-OR::LEMON - Graph Library

About

Downloads

Documentation

Development

Issue Tracker

Browse Tickets

Custom Query

Roadmap

Browse Source

Local Info

Mailing Lists

Search

Changeset 2629:84354c78b068 in lemon-0.x


Ignore:
Timestamp:
11/13/08 16:29:04 (15 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

Location:
lemon
Files:
4 edited

Legend:

Unmodified
Added
Removed

  • lemon/capacity_scaling.h

    r2623 r2629  
    255255                     const CostMap &cost,
    256256                     const SupplyMap &supply ) :
    257       _graph(graph), _lower(&lower), _capacity(graph), _cost(cost),
    258       _supply(graph), _flow(NULL), _local_flow(false),
     257      _graph(graph), _lower(&lower), _capacity(capacity), _cost(cost),
     258      _supply(supply), _flow(NULL), _local_flow(false),
    259259      _potential(NULL), _local_potential(false),
    260       _res_cap(graph), _excess(graph), _pred(graph), _dijkstra(NULL)
     260      _res_cap(capacity), _excess(supply), _pred(graph), _dijkstra(NULL)
    261261    {
    262       // Removing non-zero lower bounds
    263       _capacity = subMap(capacity, lower);
    264       _res_cap = _capacity;
     262      // Check the sum of supply values
    265263      Supply sum = 0;
    266       for (NodeIt n(_graph); n != INVALID; ++n) {
    267         Supply s = supply[n];
    268         for (InEdgeIt e(_graph, n); e != INVALID; ++e)
    269           s += lower[e];
    270         for (OutEdgeIt e(_graph, n); e != INVALID; ++e)
    271           s -= lower[e];
    272         _supply[n] = s;
    273         sum += s;
    274       }
     264      for (NodeIt n(_graph); n != INVALID; ++n) sum += _supply[n];
    275265      _valid_supply = sum == 0;
     266
     267      // Remove non-zero lower bounds
     268      typename LowerMap::Value lcap;
     269      for (EdgeIt e(_graph); e != INVALID; ++e) {
     270        if ((lcap = lower[e]) != 0) {
     271          _capacity[e] -= lcap;
     272          _res_cap[e] -= lcap;
     273          _supply[_graph.source(e)] -= lcap;
     274          _supply[_graph.target(e)] += lcap;
     275          _excess[_graph.source(e)] -= lcap;
     276          _excess[_graph.target(e)] += lcap;
     277        }
     278      }
    276279    }
    277280
    … …  
    291294      _supply(supply), _flow(NULL), _local_flow(false),
    292295      _potential(NULL), _local_potential(false),
    293       _res_cap(capacity), _excess(graph), _pred(graph), _dijkstra(NULL)
     296      _res_cap(capacity), _excess(supply), _pred(graph), _dijkstra(NULL)
    294297    {
    295       // Checking the sum of supply values
     298      // Check the sum of supply values
    296299      Supply sum = 0;
    297300      for (NodeIt n(_graph); n != INVALID; ++n) sum += _supply[n];
    … …  
    317320                     Node s, Node t,
    318321                     Supply flow_value ) :
    319       _graph(graph), _lower(&lower), _capacity(graph), _cost(cost),
    320       _supply(graph), _flow(NULL), _local_flow(false),
     322      _graph(graph), _lower(&lower), _capacity(capacity), _cost(cost),
     323      _supply(graph, 0), _flow(NULL), _local_flow(false),
    321324      _potential(NULL), _local_potential(false),
    322       _res_cap(graph), _excess(graph), _pred(graph), _dijkstra(NULL)
     325      _res_cap(capacity), _excess(graph, 0), _pred(graph), _dijkstra(NULL)
    323326    {
    324       // Removing non-zero lower bounds
    325       _capacity = subMap(capacity, lower);
    326       _res_cap = _capacity;
    327       for (NodeIt n(_graph); n != INVALID; ++n) {
    328         Supply sum = 0;
    329         if (n == s) sum =  flow_value;
    330         if (n == t) sum = -flow_value;
    331         for (InEdgeIt e(_graph, n); e != INVALID; ++e)
    332           sum += lower[e];
    333         for (OutEdgeIt e(_graph, n); e != INVALID; ++e)
    334           sum -= lower[e];
    335         _supply[n] = sum;
     327      // Remove non-zero lower bounds
     328      _supply[s] = _excess[s] =  flow_value;
     329      _supply[t] = _excess[t] = -flow_value;
     330      typename LowerMap::Value lcap;
     331      for (EdgeIt e(_graph); e != INVALID; ++e) {
     332        if ((lcap = lower[e]) != 0) {
     333          _capacity[e] -= lcap;
     334          _res_cap[e] -= lcap;
     335          _supply[_graph.source(e)] -= lcap;
     336          _supply[_graph.target(e)] += lcap;
     337          _excess[_graph.source(e)] -= lcap;
     338          _excess[_graph.target(e)] += lcap;
     339        }
    336340      }
    337341      _valid_supply = true;
    … …  
    357361      _supply(graph, 0), _flow(NULL), _local_flow(false),
    358362      _potential(NULL), _local_potential(false),
    359       _res_cap(capacity), _excess(graph), _pred(graph), _dijkstra(NULL)
     363      _res_cap(capacity), _excess(graph, 0), _pred(graph), _dijkstra(NULL)
    360364    {
    361       _supply[s] = flow_value;
    362       _supply[t] = -flow_value;
     365      _supply[s] = _excess[s] = flow_value;
     366      _supply[t] = _excess[t] = -flow_value;
    363367      _valid_supply = true;
    364368    }
    … …  
    498502      for (EdgeIt e(_graph); e != INVALID; ++e) (*_flow)[e] = 0;
    499503      for (NodeIt n(_graph); n != INVALID; ++n) (*_potential)[n] = 0;
    500       _excess = _supply;
    501504
    502505      _dijkstra = new ResidualDijkstra( _graph, *_flow, _res_cap, _cost,

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

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

  • lemon/network_simplex.h

    r2628 r2629  
    612612      _node_ref(graph), _edge_ref(graph)
    613613    {
    614       // Checking the sum of supply values
     614      // Check the sum of supply values
    615615      Supply sum = 0;
    616616      for (typename Graph::NodeIt n(_graph_ref); n != INVALID; ++n)
    … …  
    618618      if (!(_valid_supply = sum == 0)) return;
    619619
    620       // Copying _graph_ref to _graph
     620      // Copy _graph_ref to _graph
    621621      _graph.reserveNode(countNodes(_graph_ref) + 1);
    622622      _graph.reserveEdge(countEdges(_graph_ref) + countNodes(_graph_ref));
    623623      copyGraph(_graph, _graph_ref)
     624        .edgeMap(_capacity, capacity)
    624625        .edgeMap(_cost, cost)
     626        .nodeMap(_supply, supply)
    625627        .nodeRef(_node_ref)
    626628        .edgeRef(_edge_ref)
    627629        .run();
    628630
    629       // Removing non-zero lower bounds
     631      // Remove non-zero lower bounds
    630632      for (typename Graph::EdgeIt e(_graph_ref); e != INVALID; ++e) {
     633        if (lower[e] != 0) {
    631634        _capacity[_edge_ref[e]] = capacity[e] - lower[e];
    632       }
    633       for (typename Graph::NodeIt n(_graph_ref); n != INVALID; ++n) {
    634         Supply s = supply[n];
    635         for (typename Graph::InEdgeIt e(_graph_ref, n); e != INVALID; ++e)
    636           s += lower[e];
    637         for (typename Graph::OutEdgeIt e(_graph_ref, n); e != INVALID; ++e)
    638           s -= lower[e];
    639         _supply[_node_ref[n]] = s;
     635          _supply[_node_ref[_graph_ref.source(e)]] -= lower[e];
     636          _supply[_node_ref[_graph_ref.target(e)]] += lower[e];
     637      }
    640638      }
    641639    }
    … …  
    662660      _node_ref(graph), _edge_ref(graph)
    663661    {
    664       // Checking the sum of supply values
     662      // Check the sum of supply values
    665663      Supply sum = 0;
    666664      for (typename Graph::NodeIt n(_graph_ref); n != INVALID; ++n)
    … …  
    668666      if (!(_valid_supply = sum == 0)) return;
    669667
    670       // Copying _graph_ref to graph
     668      // Copy _graph_ref to _graph
     669      _graph.reserveNode(countNodes(_graph_ref) + 1);
     670      _graph.reserveEdge(countEdges(_graph_ref) + countNodes(_graph_ref));
    671671      copyGraph(_graph, _graph_ref)
    672672        .edgeMap(_capacity, capacity)
    … …  
    698698                    typename SupplyMap::Value flow_value ) :
    699699      _graph(), _graph_ref(graph), _lower(&lower), _capacity(_graph),
    700       _cost(_graph), _supply(_graph), _flow(_graph),
     700      _cost(_graph), _supply(_graph, 0), _flow(_graph),
    701701      _potential(_graph), _depth(_graph), _parent(_graph),
    702702      _pred_edge(_graph), _thread(_graph), _forward(_graph),
    … …  
    706706      _node_ref(graph), _edge_ref(graph)
    707707    {
    708       // Copying _graph_ref to graph
     708      // Copy _graph_ref to graph
     709      _graph.reserveNode(countNodes(_graph_ref) + 1);
     710      _graph.reserveEdge(countEdges(_graph_ref) + countNodes(_graph_ref));
    709711      copyGraph(_graph, _graph_ref)
     712        .edgeMap(_capacity, capacity)
    710713        .edgeMap(_cost, cost)
    711714        .nodeRef(_node_ref)
    … …  
    713716        .run();
    714717
    715       // Removing non-zero lower bounds
     718      // Remove non-zero lower bounds
     719      _supply[_node_ref[s]] =  flow_value;
     720      _supply[_node_ref[t]] = -flow_value;
    716721      for (typename Graph::EdgeIt e(_graph_ref); e != INVALID; ++e) {
     722        if (lower[e] != 0) {
    717723        _capacity[_edge_ref[e]] = capacity[e] - lower[e];
    718       }
    719       for (typename Graph::NodeIt n(_graph_ref); n != INVALID; ++n) {
    720         Supply sum = 0;
    721         if (n == s) sum =  flow_value;
    722         if (n == t) sum = -flow_value;
    723         for (typename Graph::InEdgeIt e(_graph_ref, n); e != INVALID; ++e)
    724           sum += lower[e];
    725         for (typename Graph::OutEdgeIt e(_graph_ref, n); e != INVALID; ++e)
    726           sum -= lower[e];
    727         _supply[_node_ref[n]] = sum;
     724          _supply[_node_ref[_graph_ref.source(e)]] -= lower[e];
     725          _supply[_node_ref[_graph_ref.target(e)]] += lower[e];
     726      }
    728727      }
    729728      _valid_supply = true;
    … …  
    756755      _node_ref(graph), _edge_ref(graph)
    757756    {
    758       // Copying _graph_ref to graph
     757      // Copy _graph_ref to graph
     758      _graph.reserveNode(countNodes(_graph_ref) + 1);
     759      _graph.reserveEdge(countEdges(_graph_ref) + countNodes(_graph_ref));
    759760      copyGraph(_graph, _graph_ref)
    760761        .edgeMap(_capacity, capacity)
Note: See TracChangeset for help on using the changeset viewer.