COIN-OR::LEMON - Graph Library

Changeset 2340:03c71d754990 in lemon-0.x


Ignore:
Timestamp:
01/11/07 22:22:39 (13 years ago)
Author:
Balazs Dezso
Branch:
default
Phase:
public
Convert:
svn:c9d7d8f5-90d6-0310-b91f-818b3a526b0e/lemon/trunk@3132
Message:

Make Hao-Orlin epsilon-safe

Location:
lemon
Files:
2 edited

Legend:

Unmodified
Added
Removed
  • lemon/graph_adaptor.h

    r2277 r2340  
    14511451
    14521452    bool operator[](const typename Graph::Edge& e) const {
    1453       return tolerance.less((*flow)[e], (*capacity)[e]);
     1453      return tolerance.positive((*capacity)[e] - (*flow)[e]);
    14541454    }
    14551455  };
     
    14741474    void setFlow(const FlowMap& _flow) { flow = &_flow; }
    14751475    bool operator[](const typename Graph::Edge& e) const {
    1476       return tolerance.less(0, Number((*flow)[e]));
     1476      return tolerance.positive((*flow)[e]);
    14771477    }
    14781478  };
  • lemon/hao_orlin.h

    r2275 r2340  
    2020#define LEMON_HAO_ORLIN_H
    2121
     22#include <cassert>
     23 
     24
     25
    2226#include <vector>
    2327#include <queue>
     28#include <list>
    2429#include <limits>
    2530
     
    2833#include <lemon/graph_adaptor.h>
    2934#include <lemon/iterable_maps.h>
    30  
    3135
    3236/// \file
     
    109113    OutResGraph* _out_res_graph;
    110114
    111     typedef typename Graph::template NodeMap<OutResEdge> OutCurrentEdgeMap;
    112     OutCurrentEdgeMap* _out_current_edge; 
    113 
    114115    typedef RevGraphAdaptor<const Graph> RevGraph;
    115116    RevGraph* _rev_graph;
     
    120121   
    121122    InResGraph* _in_res_graph;
    122 
    123     typedef typename Graph::template NodeMap<InResEdge> InCurrentEdgeMap;
    124     InCurrentEdgeMap* _in_current_edge; 
    125 
    126123
    127124    typedef IterableBoolMap<Graph, Node> WakeMap;
     
    162159      _graph(&graph), _capacity(&capacity),
    163160      _preflow(0), _source(), _target(),
    164       _out_res_graph(0), _out_current_edge(0),
    165       _rev_graph(0), _in_res_graph(0), _in_current_edge(0),
     161      _out_res_graph(0), _rev_graph(0), _in_res_graph(0),
    166162      _wake(0),_dist(0), _excess(0), _source_set(0),
    167163      _highest_active(), _active_nodes(), _dormant_max(), _dormant(),
     
    172168        delete _min_cut_map;
    173169      }
    174       if (_in_current_edge) {
    175         delete _in_current_edge;
    176       }
    177170      if (_in_res_graph) {
    178171        delete _in_res_graph;
     
    181174        delete _rev_graph;
    182175      }
    183       if (_out_current_edge) {
    184         delete _out_current_edge;
    185       }
    186176      if (_out_res_graph) {
    187177        delete _out_res_graph;
     
    206196  private:
    207197   
    208     template <typename ResGraph, typename EdgeMap>
    209     void findMinCut(const Node& target, bool out,
    210                     ResGraph& res_graph, EdgeMap& current_edge) {
     198    template <typename ResGraph>
     199    void findMinCut(const Node& target, bool out, ResGraph& res_graph) {
     200      typedef typename Graph::Node Node;
    211201      typedef typename ResGraph::Edge ResEdge;
    212202      typedef typename ResGraph::OutEdgeIt ResOutEdgeIt;
     
    220210        (*_excess)[it] = 0;
    221211        (*_source_set)[it] = false;
    222 
    223         res_graph.firstOut(current_edge[it], it);
    224       }
     212      }
     213
     214      _dormant[0].push_front(_source);
     215      (*_source_set)[_source] = true;
     216      _dormant_max = 0;
     217      (*_wake)[_source] = false;
     218
     219      _level_size[0] = 1;
     220      _level_size[1] = _node_num - 1;
    225221
    226222      _target = target;
     
    229225      for (ResOutEdgeIt it(res_graph, _source); it != INVALID; ++it) {
    230226        Value delta = res_graph.rescap(it);
    231         if (!_tolerance.positive(delta)) continue;
    232        
    233         (*_excess)[res_graph.source(it)] -= delta;
     227        (*_excess)[_source] -= delta;
    234228        res_graph.augment(it, delta);
    235229        Node a = res_graph.target(it);
    236         if (!_tolerance.positive((*_excess)[a]) &&
    237             (*_wake)[a] && a != _target) {
     230        if ((*_excess)[a] == 0 && (*_wake)[a] && a != _target) {
    238231          _active_nodes[(*_dist)[a]].push_front(a);
    239232          if (_highest_active < (*_dist)[a]) {
     
    244237      }
    245238
    246       _dormant[0].push_front(_source);
    247       (*_source_set)[_source] = true;
    248       _dormant_max = 0;
    249       (*_wake)[_source] = false;
    250 
    251       _level_size[0] = 1;
    252       _level_size[1] = _node_num - 1;
    253239
    254240      do {
    255241        Node n;
    256242        while ((n = findActiveNode()) != INVALID) {
    257           ResEdge e;
    258           while (_tolerance.positive((*_excess)[n]) &&
    259                  (e = findAdmissibleEdge(n, res_graph, current_edge))
    260                  != INVALID){
    261             Value delta;
    262             if ((*_excess)[n] < res_graph.rescap(e)) {
     243          for (ResOutEdgeIt e(res_graph, n); e != INVALID; ++e) {
     244            Node a = res_graph.target(e);
     245            if ((*_dist)[a] >= (*_dist)[n] || !(*_wake)[a]) continue;
     246            Value delta = res_graph.rescap(e);
     247            if (_tolerance.positive((*_excess)[n] - delta)) {
     248              (*_excess)[n] -= delta;
     249            } else {
    263250              delta = (*_excess)[n];
    264             } else {
    265               delta = res_graph.rescap(e);
    266               res_graph.nextOut(current_edge[n]);
     251              (*_excess)[n] = 0;
    267252            }
    268             if (!_tolerance.positive(delta)) continue;
    269253            res_graph.augment(e, delta);
    270             (*_excess)[res_graph.source(e)] -= delta;
    271             Node a = res_graph.target(e);
    272             if (!_tolerance.positive((*_excess)[a]) && a != _target) {
     254            if ((*_excess)[a] == 0 && a != _target) {
    273255              _active_nodes[(*_dist)[a]].push_front(a);
    274256            }
    275257            (*_excess)[a] += delta;
     258            if ((*_excess)[n] == 0) break;
    276259          }
    277           if (_tolerance.positive((*_excess)[n])) {
    278             relabel(n, res_graph, current_edge);
     260          if ((*_excess)[n] != 0) {
     261            relabel(n, res_graph);
    279262          }
    280263        }
     
    298281    }
    299282
    300     template <typename ResGraph, typename EdgeMap>
    301     void relabel(const Node& n, ResGraph& res_graph, EdgeMap& current_edge) {
     283    template <typename ResGraph>
     284    void relabel(const Node& n, ResGraph& res_graph) {
    302285      typedef typename ResGraph::OutEdgeIt ResOutEdgeIt;
    303286
     
    312295          }
    313296        }
    314         --_highest_active;
     297        --_highest_active;
    315298      } else { 
    316299        int new_dist = _node_num;
     
    332315          _active_nodes[_highest_active].push_front(n);
    333316          ++_level_size[(*_dist)[n]];
    334           res_graph.firstOut(current_edge[n], n);
    335317        }
    336318      }
     
    373355      if (wake_was_empty){
    374356        for (typename WakeMap::TrueIt it(*_wake); it != INVALID; ++it) {
    375           if (_tolerance.positive((*_excess)[it])) {
    376             if ((*_wake)[it] && it != _target) {
    377               _active_nodes[(*_dist)[it]].push_front(it);
    378             }
    379             if (_highest_active < (*_dist)[it]) {
    380               _highest_active = (*_dist)[it];               
     357          if ((*_excess)[it] != 0 && it != _target) {
     358            _active_nodes[(*_dist)[it]].push_front(it);
     359            if (_highest_active < (*_dist)[it]) {
     360              _highest_active = (*_dist)[it];               
    381361            }
    382362          }
     
    384364      }
    385365
    386       for (ResOutEdgeIt e(res_graph, old_target); e!=INVALID; ++e){
    387         if (!(*_source_set)[res_graph.target(e)]) {
    388           Value delta = res_graph.rescap(e);
    389           if (!_tolerance.positive(delta)) continue;
    390           res_graph.augment(e, delta);
    391           (*_excess)[res_graph.source(e)] -= delta;
    392           Node a = res_graph.target(e);
    393           if (!_tolerance.positive((*_excess)[a]) &&
    394               (*_wake)[a] && a != _target) {
    395             _active_nodes[(*_dist)[a]].push_front(a);
    396             if (_highest_active < (*_dist)[a]) {
    397               _highest_active = (*_dist)[a];
    398             }
     366      Node n = old_target;
     367      for (ResOutEdgeIt e(res_graph, n); e != INVALID; ++e){
     368        Node a = res_graph.target(e);
     369        if (!(*_wake)[a]) continue;
     370        Value delta = res_graph.rescap(e);
     371        res_graph.augment(e, delta);
     372        (*_excess)[n] -= delta;
     373        if ((*_excess)[a] == 0 && (*_wake)[a] && a != _target) {
     374          _active_nodes[(*_dist)[a]].push_front(a);
     375          if (_highest_active < (*_dist)[a]) {
     376            _highest_active = (*_dist)[a];
    399377          }
    400           (*_excess)[a] += delta;
    401         }
     378        }
     379        (*_excess)[a] += delta;
    402380      }
    403381     
    404382      return true;
    405383    }
    406    
     384
    407385    Node findActiveNode() {
    408386      while (_highest_active > 0 && _active_nodes[_highest_active].empty()){
     
    413391        _active_nodes[_highest_active].pop_front();
    414392        return n;
    415       } else {
    416         return INVALID;
    417       }
    418     }
    419 
    420     template <typename ResGraph, typename EdgeMap>
    421     typename ResGraph::Edge findAdmissibleEdge(const Node& n,
    422                                                ResGraph& res_graph,
    423                                                EdgeMap& current_edge) {
    424       typedef typename ResGraph::Edge ResEdge;
    425       ResEdge e = current_edge[n];
    426       while (e != INVALID &&
    427              ((*_dist)[n] <= (*_dist)[res_graph.target(e)] ||
    428               !(*_wake)[res_graph.target(e)])) {
    429         res_graph.nextOut(e);
    430       }
    431       if (e != INVALID) {
    432         current_edge[n] = e;   
    433         return e;
    434393      } else {
    435394        return INVALID;
     
    513472        _out_res_graph = new OutResGraph(*_graph, *_capacity, *_preflow);
    514473      }
    515       if (!_out_current_edge) {
    516         _out_current_edge = new OutCurrentEdgeMap(*_graph);
    517       }
    518474      if (!_rev_graph) {
    519475        _rev_graph = new RevGraph(*_graph);
     
    521477      if (!_in_res_graph) {
    522478        _in_res_graph = new InResGraph(*_rev_graph, *_capacity, *_preflow);
    523       }
    524       if (!_in_current_edge) {
    525         _in_current_edge = new InCurrentEdgeMap(*_graph);
    526479      }
    527480      if (!_min_cut_map) {
     
    556509    /// for the push-relabel algorithm.
    557510    void calculateOut(const Node& target) {
    558       findMinCut(target, true, *_out_res_graph, *_out_current_edge);
     511      findMinCut(target, true, *_out_res_graph);
    559512    }
    560513
     
    584537    /// target for the push-relabel algorithm.
    585538    void calculateIn(const Node& target) {
    586       findMinCut(target, false, *_in_res_graph, *_in_current_edge);
     539      findMinCut(target, false, *_in_res_graph);
    587540    }
    588541
Note: See TracChangeset for help on using the changeset viewer.