COIN-OR::LEMON - Graph Library

source: lemon-0.x/src/work/marci/bfs_dfs.h @ 777:a82713ed19f3

Last change on this file since 777:a82713ed19f3 was 777:a82713ed19f3, checked in by marci, 20 years ago

graph_wrapper.h is ready for hugo 0.2

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