COIN-OR::LEMON - Graph Library

Changeset 2519:a7376f7ed899 in lemon-0.x


Ignore:
Timestamp:
11/21/07 14:35:10 (12 years ago)
Author:
Balazs Dezso
Branch:
default
Phase:
public
Convert:
svn:c9d7d8f5-90d6-0310-b91f-818b3a526b0e/lemon/trunk@3395
Message:

Changed queue implementation

Location:
lemon
Files:
2 edited

Legend:

Unmodified
Added
Removed
  • lemon/dinitz_sleator_tarjan.h

    r2514 r2519  
    2525/// and Tarjan.
    2626
    27 #include <lemon/time_measure.h>
    28 #include <queue>
    2927#include <lemon/graph_utils.h>
    3028#include <lemon/tolerance.h>
    31 #include <lemon/graph_adaptor.h>
    32 #include <lemon/bfs.h>
    33 #include <lemon/edge_set.h>
    3429#include <lemon/dynamic_tree.h>
    3530
     
    161156    DynTree* _dt;
    162157
     158    std::vector<Node> _queue;
     159
    163160    Tolerance _tolerance;
    164161   
     
    230227        _flow(0), _local_flow(false),
    231228        _level(0), _dt_edges(0),
    232         _dt_index(0), _dt(0),
     229        _dt_index(0), _dt(0), _queue(),
    233230        _tolerance(), _flow_value(), _max_value()
    234231    {
     
    327324        _dt_edges = new EdgeNodeMap(_graph);
    328325      }
     326      _queue.resize(countNodes(_graph));
    329327      _max_value = _dt->maxValue();
    330328    }
     
    356354      int level = 0;
    357355
    358       std::vector<Node> queue;
    359       queue.push_back(_target);
     356      _queue[0] = _target;
    360357      _level->set(_target, level);
     358
     359      int first = 0, last = 1, limit = 0;
    361360     
    362       while ((*_level)[_source] == -2 && !queue.empty()) {
    363         std::vector<Node> nqueue;
    364         ++level;
     361      while (first != last && (*_level)[_source] == -2) {
     362        if (first == limit) {
     363          limit = last;
     364          ++level;
     365        }
    365366       
    366         for (int i = 0; i < int(queue.size()); ++i) {
    367           Node n = queue[i];
     367        Node n = _queue[first++];
    368368         
    369           for (OutEdgeIt e(_graph, n); e != INVALID; ++e) {
    370             Node v = _graph.target(e);
    371             if ((*_level)[v] != -2) continue;
    372             Value rem = (*_flow)[e];
    373             if (!_tolerance.positive(rem)) continue;
    374             _level->set(v, level);
    375             nqueue.push_back(v);
    376           }
    377 
    378           for (InEdgeIt e(_graph, n); e != INVALID; ++e) {
    379             Node v = _graph.source(e);
    380             if ((*_level)[v] != -2) continue;
    381             Value rem = (*_capacity)[e] - (*_flow)[e];
    382             if (!_tolerance.positive(rem)) continue;
    383             _level->set(v, level);
    384             nqueue.push_back(v);
    385           }
    386 
    387         }
    388         queue.swap(nqueue);
    389       }
    390      
     369        for (OutEdgeIt e(_graph, n); e != INVALID; ++e) {
     370          Node v = _graph.target(e);
     371          if ((*_level)[v] != -2) continue;
     372          Value rem = (*_flow)[e];
     373          if (!_tolerance.positive(rem)) continue;
     374          _level->set(v, level);
     375          _queue[last++] = v;
     376        }
     377       
     378        for (InEdgeIt e(_graph, n); e != INVALID; ++e) {
     379          Node v = _graph.source(e);
     380          if ((*_level)[v] != -2) continue;
     381          Value rem = (*_capacity)[e] - (*_flow)[e];
     382          if (!_tolerance.positive(rem)) continue;
     383          _level->set(v, level);
     384          _queue[last++] = v;
     385        }
     386      }
    391387      return (*_level)[_source] != -2;
    392388    }
  • lemon/dynamic_tree.h

    r2514 r2519  
    144144    /// \brief Add \e x value to the cost of every node on the path from
    145145    /// \e item to findRoot(item).
    146     void addCost(const Item &item, Value x){
     146    void addCost(const Item &item, Value x) {
    147147      addPathCost(expose(_iim[item]), x);
    148148    }
     
    201201    }
    202202
    203     int findPath(int v){
     203    int findPath(int v) {
    204204      splay(v);
    205205      return v;
    206206    }
    207207   
    208     int findPathCost(int p, Value &d){
     208    int findPathCost(int p, Value &d) {
    209209      while ((_data[p].right != -1 &&
    210210              !_tolerance.less(0, _data[_data[p].right].dmin)) ||
     
    214214          p = _data[p].right;
    215215        } else if (_data[p].left != -1 &&
    216                    !_tolerance.less(0, _data[_data[p].left].dmin)){
     216                   !_tolerance.less(0, _data[_data[p].left].dmin)) {
    217217          p = _data[p].left;
    218218        }
     
    231231    }
    232232   
    233     void addPathCost(int p, Value x){
     233    void addPathCost(int p, Value x) {
    234234      if (!_tolerance.less(x, _max_value)) {
    235         _data[p].dmin = x;_data[p].dcost = x;
     235        _data[p].dmin = x;
     236        _data[p].dcost = x;
    236237      } else if (!_tolerance.less(-x, _max_value)) {
    237238        _data[p].dmin = 0;
     
    364365      Value aa = _data[a].dcost;
    365366      if (_tolerance.less(aa, _max_value)) {
    366         aa+= min;
     367        aa += min;
    367368      }
    368369
     
    372373      Value bb = _data[b].dcost;
    373374      if (_tolerance.less(bb, _max_value)) {
    374         bb+= ab;
     375        bb += ab;
    375376      }
    376377
     
    381382        cc = _data[c].dmin;
    382383        if (_tolerance.less(cc, _max_value)) {
    383           cc+=min;
     384          cc += min;
    384385        }
    385386      }
     
    687688    }
    688689
    689     int findPath(int v){
     690    int findPath(int v) {
    690691      splay(v);
    691692      return v;
    692693    }
    693694   
    694     int findPathCost(int p, Value &d){
     695    int findPathCost(int p, Value &d) {
    695696      while ((_data[p].right != -1 &&
    696697              !_tolerance.less(0, _data[_data[p].right].dmin)) ||
     
    709710    }
    710711
    711     int findTail(int p){
     712    int findTail(int p) {
    712713      while (_data[p].right != -1) {
    713714        p = _data[p].right;
     
    717718    }
    718719   
    719     void addPathCost(int p, Value x){
     720    void addPathCost(int p, Value x) {
    720721      if (!_tolerance.less(x, _max_value)) {
    721722        _data[p].dmin = x;_data[p].dcost = x;
     
    756757        _data[p].dmin -= min;
    757758      }
    758       if (q!=-1){
     759      if (q != -1){
    759760        _data[q].parent = v;
    760761        if (_tolerance.less(_data[q].dmin,_max_value)) {
     
    764765      _data[v].left = p;
    765766      _data[v].right = q;
    766       if (_tolerance.less(min,_max_value)) {
     767      if (_tolerance.less(min, _max_value)) {
    767768        _data[v].dcost = _data[v].dmin - min;
    768769      }
Note: See TracChangeset for help on using the changeset viewer.