COIN-OR::LEMON - Graph Library

source: lemon-0.x/src/work/marci/bfs_iterator.h @ 360:91fba31268d6

Last change on this file since 360:91fba31268d6 was 360:91fba31268d6, checked in by marci, 20 years ago

work/marci/bfs_iterator.h BfsIterator5 -> BfsIterator?, DfsIterator5 -> DfsIterator?

File size: 4.6 KB
Line 
1// -*- c++ -*-
2#ifndef HUGO_BFS_ITERATOR_H
3#define HUGO_BFS_ITERATOR_H
4
5#include <queue>
6#include <stack>
7#include <utility>
8
9namespace hugo {
10
11  template <typename Graph, /*typename OutEdgeIt,*/
12            typename ReachedMap/*=typename Graph::NodeMap<bool>*/ >
13  class BfsIterator {
14  protected:
15    typedef typename Graph::Node Node;
16    typedef typename Graph::OutEdgeIt OutEdgeIt;
17    const Graph* graph;
18    std::queue<Node> bfs_queue;
19    ReachedMap& reached;
20    bool b_node_newly_reached;
21    OutEdgeIt actual_edge;
22    bool own_reached_map;
23  public:
24    BfsIterator(const Graph& _graph, ReachedMap& _reached) :
25      graph(&_graph), reached(_reached),
26      own_reached_map(false) { }
27    BfsIterator(const Graph& _graph) :
28      graph(&_graph), reached(*(new ReachedMap(*graph /*, false*/))),
29      own_reached_map(true) { }
30    ~BfsIterator() { if (own_reached_map) delete &reached; }
31    void pushAndSetReached(Node s) {
32      reached.set(s, true);
33      if (bfs_queue.empty()) {
34        bfs_queue.push(s);
35        graph->first(actual_edge, s);
36        if (graph->valid(actual_edge)) {
37          Node w=graph->bNode(actual_edge);
38          if (!reached[w]) {
39            bfs_queue.push(w);
40            reached.set(w, true);
41            b_node_newly_reached=true;
42          } else {
43            b_node_newly_reached=false;
44          }
45        }
46      } else {
47        bfs_queue.push(s);
48      }
49    }
50    BfsIterator<Graph, /*OutEdgeIt,*/ ReachedMap>&
51    operator++() {
52      if (graph->valid(actual_edge)) {
53        graph->next(actual_edge);
54        if (graph->valid(actual_edge)) {
55          Node w=graph->bNode(actual_edge);
56          if (!reached[w]) {
57            bfs_queue.push(w);
58            reached.set(w, true);
59            b_node_newly_reached=true;
60          } else {
61            b_node_newly_reached=false;
62          }
63        }
64      } else {
65        bfs_queue.pop();
66        if (!bfs_queue.empty()) {
67          graph->first(actual_edge, bfs_queue.front());
68          if (graph->valid(actual_edge)) {
69            Node w=graph->bNode(actual_edge);
70            if (!reached[w]) {
71              bfs_queue.push(w);
72              reached.set(w, true);
73              b_node_newly_reached=true;
74            } else {
75              b_node_newly_reached=false;
76            }
77          }
78        }
79      }
80      return *this;
81    }
82    bool finished() const { return bfs_queue.empty(); }
83    operator OutEdgeIt () const { return actual_edge; }
84    bool isBNodeNewlyReached() const { return b_node_newly_reached; }
85    bool isANodeExamined() const { return !(graph->valid(actual_edge)); }
86    Node aNode() const { return bfs_queue.front(); }
87    Node bNode() const { return graph->bNode(actual_edge); }
88    const ReachedMap& getReachedMap() const { return reached; }
89    const std::queue<Node>& getBfsQueue() const { return bfs_queue; }
90  }; 
91
92  template <typename Graph, /*typename OutEdgeIt,*/
93            typename ReachedMap/*=typename Graph::NodeMap<bool>*/ >
94  class DfsIterator {
95  protected:
96    typedef typename Graph::Node Node;
97    typedef typename Graph::OutEdgeIt OutEdgeIt;
98    const Graph* graph;
99    std::stack<OutEdgeIt> dfs_stack;
100    bool b_node_newly_reached;
101    OutEdgeIt actual_edge;
102    Node actual_node;
103    ReachedMap& reached;
104    bool own_reached_map;
105  public:
106    DfsIterator(const Graph& _graph, ReachedMap& _reached) :
107      graph(&_graph), reached(_reached),
108      own_reached_map(false) { }
109    DfsIterator(const Graph& _graph) :
110      graph(&_graph), reached(*(new ReachedMap(*graph /*, false*/))),
111      own_reached_map(true) { }
112    ~DfsIterator() { if (own_reached_map) delete &reached; }
113    void pushAndSetReached(Node s) {
114      actual_node=s;
115      reached.set(s, true);
116      OutEdgeIt e;
117      graph->first(e, s);
118      dfs_stack.push(e);
119    }
120    DfsIterator<Graph, /*OutEdgeIt,*/ ReachedMap>&
121    operator++() {
122      actual_edge=dfs_stack.top();
123      //actual_node=G.aNode(actual_edge);
124      if (graph->valid(actual_edge)/*.valid()*/) {
125        Node w=graph->bNode(actual_edge);
126        actual_node=w;
127        if (!reached[w]) {
128          OutEdgeIt e;
129          graph->first(e, w);
130          dfs_stack.push(e);
131          reached.set(w, true);
132          b_node_newly_reached=true;
133        } else {
134          actual_node=graph->aNode(actual_edge);
135          graph->next(dfs_stack.top());
136          b_node_newly_reached=false;
137        }
138      } else {
139        //actual_node=G.aNode(dfs_stack.top());
140        dfs_stack.pop();
141      }
142      return *this;
143    }
144    bool finished() const { return dfs_stack.empty(); }
145    operator OutEdgeIt () const { return actual_edge; }
146    bool isBNodeNewlyReached() const { return b_node_newly_reached; }
147    bool isANodeExamined() const { return !(graph->valid(actual_edge)); }
148    Node aNode() const { return actual_node; /*FIXME*/}
149    Node bNode() const { return G.bNode(actual_edge); }
150    const ReachedMap& getReachedMap() const { return reached; }
151    const std::stack<OutEdgeIt>& getDfsStack() const { return dfs_stack; }
152  };
153
154} // namespace hugo
155
156#endif //HUGO_BFS_ITERATOR_H
Note: See TracBrowser for help on using the repository browser.