COIN-OR::LEMON - Graph Library

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