COIN-OR::LEMON - Graph Library

source: lemon-0.x/src/work/marci/bfs_dfs.h @ 773:ce9438c5a82d

Last change on this file since 773:ce9438c5a82d was 671:708df4dc6ab6, checked in by athos, 17 years ago

Compiles now

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