COIN-OR::LEMON - Graph Library

source: lemon-0.x/src/work/marci/bfs_dfs.h @ 602:580b329c2a0c

Last change on this file since 602:580b329c2a0c was 602:580b329c2a0c, checked in by marci, 17 years ago

bfs_iterator -> bfs_dfs.h, some docs

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