COIN-OR::LEMON - Graph Library

Changeset 650:425cc8328c0e in lemon for lemon/network_simplex.h


Ignore:
Timestamp:
03/23/09 23:54:42 (10 years ago)
Author:
Peter Kovacs <kpeter@…>
Branch:
default
Phase:
public
Message:

Internal restructuring and renamings in NetworkSimplex? (#234)

File:
1 edited

Legend:

Unmodified
Added
Removed
  • lemon/network_simplex.h

    r648 r650  
    2929#include <algorithm>
    3030
     31#include <lemon/core.h>
    3132#include <lemon/math.h>
    3233
     
    121122
    122123    // References for the original data
    123     const Digraph &_orig_graph;
     124    const Digraph &_graph;
    124125    const LowerMap *_orig_lower;
    125126    const CapacityMap &_orig_cap;
     
    131132
    132133    // Result maps
    133     FlowMap *_flow_result;
    134     PotentialMap *_potential_result;
     134    FlowMap *_flow_map;
     135    PotentialMap *_potential_map;
    135136    bool _local_flow;
    136137    bool _local_potential;
    137 
    138     // Data structures for storing the graph
    139     ArcVector _arc;
    140     NodeVector _node;
    141     IntNodeMap _node_id;
    142     IntVector _source;
    143     IntVector _target;
    144138
    145139    // The number of nodes and arcs in the original graph
    146140    int _node_num;
    147141    int _arc_num;
     142
     143    // Data structures for storing the graph
     144    IntNodeMap _node_id;
     145    ArcVector _arc_ref;
     146    IntVector _source;
     147    IntVector _target;
    148148
    149149    // Node and arc maps
     
    154154    CostVector _pi;
    155155
    156     // Node and arc maps for the spanning tree structure
     156    // Data for storing the spanning tree structure
    157157    IntVector _depth;
    158158    IntVector _parent;
     
    161161    BoolVector _forward;
    162162    IntVector _state;
    163 
    164     // The root node
    165163    int _root;
    166164
    167     // The entering arc in the current pivot iteration
    168     int _in_arc;
    169 
    170165    // Temporary data used in the current pivot iteration
    171     int join, u_in, v_in, u_out, v_out;
    172     int right, first, second, last;
     166    int in_arc, join, u_in, v_in, u_out, v_out;
     167    int first, second, right, last;
    173168    int stem, par_stem, new_stem;
    174169    Capacity delta;
     
    188183
    189184      // References to the NetworkSimplex class
    190       const ArcVector &_arc;
    191185      const IntVector  &_source;
    192186      const IntVector  &_target;
     
    204198      /// Constructor
    205199      FirstEligiblePivotRule(NetworkSimplex &ns) :
    206         _arc(ns._arc), _source(ns._source), _target(ns._target),
     200        _source(ns._source), _target(ns._target),
    207201        _cost(ns._cost), _state(ns._state), _pi(ns._pi),
    208         _in_arc(ns._in_arc), _arc_num(ns._arc_num), _next_arc(0)
     202        _in_arc(ns.in_arc), _arc_num(ns._arc_num), _next_arc(0)
    209203      {}
    210204
     
    246240
    247241      // References to the NetworkSimplex class
    248       const ArcVector &_arc;
    249242      const IntVector  &_source;
    250243      const IntVector  &_target;
     
    259252      /// Constructor
    260253      BestEligiblePivotRule(NetworkSimplex &ns) :
    261         _arc(ns._arc), _source(ns._source), _target(ns._target),
     254        _source(ns._source), _target(ns._target),
    262255        _cost(ns._cost), _state(ns._state), _pi(ns._pi),
    263         _in_arc(ns._in_arc), _arc_num(ns._arc_num)
     256        _in_arc(ns.in_arc), _arc_num(ns._arc_num)
    264257      {}
    265258
     
    292285
    293286      // References to the NetworkSimplex class
    294       const ArcVector &_arc;
    295287      const IntVector  &_source;
    296288      const IntVector  &_target;
     
    309301      /// Constructor
    310302      BlockSearchPivotRule(NetworkSimplex &ns) :
    311         _arc(ns._arc), _source(ns._source), _target(ns._target),
     303        _source(ns._source), _target(ns._target),
    312304        _cost(ns._cost), _state(ns._state), _pi(ns._pi),
    313         _in_arc(ns._in_arc), _arc_num(ns._arc_num), _next_arc(0)
     305        _in_arc(ns.in_arc), _arc_num(ns._arc_num), _next_arc(0)
    314306      {
    315307        // The main parameters of the pivot rule
     
    371363
    372364      // References to the NetworkSimplex class
    373       const ArcVector &_arc;
    374365      const IntVector  &_source;
    375366      const IntVector  &_target;
     
    390381      /// Constructor
    391382      CandidateListPivotRule(NetworkSimplex &ns) :
    392         _arc(ns._arc), _source(ns._source), _target(ns._target),
     383        _source(ns._source), _target(ns._target),
    393384        _cost(ns._cost), _state(ns._state), _pi(ns._pi),
    394         _in_arc(ns._in_arc), _arc_num(ns._arc_num), _next_arc(0)
     385        _in_arc(ns.in_arc), _arc_num(ns._arc_num), _next_arc(0)
    395386      {
    396387        // The main parameters of the pivot rule
     
    483474
    484475      // References to the NetworkSimplex class
    485       const ArcVector &_arc;
    486476      const IntVector  &_source;
    487477      const IntVector  &_target;
     
    516506      /// Constructor
    517507      AlteringListPivotRule(NetworkSimplex &ns) :
    518         _arc(ns._arc), _source(ns._source), _target(ns._target),
     508        _source(ns._source), _target(ns._target),
    519509        _cost(ns._cost), _state(ns._state), _pi(ns._pi),
    520         _in_arc(ns._in_arc), _arc_num(ns._arc_num),
     510        _in_arc(ns.in_arc), _arc_num(ns._arc_num),
    521511        _next_arc(0), _cand_cost(ns._arc_num), _sort_func(_cand_cost)
    522512      {
     
    550540        // Extend the list
    551541        int cnt = _block_size;
    552         int last_edge = 0;
     542        int last_arc = 0;
    553543        int limit = _head_length;
    554544
     
    558548          if (_cand_cost[e] < 0) {
    559549            _candidates[_curr_length++] = e;
    560             last_edge = e;
     550            last_arc = e;
    561551          }
    562552          if (--cnt == 0) {
     
    572562            if (_cand_cost[e] < 0) {
    573563              _candidates[_curr_length++] = e;
    574               last_edge = e;
     564              last_arc = e;
    575565            }
    576566            if (--cnt == 0) {
     
    582572        }
    583573        if (_curr_length == 0) return false;
    584         _next_arc = last_edge + 1;
     574        _next_arc = last_arc + 1;
    585575
    586576        // Make heap of the candidate list (approximating a partial sort)
     
    604594    /// General constructor (with lower bounds).
    605595    ///
    606     /// \param digraph The digraph the algorithm runs on.
     596    /// \param graph The digraph the algorithm runs on.
    607597    /// \param lower The lower bounds of the arcs.
    608598    /// \param capacity The capacities (upper bounds) of the arcs.
    609599    /// \param cost The cost (length) values of the arcs.
    610600    /// \param supply The supply values of the nodes (signed).
    611     NetworkSimplex( const Digraph &digraph,
     601    NetworkSimplex( const Digraph &graph,
    612602                    const LowerMap &lower,
    613603                    const CapacityMap &capacity,
    614604                    const CostMap &cost,
    615605                    const SupplyMap &supply ) :
    616       _orig_graph(digraph), _orig_lower(&lower), _orig_cap(capacity),
     606      _graph(graph), _orig_lower(&lower), _orig_cap(capacity),
    617607      _orig_cost(cost), _orig_supply(&supply),
    618       _flow_result(NULL), _potential_result(NULL),
     608      _flow_map(NULL), _potential_map(NULL),
    619609      _local_flow(false), _local_potential(false),
    620       _node_id(digraph)
     610      _node_id(graph)
    621611    {}
    622612
     
    625615    /// General constructor (without lower bounds).
    626616    ///
    627     /// \param digraph The digraph the algorithm runs on.
     617    /// \param graph The digraph the algorithm runs on.
    628618    /// \param capacity The capacities (upper bounds) of the arcs.
    629619    /// \param cost The cost (length) values of the arcs.
    630620    /// \param supply The supply values of the nodes (signed).
    631     NetworkSimplex( const Digraph &digraph,
     621    NetworkSimplex( const Digraph &graph,
    632622                    const CapacityMap &capacity,
    633623                    const CostMap &cost,
    634624                    const SupplyMap &supply ) :
    635       _orig_graph(digraph), _orig_lower(NULL), _orig_cap(capacity),
     625      _graph(graph), _orig_lower(NULL), _orig_cap(capacity),
    636626      _orig_cost(cost), _orig_supply(&supply),
    637       _flow_result(NULL), _potential_result(NULL),
     627      _flow_map(NULL), _potential_map(NULL),
    638628      _local_flow(false), _local_potential(false),
    639       _node_id(digraph)
     629      _node_id(graph)
    640630    {}
    641631
     
    644634    /// Simple constructor (with lower bounds).
    645635    ///
    646     /// \param digraph The digraph the algorithm runs on.
     636    /// \param graph The digraph the algorithm runs on.
    647637    /// \param lower The lower bounds of the arcs.
    648638    /// \param capacity The capacities (upper bounds) of the arcs.
     
    652642    /// \param flow_value The required amount of flow from node \c s
    653643    /// to node \c t (i.e. the supply of \c s and the demand of \c t).
    654     NetworkSimplex( const Digraph &digraph,
     644    NetworkSimplex( const Digraph &graph,
    655645                    const LowerMap &lower,
    656646                    const CapacityMap &capacity,
     
    658648                    Node s, Node t,
    659649                    Capacity flow_value ) :
    660       _orig_graph(digraph), _orig_lower(&lower), _orig_cap(capacity),
     650      _graph(graph), _orig_lower(&lower), _orig_cap(capacity),
    661651      _orig_cost(cost), _orig_supply(NULL),
    662652      _orig_source(s), _orig_target(t), _orig_flow_value(flow_value),
    663       _flow_result(NULL), _potential_result(NULL),
     653      _flow_map(NULL), _potential_map(NULL),
    664654      _local_flow(false), _local_potential(false),
    665       _node_id(digraph)
     655      _node_id(graph)
    666656    {}
    667657
     
    670660    /// Simple constructor (without lower bounds).
    671661    ///
    672     /// \param digraph The digraph the algorithm runs on.
     662    /// \param graph The digraph the algorithm runs on.
    673663    /// \param capacity The capacities (upper bounds) of the arcs.
    674664    /// \param cost The cost (length) values of the arcs.
     
    677667    /// \param flow_value The required amount of flow from node \c s
    678668    /// to node \c t (i.e. the supply of \c s and the demand of \c t).
    679     NetworkSimplex( const Digraph &digraph,
     669    NetworkSimplex( const Digraph &graph,
    680670                    const CapacityMap &capacity,
    681671                    const CostMap &cost,
    682672                    Node s, Node t,
    683673                    Capacity flow_value ) :
    684       _orig_graph(digraph), _orig_lower(NULL), _orig_cap(capacity),
     674      _graph(graph), _orig_lower(NULL), _orig_cap(capacity),
    685675      _orig_cost(cost), _orig_supply(NULL),
    686676      _orig_source(s), _orig_target(t), _orig_flow_value(flow_value),
    687       _flow_result(NULL), _potential_result(NULL),
     677      _flow_map(NULL), _potential_map(NULL),
    688678      _local_flow(false), _local_potential(false),
    689       _node_id(digraph)
     679      _node_id(graph)
    690680    {}
    691681
    692682    /// Destructor.
    693683    ~NetworkSimplex() {
    694       if (_local_flow) delete _flow_result;
    695       if (_local_potential) delete _potential_result;
     684      if (_local_flow) delete _flow_map;
     685      if (_local_potential) delete _potential_map;
    696686    }
    697687
     
    703693    NetworkSimplex& flowMap(FlowMap &map) {
    704694      if (_local_flow) {
    705         delete _flow_result;
     695        delete _flow_map;
    706696        _local_flow = false;
    707697      }
    708       _flow_result = &map;
     698      _flow_map = &map;
    709699      return *this;
    710700    }
     
    717707    NetworkSimplex& potentialMap(PotentialMap &map) {
    718708      if (_local_potential) {
    719         delete _potential_result;
     709        delete _potential_map;
    720710        _local_potential = false;
    721711      }
    722       _potential_result = &map;
     712      _potential_map = &map;
    723713      return *this;
    724714    }
     
    784774    /// \pre \ref run() must be called before using this function.
    785775    const FlowMap& flowMap() const {
    786       return *_flow_result;
     776      return *_flow_map;
    787777    }
    788778
     
    795785    /// \pre \ref run() must be called before using this function.
    796786    const PotentialMap& potentialMap() const {
    797       return *_potential_result;
     787      return *_potential_map;
    798788    }
    799789
     
    804794    /// \pre \ref run() must be called before using this function.
    805795    Capacity flow(const Arc& arc) const {
    806       return (*_flow_result)[arc];
     796      return (*_flow_map)[arc];
    807797    }
    808798
     
    813803    /// \pre \ref run() must be called before using this function.
    814804    Cost potential(const Node& node) const {
    815       return (*_potential_result)[node];
     805      return (*_potential_map)[node];
    816806    }
    817807
     
    824814    Cost totalCost() const {
    825815      Cost c = 0;
    826       for (ArcIt e(_orig_graph); e != INVALID; ++e)
    827         c += (*_flow_result)[e] * _orig_cost[e];
     816      for (ArcIt e(_graph); e != INVALID; ++e)
     817        c += (*_flow_map)[e] * _orig_cost[e];
    828818      return c;
    829819    }
     
    836826    bool init() {
    837827      // Initialize result maps
    838       if (!_flow_result) {
    839         _flow_result = new FlowMap(_orig_graph);
     828      if (!_flow_map) {
     829        _flow_map = new FlowMap(_graph);
    840830        _local_flow = true;
    841831      }
    842       if (!_potential_result) {
    843         _potential_result = new PotentialMap(_orig_graph);
     832      if (!_potential_map) {
     833        _potential_map = new PotentialMap(_graph);
    844834        _local_potential = true;
    845835      }
    846836
    847837      // Initialize vectors
    848       _node_num = countNodes(_orig_graph);
    849       _arc_num = countArcs(_orig_graph);
     838      _node_num = countNodes(_graph);
     839      _arc_num = countArcs(_graph);
    850840      int all_node_num = _node_num + 1;
    851       int all_edge_num = _arc_num + _node_num;
    852 
    853       _arc.resize(_arc_num);
    854       _node.reserve(_node_num);
    855       _source.resize(all_edge_num);
    856       _target.resize(all_edge_num);
    857 
    858       _cap.resize(all_edge_num);
    859       _cost.resize(all_edge_num);
     841      int all_arc_num = _arc_num + _node_num;
     842
     843      _arc_ref.resize(_arc_num);
     844      _source.resize(all_arc_num);
     845      _target.resize(all_arc_num);
     846
     847      _cap.resize(all_arc_num);
     848      _cost.resize(all_arc_num);
    860849      _supply.resize(all_node_num);
    861       _flow.resize(all_edge_num, 0);
     850      _flow.resize(all_arc_num, 0);
    862851      _pi.resize(all_node_num, 0);
    863852
     
    865854      _parent.resize(all_node_num);
    866855      _pred.resize(all_node_num);
     856      _forward.resize(all_node_num);
    867857      _thread.resize(all_node_num);
    868       _forward.resize(all_node_num);
    869       _state.resize(all_edge_num, STATE_LOWER);
     858      _state.resize(all_arc_num, STATE_LOWER);
    870859
    871860      // Initialize node related data
     
    874863        Supply sum = 0;
    875864        int i = 0;
    876         for (NodeIt n(_orig_graph); n != INVALID; ++n, ++i) {
    877           _node.push_back(n);
     865        for (NodeIt n(_graph); n != INVALID; ++n, ++i) {
    878866          _node_id[n] = i;
    879867          _supply[i] = (*_orig_supply)[n];
     
    883871      } else {
    884872        int i = 0;
    885         for (NodeIt n(_orig_graph); n != INVALID; ++n, ++i) {
    886           _node.push_back(n);
     873        for (NodeIt n(_graph); n != INVALID; ++n, ++i) {
    887874          _node_id[n] = i;
    888875          _supply[i] = 0;
     
    905892      int k = std::max(int(sqrt(_arc_num)), 10);
    906893      int i = 0;
    907       for (ArcIt e(_orig_graph); e != INVALID; ++e) {
    908         _arc[i] = e;
     894      for (ArcIt e(_graph); e != INVALID; ++e) {
     895        _arc_ref[i] = e;
    909896        if ((i += k) >= _arc_num) i = (i % k) + 1;
    910897      }
     
    912899      // Initialize arc maps
    913900      for (int i = 0; i != _arc_num; ++i) {
    914         Arc e = _arc[i];
    915         _source[i] = _node_id[_orig_graph.source(e)];
    916         _target[i] = _node_id[_orig_graph.target(e)];
     901        Arc e = _arc_ref[i];
     902        _source[i] = _node_id[_graph.source(e)];
     903        _target[i] = _node_id[_graph.target(e)];
    917904        _cost[i] = _orig_cost[e];
    918905        _cap[i] = _orig_cap[e];
     
    922909      if (_orig_lower) {
    923910        for (int i = 0; i != _arc_num; ++i) {
    924           Capacity c = (*_orig_lower)[_arc[i]];
     911          Capacity c = (*_orig_lower)[_arc_ref[i]];
    925912          if (c != 0) {
    926913            _cap[i] -= c;
     
    958945    // Find the join node
    959946    void findJoinNode() {
    960       int u = _source[_in_arc];
    961       int v = _target[_in_arc];
     947      int u = _source[in_arc];
     948      int v = _target[in_arc];
    962949      while (_depth[u] > _depth[v]) u = _parent[u];
    963950      while (_depth[v] > _depth[u]) v = _parent[v];
     
    974961      // Initialize first and second nodes according to the direction
    975962      // of the cycle
    976       if (_state[_in_arc] == STATE_LOWER) {
    977         first  = _source[_in_arc];
    978         second = _target[_in_arc];
     963      if (_state[in_arc] == STATE_LOWER) {
     964        first  = _source[in_arc];
     965        second = _target[in_arc];
    979966      } else {
    980         first  = _target[_in_arc];
    981         second = _source[_in_arc];
    982       }
    983       delta = _cap[_in_arc];
     967        first  = _target[in_arc];
     968        second = _source[in_arc];
     969      }
     970      delta = _cap[in_arc];
    984971      int result = 0;
    985972      Capacity d;
     
    10211008      // Augment along the cycle
    10221009      if (delta > 0) {
    1023         Capacity val = _state[_in_arc] * delta;
    1024         _flow[_in_arc] += val;
    1025         for (int u = _source[_in_arc]; u != join; u = _parent[u]) {
     1010        Capacity val = _state[in_arc] * delta;
     1011        _flow[in_arc] += val;
     1012        for (int u = _source[in_arc]; u != join; u = _parent[u]) {
    10261013          _flow[_pred[u]] += _forward[u] ? -val : val;
    10271014        }
    1028         for (int u = _target[_in_arc]; u != join; u = _parent[u]) {
     1015        for (int u = _target[in_arc]; u != join; u = _parent[u]) {
    10291016          _flow[_pred[u]] += _forward[u] ? val : -val;
    10301017        }
     
    10321019      // Update the state of the entering and leaving arcs
    10331020      if (change) {
    1034         _state[_in_arc] = STATE_TREE;
     1021        _state[in_arc] = STATE_TREE;
    10351022        _state[_pred[u_out]] =
    10361023          (_flow[_pred[u_out]] == 0) ? STATE_LOWER : STATE_UPPER;
    10371024      } else {
    1038         _state[_in_arc] = -_state[_in_arc];
     1025        _state[in_arc] = -_state[in_arc];
    10391026      }
    10401027    }
     
    11071094        u = v;
    11081095      }
    1109       _pred[u_in] = _in_arc;
    1110       _forward[u_in] = (u_in == _source[_in_arc]);
     1096      _pred[u_in] = in_arc;
     1097      _forward[u_in] = (u_in == _source[in_arc]);
    11111098    }
    11121099
     
    11641151      }
    11651152
    1166       // Copy flow values to _flow_result
     1153      // Copy flow values to _flow_map
    11671154      if (_orig_lower) {
    11681155        for (int i = 0; i != _arc_num; ++i) {
    1169           Arc e = _arc[i];
    1170           (*_flow_result)[e] = (*_orig_lower)[e] + _flow[i];
     1156          Arc e = _arc_ref[i];
     1157          _flow_map->set(e, (*_orig_lower)[e] + _flow[i]);
    11711158        }
    11721159      } else {
    11731160        for (int i = 0; i != _arc_num; ++i) {
    1174           (*_flow_result)[_arc[i]] = _flow[i];
    1175         }
    1176       }
    1177       // Copy potential values to _potential_result
    1178       for (int i = 0; i != _node_num; ++i) {
    1179         (*_potential_result)[_node[i]] = _pi[i];
     1161          _flow_map->set(_arc_ref[i], _flow[i]);
     1162        }
     1163      }
     1164      // Copy potential values to _potential_map
     1165      for (NodeIt n(_graph); n != INVALID; ++n) {
     1166        _potential_map->set(n, _pi[_node_id[n]]);
    11801167      }
    11811168
Note: See TracChangeset for help on using the changeset viewer.