COIN-OR::LEMON - Graph Library

source: lemon-0.x/src/work/marci/bfs_iterator.h @ 448:510c53fd06cd

Last change on this file since 448:510c53fd06cd was 448:510c53fd06cd, checked in by marci, 16 years ago

bfs, dfs, bfsiterator, dfsiterator for alpar's sake of being much more standardized.

File size: 8.5 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    /// This method markes s reached.
32    /// If the queue is empty, then s is pushed in the bfs queue
33    /// and the first OutEdgeIt is processed.
34    /// If the queue is not empty, then s is simply pushed.
35    void pushAndSetReached(Node s) {
36      reached.set(s, true);
37      if (bfs_queue.empty()) {
38        bfs_queue.push(s);
39        graph->first(actual_edge, s);
40        if (graph->valid(actual_edge)) {
41          Node w=graph->bNode(actual_edge);
42          if (!reached[w]) {
43            bfs_queue.push(w);
44            reached.set(w, true);
45            b_node_newly_reached=true;
46          } else {
47            b_node_newly_reached=false;
48          }
49        }
50      } else {
51        bfs_queue.push(s);
52      }
53    }
54    /// As \c BfsIterator<Graph, ReachedMap> works as an edge-iterator,
55    /// its \c operator++() iterates on the edges in a bfs order.
56    BfsIterator<Graph, /*OutEdgeIt,*/ ReachedMap>&
57    operator++() {
58      if (graph->valid(actual_edge)) {
59        graph->next(actual_edge);
60        if (graph->valid(actual_edge)) {
61          Node w=graph->bNode(actual_edge);
62          if (!reached[w]) {
63            bfs_queue.push(w);
64            reached.set(w, true);
65            b_node_newly_reached=true;
66          } else {
67            b_node_newly_reached=false;
68          }
69        }
70      } else {
71        bfs_queue.pop();
72        if (!bfs_queue.empty()) {
73          graph->first(actual_edge, bfs_queue.front());
74          if (graph->valid(actual_edge)) {
75            Node w=graph->bNode(actual_edge);
76            if (!reached[w]) {
77              bfs_queue.push(w);
78              reached.set(w, true);
79              b_node_newly_reached=true;
80            } else {
81              b_node_newly_reached=false;
82            }
83          }
84        }
85      }
86      return *this;
87    }
88    bool finished() const { return bfs_queue.empty(); }
89    /// The conversion operator makes for converting the bfs-iterator
90    /// to an \c out-edge-iterator.
91    operator OutEdgeIt() const { return actual_edge; }
92    bool isBNodeNewlyReached() const { return b_node_newly_reached; }
93    bool isANodeExamined() const { return !(graph->valid(actual_edge)); }
94    Node aNode() const { return bfs_queue.front(); }
95    Node bNode() const { return graph->bNode(actual_edge); }
96    const ReachedMap& getReachedMap() const { return reached; }
97    const std::queue<Node>& getBfsQueue() const { return bfs_queue; }
98  }; 
99
100  /// Bfs searches from s for the nodes wich are not marked in
101  /// \c reached_map
102  /// Reached is a read-write bool-map, Pred is a write-nodemap
103  /// and dist is an rw-nodemap, have to be.
104  template <typename Graph,
105            typename ReachedMap=typename Graph::template NodeMap<bool>,
106            typename PredMap
107            =typename Graph::template NodeMap<typename Graph::Edge>,
108            typename DistMap=typename Graph::template NodeMap<int> >
109  class Bfs : public BfsIterator<Graph, ReachedMap> {
110    typedef BfsIterator<Graph, ReachedMap> Parent;
111  protected:
112    typedef typename Parent::Node Node;
113    PredMap& pred;
114    DistMap& dist;
115  public:
116    Bfs<Graph, ReachedMap, PredMap, DistMap>(const Graph& _graph, ReachedMap& _reached, PredMap& _pred, DistMap& _dist) : BfsIterator<Graph, ReachedMap>(_graph, _reached), pred(&_pred), dist(&_dist) { }
117    /// s is marked to be reached and pushed in the bfs queue.
118    /// If the queue is empty, then the first out-edge is processed.
119    /// If s was not marked previously, then
120    /// in addition its pred is set to be INVALID, and dist to 0.
121    /// if s was marked previuosly, then it is simply pushed.
122    void push(Node s) {
123      if (this->reached[s]) {
124        Parent::pushAndSetReached(s);
125      } else {
126        Parent::pushAndSetReached(s);
127        pred.set(s, INVALID);
128        dist.set(s, 0);
129      }
130    }
131    /// A bfs is processed from s.
132    void run(Node s) {
133      push(s);
134      while (!this->finished()) this->operator++();
135    }
136    Bfs<Graph, ReachedMap, PredMap, DistMap> operator++() {
137      Parent::operator++();
138      if (this->graph->valid(this->actual_edge) && this->b_node_newly_reached)
139      {
140        pred.set(this->bNode(), this->actual_edge);
141        dist.set(this->bNode(), dist[this->aNode()]);
142      }
143      return *this;
144    }
145    const PredMap& getPredMap() const { return pred; }
146    const DistMap& getDistMap() const { return dist; }
147  };
148
149  template <typename Graph, /*typename OutEdgeIt,*/
150            typename ReachedMap/*=typename Graph::NodeMap<bool>*/ >
151  class DfsIterator {
152  protected:
153    typedef typename Graph::Node Node;
154    typedef typename Graph::OutEdgeIt OutEdgeIt;
155    const Graph* graph;
156    std::stack<OutEdgeIt> dfs_stack;
157    bool b_node_newly_reached;
158    OutEdgeIt actual_edge;
159    Node actual_node;
160    ReachedMap& reached;
161    bool own_reached_map;
162  public:
163    DfsIterator(const Graph& _graph, ReachedMap& _reached) :
164      graph(&_graph), reached(_reached),
165      own_reached_map(false) { }
166    DfsIterator(const Graph& _graph) :
167      graph(&_graph), reached(*(new ReachedMap(*graph /*, false*/))),
168      own_reached_map(true) { }
169    ~DfsIterator() { if (own_reached_map) delete &reached; }
170    void pushAndSetReached(Node s) {
171      actual_node=s;
172      reached.set(s, true);
173      OutEdgeIt e;
174      graph->first(e, s);
175      dfs_stack.push(e);
176    }
177    DfsIterator<Graph, /*OutEdgeIt,*/ ReachedMap>&
178    operator++() {
179      actual_edge=dfs_stack.top();
180      //actual_node=G.aNode(actual_edge);
181      if (graph->valid(actual_edge)/*.valid()*/) {
182        Node w=graph->bNode(actual_edge);
183        actual_node=w;
184        if (!reached[w]) {
185          OutEdgeIt e;
186          graph->first(e, w);
187          dfs_stack.push(e);
188          reached.set(w, true);
189          b_node_newly_reached=true;
190        } else {
191          actual_node=graph->aNode(actual_edge);
192          graph->next(dfs_stack.top());
193          b_node_newly_reached=false;
194        }
195      } else {
196        //actual_node=G.aNode(dfs_stack.top());
197        dfs_stack.pop();
198      }
199      return *this;
200    }
201    bool finished() const { return dfs_stack.empty(); }
202    operator OutEdgeIt() const { return actual_edge; }
203    bool isBNodeNewlyReached() const { return b_node_newly_reached; }
204    bool isANodeExamined() const { return !(graph->valid(actual_edge)); }
205    Node aNode() const { return actual_node; /*FIXME*/}
206    Node bNode() const { return graph->bNode(actual_edge); }
207    const ReachedMap& getReachedMap() const { return reached; }
208    const std::stack<OutEdgeIt>& getDfsStack() const { return dfs_stack; }
209  };
210
211  /// Dfs searches from s for the nodes wich are not marked in
212  /// \c reached_map
213  /// Reached is a read-write bool-map, Pred is a write-nodemap, have to be.
214  template <typename Graph,
215            typename ReachedMap=typename Graph::template NodeMap<bool>,
216            typename PredMap
217            =typename Graph::template NodeMap<typename Graph::Edge> >
218  class Dfs : public DfsIterator<Graph, ReachedMap> {
219    typedef DfsIterator<Graph, ReachedMap> Parent;
220  protected:
221    typedef typename Parent::Node Node;
222    PredMap& pred;
223  public:
224    Dfs<Graph, ReachedMap, PredMap>(const Graph& _graph, ReachedMap& _reached, PredMap& _pred) : DfsIterator<Graph, ReachedMap>(_graph, _reached), pred(&_pred) { }
225    /// s is marked to be reached and pushed in the bfs queue.
226    /// If the queue is empty, then the first out-edge is processed.
227    /// If s was not marked previously, then
228    /// in addition its pred is set to be INVALID.
229    /// if s was marked previuosly, then it is simply pushed.
230    void push(Node s) {
231      if (this->reached[s]) {
232        Parent::pushAndSetReached(s);
233      } else {
234        Parent::pushAndSetReached(s);
235        pred.set(s, INVALID);
236      }
237    }
238    /// A bfs is processed from s.
239    void run(Node s) {
240      push(s);
241      while (!this->finished()) this->operator++();
242    }
243    Dfs<Graph, ReachedMap, PredMap> operator++() {
244      Parent::operator++();
245      if (this->graph->valid(this->actual_edge) && this->b_node_newly_reached)
246      {
247        pred.set(this->bNode(), this->actual_edge);
248      }
249      return *this;
250    }
251    const PredMap& getPredMap() const { return pred; }
252  };
253
254
255} // namespace hugo
256
257#endif //HUGO_BFS_ITERATOR_H
Note: See TracBrowser for help on using the repository browser.