COIN-OR::LEMON - Graph Library

source: lemon-0.x/src/work/marci/bfs_dfs.h @ 643:f8053cb51047

Last change on this file since 643:f8053cb51047 was 615:b6b31b75b522, checked in by marci, 20 years ago

docs, max_flow improvments

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