COIN-OR::LEMON - Graph Library

source: lemon-0.x/src/work/marci/bfs_dfs.h @ 650:588ff2ca55bd

Last change on this file since 650:588ff2ca55bd was 650:588ff2ca55bd, checked in by marci, 17 years ago

a

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) : BfsIterator<Graph, ReachedMap>(_graph, _reached), pred(&_pred), dist(&_dist) { }
155    /// \c s is marked to be reached and pushed in the bfs queue.
156    /// If the queue is empty, then the first out-edge is processed.
157    /// If \c s was not marked previously, then
158    /// in addition its pred is set to be \c INVALID, and dist to \c 0.
159    /// if \c s was marked previuosly, then it is simply pushed.
160    void push(Node s) {
161      if (this->reached[s]) {
162        Parent::pushAndSetReached(s);
163      } else {
164        Parent::pushAndSetReached(s);
165        pred.set(s, INVALID);
166        dist.set(s, 0);
167      }
168    }
169    /// A bfs is processed from \c s.
170    void run(Node s) {
171      push(s);
172      while (!this->finished()) this->operator++();
173    }
174    /// Beside the bfs iteration, \c pred and \dist are saved in a
175    /// newly reached node.
176    Bfs<Graph, ReachedMap, PredMap, DistMap>& operator++() {
177      Parent::operator++();
178      if (this->graph->valid(this->actual_edge) && this->b_node_newly_reached)
179      {
180        pred.set(this->bNode(), this->actual_edge);
181        dist.set(this->bNode(), dist[this->aNode()]);
182      }
183      return *this;
184    }
185    /// Guess what?
186    /// \deprecated
187    const PredMap& getPredMap() const { return pred; }
188    /// Guess what?
189    /// \deprecated
190    const DistMap& getDistMap() const { return dist; }
191  };
192
193  /// Dfs searches for the nodes wich are not marked in
194  /// \c reached_map
195  /// Reached have to be a read-write bool Node-map.
196  /// \ingroup galgs
197  template <typename Graph, /*typename OutEdgeIt,*/
198            typename ReachedMap/*=typename Graph::NodeMap<bool>*/ >
199  class DfsIterator {
200  protected:
201    typedef typename Graph::Node Node;
202    typedef typename Graph::OutEdgeIt OutEdgeIt;
203    const Graph* graph;
204    std::stack<OutEdgeIt> dfs_stack;
205    bool b_node_newly_reached;
206    OutEdgeIt actual_edge;
207    Node actual_node;
208    ReachedMap& reached;
209    bool own_reached_map;
210  public:
211    /// In that constructor \c _reached have to be a reference
212    /// for a bool node-map. The algorithm will search in a dfs order for
213    /// the nodes which are \c false initially
214    DfsIterator(const Graph& _graph, ReachedMap& _reached) :
215      graph(&_graph), reached(_reached),
216      own_reached_map(false) { }
217    /// The same as above, but the map of reached nodes is
218    /// constructed dynamically
219    /// to everywhere false.
220    DfsIterator(const Graph& _graph) :
221      graph(&_graph), reached(*(new ReachedMap(*graph /*, false*/))),
222      own_reached_map(true) { }
223    ~DfsIterator() { if (own_reached_map) delete &reached; }
224    /// This method markes s reached and first out-edge is processed.
225    void pushAndSetReached(Node s) {
226      actual_node=s;
227      reached.set(s, true);
228      OutEdgeIt e;
229      graph->first(e, s);
230      dfs_stack.push(e);
231    }
232    /// As \c DfsIterator<Graph, ReachedMap> works as an edge-iterator,
233    /// its \c operator++() iterates on the edges in a dfs order.
234    DfsIterator<Graph, /*OutEdgeIt,*/ ReachedMap>&
235    operator++() {
236      actual_edge=dfs_stack.top();
237      //actual_node=G.aNode(actual_edge);
238      if (graph->valid(actual_edge)/*.valid()*/) {
239        Node w=graph->bNode(actual_edge);
240        actual_node=w;
241        if (!reached[w]) {
242          OutEdgeIt e;
243          graph->first(e, w);
244          dfs_stack.push(e);
245          reached.set(w, true);
246          b_node_newly_reached=true;
247        } else {
248          actual_node=graph->aNode(actual_edge);
249          graph->next(dfs_stack.top());
250          b_node_newly_reached=false;
251        }
252      } else {
253        //actual_node=G.aNode(dfs_stack.top());
254        dfs_stack.pop();
255      }
256      return *this;
257    }
258    /// Returns true iff the algorithm is finished.
259    bool finished() const { return dfs_stack.empty(); }
260    /// The conversion operator makes for converting the bfs-iterator
261    /// to an \c out-edge-iterator.
262    ///\bug Edge have to be in HUGO 0.2
263    operator OutEdgeIt() const { return actual_edge; }
264    /// Returns if b-node has been reached just now.
265    bool isBNodeNewlyReached() const { return b_node_newly_reached; }
266    /// Returns if a-node is examined.
267    bool isANodeExamined() const { return !(graph->valid(actual_edge)); }
268    /// Returns a-node of the actual edge, so does if the edge is invalid.
269    Node aNode() const { return actual_node; /*FIXME*/}
270    /// Returns b-node of the actual edge.
271    /// \pre The actual edge have to be valid.
272    Node bNode() const { return graph->bNode(actual_edge); }
273    /// Guess what?
274    /// \deprecated
275    const ReachedMap& getReachedMap() const { return reached; }
276    /// Guess what?
277    /// \deprecated
278    const std::stack<OutEdgeIt>& getDfsStack() const { return dfs_stack; }
279  };
280
281  /// Dfs searches for the nodes wich are not marked in
282  /// \c reached_map
283  /// Reached is a read-write bool node-map,
284  /// Pred is a write node-map, have to be.
285  /// \ingroup galgs
286  template <typename Graph,
287            typename ReachedMap=typename Graph::template NodeMap<bool>,
288            typename PredMap
289            =typename Graph::template NodeMap<typename Graph::Edge> >
290  class Dfs : public DfsIterator<Graph, ReachedMap> {
291    typedef DfsIterator<Graph, ReachedMap> Parent;
292  protected:
293    typedef typename Parent::Node Node;
294    PredMap& pred;
295  public:
296    /// The algorithm will search in a dfs order for
297    /// the nodes which are \c false initially.
298    /// The constructor makes no initial changes on the maps.
299    Dfs<Graph, ReachedMap, PredMap>(const Graph& _graph, ReachedMap& _reached, PredMap& _pred) : DfsIterator<Graph, ReachedMap>(_graph, _reached), pred(&_pred) { }
300    /// \c s is marked to be reached and pushed in the bfs queue.
301    /// If the queue is empty, then the first out-edge is processed.
302    /// If \c s was not marked previously, then
303    /// in addition its pred is set to be \c INVALID.
304    /// if \c s was marked previuosly, then it is simply pushed.
305    void push(Node s) {
306      if (this->reached[s]) {
307        Parent::pushAndSetReached(s);
308      } else {
309        Parent::pushAndSetReached(s);
310        pred.set(s, INVALID);
311      }
312    }
313    /// A bfs is processed from \c s.
314    void run(Node s) {
315      push(s);
316      while (!this->finished()) this->operator++();
317    }
318    /// Beside the dfs iteration, \c pred is saved in a
319    /// newly reached node.
320    Dfs<Graph, ReachedMap, PredMap>& operator++() {
321      Parent::operator++();
322      if (this->graph->valid(this->actual_edge) && this->b_node_newly_reached)
323      {
324        pred.set(this->bNode(), this->actual_edge);
325      }
326      return *this;
327    }
328    /// Guess what?
329    /// \deprecated
330    const PredMap& getPredMap() const { return pred; }
331  };
332
333
334} // namespace hugo
335
336#endif //HUGO_BFS_DFS_H
Note: See TracBrowser for help on using the repository browser.