COIN-OR::LEMON - Graph Library

Changeset 58:f71840c04b2a in lemon-0.x for src


Ignore:
Timestamp:
02/04/04 13:45:32 (16 years ago)
Author:
marci
Branch:
default
Phase:
public
Convert:
svn:c9d7d8f5-90d6-0310-b91f-818b3a526b0e/lemon/trunk@73
Message:

BfsIterator2

File:
1 edited

Legend:

Unmodified
Added
Removed
  • src/work/bfs_iterator.hh

    r42 r58  
    1 #ifndef MARCI_BFS_HH
    2 #define MARCI_BFS_HH
     1#ifndef BFS_ITERATOR_HH
     2#define BFS_ITERATOR_HH
    33
    44#include <queue>
     
    396396  };
    397397
     398  template <typename Graph, typename OutEdgeIt, typename ReachedMap>
     399  class BfsIterator2 {
     400    typedef typename Graph::NodeIt NodeIt;
     401    const Graph& G;
     402    std::queue<OutEdgeIt> bfs_queue;
     403    ReachedMap reached;
     404    bool b_node_newly_reached;
     405    OutEdgeIt actual_edge;
     406  public:
     407    BfsIterator2(const Graph& _G) : G(_G), reached(G, false) { }
     408    void pushAndSetReached(const NodeIt s) {
     409      reached.set(s, true);
     410      if (bfs_queue.empty()) {
     411        bfs_queue.push(G.template first<OutEdgeIt>(s));
     412        actual_edge=bfs_queue.front();
     413        if (actual_edge.valid()) {
     414          NodeIt w=G.bNode(actual_edge);
     415          if (!reached.get(w)) {
     416            bfs_queue.push(G.template first<OutEdgeIt>(w));
     417            reached.set(w, true);
     418            b_node_newly_reached=true;
     419          } else {
     420            b_node_newly_reached=false;
     421          }
     422        } //else {
     423        //}
     424      } else {
     425        bfs_queue.push(G.template first<OutEdgeIt>(s));
     426      }
     427    }
     428    BfsIterator2<Graph, OutEdgeIt, ReachedMap>&
     429    operator++() {
     430      if (bfs_queue.front().valid()) {
     431        ++(bfs_queue.front());
     432        actual_edge=bfs_queue.front();
     433        if (actual_edge.valid()) {
     434          NodeIt w=G.bNode(actual_edge);
     435          if (!reached.get(w)) {
     436            bfs_queue.push(G.template first<OutEdgeIt>(w));
     437            reached.set(w, true);
     438            b_node_newly_reached=true;
     439          } else {
     440            b_node_newly_reached=false;
     441          }
     442        }
     443      } else {
     444        bfs_queue.pop();
     445        if (!bfs_queue.empty()) {
     446          actual_edge=bfs_queue.front();
     447        } else {
     448          actual_edge=OutEdgeIt();
     449        }
     450        if (actual_edge.valid()) {
     451          NodeIt w=G.bNode(actual_edge);
     452          if (!reached.get(w)) {
     453            bfs_queue.push(G.template first<OutEdgeIt>(w));
     454            reached.set(w, true);
     455            b_node_newly_reached=true;
     456          } else {
     457            b_node_newly_reached=false;
     458          }
     459        }
     460      }
     461      return *this;
     462    }
     463    bool finished() const { return bfs_queue.empty(); }
     464    operator OutEdgeIt () const { return actual_edge; }
     465    bool isBNodeNewlyReached() const { return b_node_newly_reached; }
     466    bool isANodeExamined() const { return !(actual_edge.valid()); }
     467    const ReachedMap& getReachedMap() const { return reached; }
     468    const std::queue<OutEdgeIt>& getBfsQueue() const { return bfs_queue; }
     469 };
     470
     471
    398472} // namespace marci
    399473
    400 #endif //MARCI_BFS_HH
     474#endif //BFS_ITERATOR_HH
Note: See TracChangeset for help on using the changeset viewer.