COIN-OR::LEMON - Graph Library

source: lemon-0.x/src/work/marci/bfs_dfs.h @ 691:014c2e4eb07b

Last change on this file since 691:014c2e4eb07b was 671:708df4dc6ab6, checked in by athos, 21 years ago

Compiles now

File size: 11.5 KB
RevLine 
[602]1// -*- c++ -*-
2#ifndef HUGO_BFS_DFS_H
3#define HUGO_BFS_DFS_H
4
[615]5/// \ingroup galgs
6/// \file
7/// \brief Bfs and dfs iterators.
[604]8///
[615]9/// This file contains bfs and dfs iterator classes.
[604]10///
[615]11// /// \author Marton Makai
[604]12
[602]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
[650]23  /// Reached have to be a read-write bool node-map.
[615]24  /// \ingroup galgs
[602]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
[650]39    /// for a bool bode-map. The algorithm will search for the
40    /// initially \c false nodes
41    /// in a bfs order.
[602]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.
[650]47    /// \deprecated
[602]48    BfsIterator(const Graph& _graph) :
49      graph(&_graph), reached(*(new ReachedMap(*graph /*, false*/))),
50      own_reached_map(true) { }
[604]51    /// The map storing the reached nodes have to be destroyed if
[602]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    }
[646]111    /// Returns true iff the algorithm is finished.
[602]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; }
[646]117    /// Returns if b-node has been reached just now.
[602]118    bool isBNodeNewlyReached() const { return b_node_newly_reached; }
[646]119    /// Returns if a-node is examined.
[602]120    bool isANodeExamined() const { return !(graph->valid(actual_edge)); }
[646]121    /// Returns a-node of the actual edge, so does if the edge is invalid.
[602]122    Node aNode() const { return bfs_queue.front(); }
[646]123    /// \pre The actual edge have to be valid.
[602]124    Node bNode() const { return graph->bNode(actual_edge); }
[615]125    /// Guess what?
[650]126    /// \deprecated
[602]127    const ReachedMap& getReachedMap() const { return reached; }
[615]128    /// Guess what?
[650]129    /// \deprecated
[602]130    const std::queue<Node>& getBfsQueue() const { return bfs_queue; }
[615]131  };
[602]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,
[650]136  /// Pred is a write edge node-map and
137  /// Dist is a read-write node-map of integral value, have to be.
[615]138  /// \ingroup galgs
[602]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.
[671]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) { }
[602]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.
[604]178    Bfs<Graph, ReachedMap, PredMap, DistMap>& operator++() {
[602]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    }
[615]187    /// Guess what?
[650]188    /// \deprecated
[602]189    const PredMap& getPredMap() const { return pred; }
[615]190    /// Guess what?
[650]191    /// \deprecated
[602]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.
[615]198  /// \ingroup galgs
[602]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
[650]214    /// for a bool node-map. The algorithm will search in a dfs order for
[602]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    }
[646]260    /// Returns true iff the algorithm is finished.
[602]261    bool finished() const { return dfs_stack.empty(); }
[646]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
[602]265    operator OutEdgeIt() const { return actual_edge; }
[646]266    /// Returns if b-node has been reached just now.
[602]267    bool isBNodeNewlyReached() const { return b_node_newly_reached; }
[646]268    /// Returns if a-node is examined.
[602]269    bool isANodeExamined() const { return !(graph->valid(actual_edge)); }
[646]270    /// Returns a-node of the actual edge, so does if the edge is invalid.
[602]271    Node aNode() const { return actual_node; /*FIXME*/}
[646]272    /// Returns b-node of the actual edge.
273    /// \pre The actual edge have to be valid.
[602]274    Node bNode() const { return graph->bNode(actual_edge); }
[615]275    /// Guess what?
[650]276    /// \deprecated
[602]277    const ReachedMap& getReachedMap() const { return reached; }
[615]278    /// Guess what?
[650]279    /// \deprecated
[602]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
[650]285  /// Reached is a read-write bool node-map,
286  /// Pred is a write node-map, have to be.
[615]287  /// \ingroup galgs
[602]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.
[671]301    Dfs<Graph, ReachedMap, PredMap>(const Graph& _graph, ReachedMap& _reached, PredMap& _pred) : DfsIterator<Graph, ReachedMap>(_graph, _reached), pred(_pred) { }
[602]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.
[604]322    Dfs<Graph, ReachedMap, PredMap>& operator++() {
[602]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    }
[615]330    /// Guess what?
[650]331    /// \deprecated
[602]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.