COIN-OR::LEMON - Graph Library

About

Downloads

Documentation

Development

Issue Tracker

Browse Tickets

Custom Query

Roadmap

Browse Source

Local Info

Mailing Lists

Search

Changeset 148:004fdf703abb in lemon-0.x for src/work/bfs_iterator.hh


Ignore:
Timestamp:
03/03/04 15:30:38 (19 years ago)
Author:
marci
Branch:
default
Phase:
public
Convert:
svn:c9d7d8f5-90d6-0310-b91f-818b3a526b0e/lemon/trunk@208
Message:

G.next(...), G.valid(...), ...

File:
1 edited

Legend:

Unmodified
Added
Removed

  • src/work/bfs_iterator.hh

    r144 r148  
    545545
    546546  template <typename Graph, typename OutEdgeIt,
    547             typename ReachedMap=typename Graph::NodeMap<bool> >
     547            typename ReachedMap/*=typename Graph::NodeMap<bool>*/ >
    548548  class BfsIterator4 {
    549549    typedef typename Graph::NodeIt NodeIt;
    … …  
    567567        bfs_queue.push(s);
    568568        G.getFirst(actual_edge, s);
    569         if (actual_edge.valid()) {
     569        if (G.valid(actual_edge)/*.valid()*/) {
    570570          NodeIt w=G.bNode(actual_edge);
    571571          if (!reached.get(w)) {
    … …  
    583583    BfsIterator4<Graph, OutEdgeIt, ReachedMap>&
    584584    operator++() {
    585       if (actual_edge.valid()) {
    586         ++actual_edge;
    587         if (actual_edge.valid()) {
     585      if (G.valid(actual_edge)/*.valid()*/) {
     586        /*++*/G.next(actual_edge);
     587        if (G.valid(actual_edge)/*.valid()*/) {
    588588          NodeIt w=G.bNode(actual_edge);
    589589          if (!reached.get(w)) {
    … …  
    599599        if (!bfs_queue.empty()) {
    600600          G.getFirst(actual_edge, bfs_queue.front());
    601           if (actual_edge.valid()) {
     601          if (G.valid(actual_edge)/*.valid()*/) {
    602602            NodeIt w=G.bNode(actual_edge);
    603603            if (!reached.get(w)) {
    … …  
    616616    operator OutEdgeIt () const { return actual_edge; }
    617617    bool isBNodeNewlyReached() const { return b_node_newly_reached; }
    618     bool isANodeExamined() const { return !(actual_edge.valid()); }
     618    bool isANodeExamined() const { return !(G.valid(actual_edge)/*.valid()*/); }
    619619    NodeIt aNode() const { return bfs_queue.front(); }
    620620    NodeIt bNode() const { return G.bNode(actual_edge); }
    … …  
    623623 }; 
    624624
     625
     626  template <typename GraphWrapper, typename OutEdgeIt,
     627            typename ReachedMap/*=typename GraphWrapper::NodeMap<bool>*/ >
     628  class BfsIterator5 {
     629    typedef typename GraphWrapper::NodeIt NodeIt;
     630    GraphWrapper G;
     631    std::queue<NodeIt> bfs_queue;
     632    ReachedMap& reached;
     633    bool b_node_newly_reached;
     634    OutEdgeIt actual_edge;
     635    bool own_reached_map;
     636  public:
     637    BfsIterator5(const GraphWrapper& _G, ReachedMap& _reached) :
     638      G(_G), reached(_reached),
     639      own_reached_map(false) { }
     640    BfsIterator5(const GraphWrapper& _G) :
     641      G(_G), reached(*(new ReachedMap(G /*, false*/))),
     642      own_reached_map(true) { }
     643    ~BfsIterator5() { if (own_reached_map) delete &reached; }
     644    void pushAndSetReached(NodeIt s) {
     645      reached.set(s, true);
     646      if (bfs_queue.empty()) {
     647        bfs_queue.push(s);
     648        G.getFirst(actual_edge, s);
     649        if (G.valid(actual_edge)/*.valid()*/) {
     650          NodeIt w=G.bNode(actual_edge);
     651          if (!reached.get(w)) {
     652            bfs_queue.push(w);
     653            reached.set(w, true);
     654            b_node_newly_reached=true;
     655          } else {
     656            b_node_newly_reached=false;
     657          }
     658        }
     659      } else {
     660        bfs_queue.push(s);
     661      }
     662    }
     663    BfsIterator5<GraphWrapper, OutEdgeIt, ReachedMap>&
     664    operator++() {
     665      if (G.valid(actual_edge)/*.valid()*/) {
     666        /*++*/G.next(actual_edge);
     667        if (G.valid(actual_edge)/*.valid()*/) {
     668          NodeIt w=G.bNode(actual_edge);
     669          if (!reached.get(w)) {
     670            bfs_queue.push(w);
     671            reached.set(w, true);
     672            b_node_newly_reached=true;
     673          } else {
     674            b_node_newly_reached=false;
     675          }
     676        }
     677      } else {
     678        bfs_queue.pop();
     679        if (!bfs_queue.empty()) {
     680          G.getFirst(actual_edge, bfs_queue.front());
     681          if (G.valid(actual_edge)/*.valid()*/) {
     682            NodeIt w=G.bNode(actual_edge);
     683            if (!reached.get(w)) {
     684              bfs_queue.push(w);
     685              reached.set(w, true);
     686              b_node_newly_reached=true;
     687            } else {
     688              b_node_newly_reached=false;
     689            }
     690          }
     691        }
     692      }
     693      return *this;
     694    }
     695    bool finished() const { return bfs_queue.empty(); }
     696    operator OutEdgeIt () const { return actual_edge; }
     697    bool isBNodeNewlyReached() const { return b_node_newly_reached; }
     698    bool isANodeExamined() const { return !(G.valid(actual_edge)/*.valid()*/); }
     699    NodeIt aNode() const { return bfs_queue.front(); }
     700    NodeIt bNode() const { return G.bNode(actual_edge); }
     701    const ReachedMap& getReachedMap() const { return reached; }
     702    const std::queue<NodeIt>& getBfsQueue() const { return bfs_queue; }
     703  }; 
     704
    625705  template <typename Graph, typename OutEdgeIt,
    626             typename ReachedMap=typename Graph::NodeMap<bool> >
     706            typename ReachedMap/*=typename Graph::NodeMap<bool>*/ >
    627707  class DfsIterator4 {
    628708    typedef typename Graph::NodeIt NodeIt;
    … …  
    651731      actual_edge=dfs_stack.top();
    652732      //actual_node=G.aNode(actual_edge);
    653       if (actual_edge.valid()) {
     733      if (G.valid(actual_edge)/*.valid()*/) {
    654734        NodeIt w=G.bNode(actual_edge);
    655735        actual_node=w;
    … …  
    660740        } else {
    661741          actual_node=G.aNode(actual_edge);
    662           ++(dfs_stack.top());
     742          /*++*/G.next(dfs_stack.top());
    663743          b_node_newly_reached=false;
    664744        }
    … …  
    672752    operator OutEdgeIt () const { return actual_edge; }
    673753    bool isBNodeNewlyReached() const { return b_node_newly_reached; }
    674     bool isANodeExamined() const { return !(actual_edge.valid()); }
     754    bool isANodeExamined() const { return !(G.valid(actual_edge)/*.valid()*/); }
    675755    NodeIt aNode() const { return actual_node; /*FIXME*/}
    676756    NodeIt bNode() const { return G.bNode(actual_edge); }
    … …  
    679759  };
    680760
    681 
    682 
    683   template <typename GraphWrapper, typename ReachedMap>
    684   class BfsIterator5 {
     761  template <typename GraphWrapper, typename OutEdgeIt,
     762            typename ReachedMap/*=typename GraphWrapper::NodeMap<bool>*/ >
     763  class DfsIterator5 {
    685764    typedef typename GraphWrapper::NodeIt NodeIt;
    686     typedef typename GraphWrapper::OutEdgeIt OutEdgeIt;
    687     GraphWrapper gw;
    688     std::queue<NodeIt> bfs_queue;
    689     ReachedMap reached;
    690     bool b_node_newly_reached;
    691     OutEdgeIt actual_edge;
     765    GraphWrapper G;
     766    std::stack<OutEdgeIt> dfs_stack;
     767    bool b_node_newly_reached;
     768    OutEdgeIt actual_edge;
     769    NodeIt actual_node;
     770    ReachedMap& reached;
     771    bool own_reached_map;
    692772  public:
    693     BfsIterator5(GraphWrapper _gw) :
    694       gw(_gw), reached(_gw.getGraph()) { }
     773    DfsIterator5(const GraphWrapper& _G, ReachedMap& _reached) :
     774      G(_G), reached(_reached),
     775      own_reached_map(false) { }
     776    DfsIterator5(const GraphWrapper& _G) :
     777      G(_G), reached(*(new ReachedMap(G /*, false*/))),
     778      own_reached_map(true) { }
     779    ~DfsIterator5() { if (own_reached_map) delete &reached; }
    695780    void pushAndSetReached(NodeIt s) {
     781      actual_node=s;
    696782      reached.set(s, true);
    697       if (bfs_queue.empty()) {
    698         bfs_queue.push(s);
    699         gw.getFirst(actual_edge, s);
    700         if (actual_edge.valid()) {
    701           NodeIt w=gw.bNode(actual_edge);
    702           if (!reached.get(w)) {
    703             bfs_queue.push(w);
    704             reached.set(w, true);
    705             b_node_newly_reached=true;
    706           } else {
    707             b_node_newly_reached=false;
    708           }
    709         }
    710       } else {
    711         bfs_queue.push(s);
    712       }
    713     }
    714     BfsIterator5<GraphWrapper, ReachedMap>&
     783      dfs_stack.push(G.template first<OutEdgeIt>(s));
     784    }
     785    DfsIterator5<GraphWrapper, OutEdgeIt, ReachedMap>&
    715786    operator++() {
    716       if (actual_edge.valid()) {
    717         ++actual_edge;
    718         if (actual_edge.valid()) {
    719           NodeIt w=gw.bNode(actual_edge);
    720           if (!reached.get(w)) {
    721             bfs_queue.push(w);
    722             reached.set(w, true);
    723             b_node_newly_reached=true;
    724           } else {
    725             b_node_newly_reached=false;
    726           }
    727         }
    728       } else {
    729         bfs_queue.pop();
    730         if (!bfs_queue.empty()) {
    731           gw.getFirst(actual_edge, bfs_queue.front());
    732           if (actual_edge.valid()) {
    733             NodeIt w=gw.bNode(actual_edge);
    734             if (!reached.get(w)) {
    735               bfs_queue.push(w);
    736               reached.set(w, true);
    737               b_node_newly_reached=true;
    738             } else {
    739               b_node_newly_reached=false;
    740             }
    741           }
    742         }
    743       }
    744       return *this;
    745     }
    746     bool finished() const { return bfs_queue.empty(); }
     787      actual_edge=dfs_stack.top();
     788      //actual_node=G.aNode(actual_edge);
     789      if (G.valid(actual_edge)/*.valid()*/) {
     790        NodeIt w=G.bNode(actual_edge);
     791        actual_node=w;
     792        if (!reached.get(w)) {
     793          dfs_stack.push(G.template first<OutEdgeIt>(w));
     794          reached.set(w, true);
     795          b_node_newly_reached=true;
     796        } else {
     797          actual_node=G.aNode(actual_edge);
     798          /*++*/G.next(dfs_stack.top());
     799          b_node_newly_reached=false;
     800        }
     801      } else {
     802        //actual_node=G.aNode(dfs_stack.top());
     803        dfs_stack.pop();
     804      }
     805      return *this;
     806    }
     807    bool finished() const { return dfs_stack.empty(); }
    747808    operator OutEdgeIt () const { return actual_edge; }
    748809    bool isBNodeNewlyReached() const { return b_node_newly_reached; }
    749     bool isANodeExamined() const { return !(actual_edge.valid()); }
    750     NodeIt aNode() const { return bfs_queue.front(); }
    751     NodeIt bNode() const { return gw.bNode(actual_edge); }
     810    bool isANodeExamined() const { return !(G.valid(actual_edge)/*.valid()*/); }
     811    NodeIt aNode() const { return actual_node; /*FIXME*/}
     812    NodeIt bNode() const { return G.bNode(actual_edge); }
    752813    const ReachedMap& getReachedMap() const { return reached; }
    753     const std::queue<NodeIt>& getBfsQueue() const { return bfs_queue; }
    754  };
     814    const std::stack<OutEdgeIt>& getDfsStack() const { return dfs_stack; }
     815  };
    755816
    756817
Note: See TracChangeset for help on using the changeset viewer.