COIN-OR::LEMON - Graph Library

source: lemon-0.x/src/work/marci/bfs_dfs.h @ 604:4acd273c3009

Last change on this file since 604:4acd273c3009 was 604:4acd273c3009, checked in by marci, 17 years ago

some docs

File size: 10.6 KB
Line 
1// -*- c++ -*-
2#ifndef HUGO_BFS_DFS_H
3#define HUGO_BFS_DFS_H
4
5// ///\ingroup gwrappers
6///\file
7///\brief Bfs and dfs iterators.
8///
9///This file contains bfs and dfs iterator classes.
10///
11// ///\author Marton Makai
12
13#include <queue>
14#include <stack>
15#include <utility>
16
17#include <hugo/invalid.h>
18
19namespace hugo {
20
21  /// Bfs searches for the nodes wich are not marked in
22  /// \c reached_map
23  /// Reached have to work as read-write bool Node-map.
24  template <typename Graph, /*typename OutEdgeIt,*/
25            typename ReachedMap/*=typename Graph::NodeMap<bool>*/ >
26  class BfsIterator {
27  protected:
28    typedef typename Graph::Node Node;
29    typedef typename Graph::OutEdgeIt OutEdgeIt;
30    const Graph* graph;
31    std::queue<Node> bfs_queue;
32    ReachedMap& reached;
33    bool b_node_newly_reached;
34    OutEdgeIt actual_edge;
35    bool own_reached_map;
36  public:
37    /// In that constructor \c _reached have to be a reference
38    /// for a bool Node-map. The algorithm will search in a bfs order for
39    /// the nodes which are \c false initially
40    BfsIterator(const Graph& _graph, ReachedMap& _reached) :
41      graph(&_graph), reached(_reached),
42      own_reached_map(false) { }
43    /// The same as above, but the map storing the reached nodes
44    /// is constructed dynamically to everywhere false.
45    BfsIterator(const Graph& _graph) :
46      graph(&_graph), reached(*(new ReachedMap(*graph /*, false*/))),
47      own_reached_map(true) { }
48    /// The map storing the reached nodes have to be destroyed if
49    /// it was constructed dynamically
50    ~BfsIterator() { if (own_reached_map) delete &reached; }
51    /// This method markes \c s reached.
52    /// If the queue is empty, then \c s is pushed in the bfs queue
53    /// and the first out-edge is processed.
54    /// If the queue is not empty, then \c s is simply pushed.
55    void pushAndSetReached(Node s) {
56      reached.set(s, true);
57      if (bfs_queue.empty()) {
58        bfs_queue.push(s);
59        graph->first(actual_edge, s);
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.push(s);
72      }
73    }
74    /// As \c BfsIterator<Graph, ReachedMap> works as an edge-iterator,
75    /// its \c operator++() iterates on the edges in a bfs order.
76    BfsIterator<Graph, /*OutEdgeIt,*/ ReachedMap>&
77    operator++() {
78      if (graph->valid(actual_edge)) {
79        graph->next(actual_edge);
80        if (graph->valid(actual_edge)) {
81          Node w=graph->bNode(actual_edge);
82          if (!reached[w]) {
83            bfs_queue.push(w);
84            reached.set(w, true);
85            b_node_newly_reached=true;
86          } else {
87            b_node_newly_reached=false;
88          }
89        }
90      } else {
91        bfs_queue.pop();
92        if (!bfs_queue.empty()) {
93          graph->first(actual_edge, bfs_queue.front());
94          if (graph->valid(actual_edge)) {
95            Node w=graph->bNode(actual_edge);
96            if (!reached[w]) {
97              bfs_queue.push(w);
98              reached.set(w, true);
99              b_node_newly_reached=true;
100            } else {
101              b_node_newly_reached=false;
102            }
103          }
104        }
105      }
106      return *this;
107    }
108    ///
109    bool finished() const { return bfs_queue.empty(); }
110    /// The conversion operator makes for converting the bfs-iterator
111    /// to an \c out-edge-iterator.
112    ///\bug Edge have to be in HUGO 0.2
113    operator OutEdgeIt() const { return actual_edge; }
114    ///
115    bool isBNodeNewlyReached() const { return b_node_newly_reached; }
116    ///
117    bool isANodeExamined() const { return !(graph->valid(actual_edge)); }
118    ///
119    Node aNode() const { return bfs_queue.front(); }
120    ///
121    Node bNode() const { return graph->bNode(actual_edge); }
122    ///
123    const ReachedMap& getReachedMap() const { return reached; }
124    ///
125    const std::queue<Node>& getBfsQueue() const { return bfs_queue; }
126  }; 
127
128  /// Bfs searches for the nodes wich are not marked in
129  /// \c reached_map
130  /// Reached have to work as a read-write bool Node-map,
131  /// Pred is a write Edge Node-map and
132  /// Dist is a read-write int Node-map, have to be.
133  ///\todo In fact onsly simple operations requirement are needed for
134  /// Dist::Value.
135  template <typename Graph,
136            typename ReachedMap=typename Graph::template NodeMap<bool>,
137            typename PredMap
138            =typename Graph::template NodeMap<typename Graph::Edge>,
139            typename DistMap=typename Graph::template NodeMap<int> >
140  class Bfs : public BfsIterator<Graph, ReachedMap> {
141    typedef BfsIterator<Graph, ReachedMap> Parent;
142  protected:
143    typedef typename Parent::Node Node;
144    PredMap& pred;
145    DistMap& dist;
146  public:
147    /// The algorithm will search in a bfs order for
148    /// the nodes which are \c false initially.
149    /// The constructor makes no initial changes on the maps.
150    Bfs<Graph, ReachedMap, PredMap, DistMap>(const Graph& _graph, ReachedMap& _reached, PredMap& _pred, DistMap& _dist) : BfsIterator<Graph, ReachedMap>(_graph, _reached), pred(&_pred), dist(&_dist) { }
151    /// \c s is marked to be reached and pushed in the bfs queue.
152    /// If the queue is empty, then the first out-edge is processed.
153    /// If \c s was not marked previously, then
154    /// in addition its pred is set to be \c INVALID, and dist to \c 0.
155    /// if \c s was marked previuosly, then it is simply pushed.
156    void push(Node s) {
157      if (this->reached[s]) {
158        Parent::pushAndSetReached(s);
159      } else {
160        Parent::pushAndSetReached(s);
161        pred.set(s, INVALID);
162        dist.set(s, 0);
163      }
164    }
165    /// A bfs is processed from \c s.
166    void run(Node s) {
167      push(s);
168      while (!this->finished()) this->operator++();
169    }
170    /// Beside the bfs iteration, \c pred and \dist are saved in a
171    /// newly reached node.
172    Bfs<Graph, ReachedMap, PredMap, DistMap>& operator++() {
173      Parent::operator++();
174      if (this->graph->valid(this->actual_edge) && this->b_node_newly_reached)
175      {
176        pred.set(this->bNode(), this->actual_edge);
177        dist.set(this->bNode(), dist[this->aNode()]);
178      }
179      return *this;
180    }
181    ///
182    const PredMap& getPredMap() const { return pred; }
183    ///
184    const DistMap& getDistMap() const { return dist; }
185  };
186
187  /// Dfs searches for the nodes wich are not marked in
188  /// \c reached_map
189  /// Reached have to be a read-write bool Node-map.
190  template <typename Graph, /*typename OutEdgeIt,*/
191            typename ReachedMap/*=typename Graph::NodeMap<bool>*/ >
192  class DfsIterator {
193  protected:
194    typedef typename Graph::Node Node;
195    typedef typename Graph::OutEdgeIt OutEdgeIt;
196    const Graph* graph;
197    std::stack<OutEdgeIt> dfs_stack;
198    bool b_node_newly_reached;
199    OutEdgeIt actual_edge;
200    Node actual_node;
201    ReachedMap& reached;
202    bool own_reached_map;
203  public:
204    /// In that constructor \c _reached have to be a reference
205    /// for a bool Node-map. The algorithm will search in a dfs order for
206    /// the nodes which are \c false initially
207    DfsIterator(const Graph& _graph, ReachedMap& _reached) :
208      graph(&_graph), reached(_reached),
209      own_reached_map(false) { }
210    /// The same as above, but the map of reached nodes is
211    /// constructed dynamically
212    /// to everywhere false.
213    DfsIterator(const Graph& _graph) :
214      graph(&_graph), reached(*(new ReachedMap(*graph /*, false*/))),
215      own_reached_map(true) { }
216    ~DfsIterator() { if (own_reached_map) delete &reached; }
217    /// This method markes s reached and first out-edge is processed.
218    void pushAndSetReached(Node s) {
219      actual_node=s;
220      reached.set(s, true);
221      OutEdgeIt e;
222      graph->first(e, s);
223      dfs_stack.push(e);
224    }
225    /// As \c DfsIterator<Graph, ReachedMap> works as an edge-iterator,
226    /// its \c operator++() iterates on the edges in a dfs order.
227    DfsIterator<Graph, /*OutEdgeIt,*/ ReachedMap>&
228    operator++() {
229      actual_edge=dfs_stack.top();
230      //actual_node=G.aNode(actual_edge);
231      if (graph->valid(actual_edge)/*.valid()*/) {
232        Node w=graph->bNode(actual_edge);
233        actual_node=w;
234        if (!reached[w]) {
235          OutEdgeIt e;
236          graph->first(e, w);
237          dfs_stack.push(e);
238          reached.set(w, true);
239          b_node_newly_reached=true;
240        } else {
241          actual_node=graph->aNode(actual_edge);
242          graph->next(dfs_stack.top());
243          b_node_newly_reached=false;
244        }
245      } else {
246        //actual_node=G.aNode(dfs_stack.top());
247        dfs_stack.pop();
248      }
249      return *this;
250    }
251    ///
252    bool finished() const { return dfs_stack.empty(); }
253    ///
254    operator OutEdgeIt() const { return actual_edge; }
255    ///
256    bool isBNodeNewlyReached() const { return b_node_newly_reached; }
257    ///
258    bool isANodeExamined() const { return !(graph->valid(actual_edge)); }
259    ///
260    Node aNode() const { return actual_node; /*FIXME*/}
261    ///
262    Node bNode() const { return graph->bNode(actual_edge); }
263    ///
264    const ReachedMap& getReachedMap() const { return reached; }
265    ///
266    const std::stack<OutEdgeIt>& getDfsStack() const { return dfs_stack; }
267  };
268
269  /// Dfs searches for the nodes wich are not marked in
270  /// \c reached_map
271  /// Reached is a read-write bool Node-map,
272  /// Pred is a write Node-map, have to be.
273  template <typename Graph,
274            typename ReachedMap=typename Graph::template NodeMap<bool>,
275            typename PredMap
276            =typename Graph::template NodeMap<typename Graph::Edge> >
277  class Dfs : public DfsIterator<Graph, ReachedMap> {
278    typedef DfsIterator<Graph, ReachedMap> Parent;
279  protected:
280    typedef typename Parent::Node Node;
281    PredMap& pred;
282  public:
283    /// The algorithm will search in a dfs order for
284    /// the nodes which are \c false initially.
285    /// The constructor makes no initial changes on the maps.
286    Dfs<Graph, ReachedMap, PredMap>(const Graph& _graph, ReachedMap& _reached, PredMap& _pred) : DfsIterator<Graph, ReachedMap>(_graph, _reached), pred(&_pred) { }
287    /// \c s is marked to be reached and pushed in the bfs queue.
288    /// If the queue is empty, then the first out-edge is processed.
289    /// If \c s was not marked previously, then
290    /// in addition its pred is set to be \c INVALID.
291    /// if \c s was marked previuosly, then it is simply pushed.
292    void push(Node s) {
293      if (this->reached[s]) {
294        Parent::pushAndSetReached(s);
295      } else {
296        Parent::pushAndSetReached(s);
297        pred.set(s, INVALID);
298      }
299    }
300    /// A bfs is processed from \c s.
301    void run(Node s) {
302      push(s);
303      while (!this->finished()) this->operator++();
304    }
305    /// Beside the dfs iteration, \c pred is saved in a
306    /// newly reached node.
307    Dfs<Graph, ReachedMap, PredMap>& operator++() {
308      Parent::operator++();
309      if (this->graph->valid(this->actual_edge) && this->b_node_newly_reached)
310      {
311        pred.set(this->bNode(), this->actual_edge);
312      }
313      return *this;
314    }
315    ///
316    const PredMap& getPredMap() const { return pred; }
317  };
318
319
320} // namespace hugo
321
322#endif //HUGO_BFS_DFS_H
Note: See TracBrowser for help on using the repository browser.