COIN-OR::LEMON - Graph Library

source: lemon-0.x/src/work/marci/bfs_iterator.h @ 560:5adcef1d7bcc

Last change on this file since 560:5adcef1d7bcc was 560:5adcef1d7bcc, checked in by marci, 16 years ago
File size: 8.5 KB
Line 
1// -*- c++ -*-
2#ifndef HUGO_BFS_ITERATOR_H
3#define HUGO_BFS_ITERATOR_H
4
5#include <queue>
6#include <stack>
7#include <utility>
8
9#include <hugo/invalid.h>
10
11namespace hugo {
12
13  template <typename Graph, /*typename OutEdgeIt,*/
14            typename ReachedMap/*=typename Graph::NodeMap<bool>*/ >
15  class BfsIterator {
16  protected:
17    typedef typename Graph::Node Node;
18    typedef typename Graph::OutEdgeIt OutEdgeIt;
19    const Graph* graph;
20    std::queue<Node> bfs_queue;
21    ReachedMap& reached;
22    bool b_node_newly_reached;
23    OutEdgeIt actual_edge;
24    bool own_reached_map;
25  public:
26    BfsIterator(const Graph& _graph, ReachedMap& _reached) :
27      graph(&_graph), reached(_reached),
28      own_reached_map(false) { }
29    BfsIterator(const Graph& _graph) :
30      graph(&_graph), reached(*(new ReachedMap(*graph /*, false*/))),
31      own_reached_map(true) { }
32    ~BfsIterator() { if (own_reached_map) delete &reached; }
33    /// This method markes s reached.
34    /// If the queue is empty, then s is pushed in the bfs queue
35    /// and the first OutEdgeIt is processed.
36    /// If the queue is not empty, then s is simply pushed.
37    void pushAndSetReached(Node s) {
38      reached.set(s, true);
39      if (bfs_queue.empty()) {
40        bfs_queue.push(s);
41        graph->first(actual_edge, s);
42        if (graph->valid(actual_edge)) {
43          Node w=graph->bNode(actual_edge);
44          if (!reached[w]) {
45            bfs_queue.push(w);
46            reached.set(w, true);
47            b_node_newly_reached=true;
48          } else {
49            b_node_newly_reached=false;
50          }
51        }
52      } else {
53        bfs_queue.push(s);
54      }
55    }
56    /// As \c BfsIterator<Graph, ReachedMap> works as an edge-iterator,
57    /// its \c operator++() iterates on the edges in a bfs order.
58    BfsIterator<Graph, /*OutEdgeIt,*/ ReachedMap>&
59    operator++() {
60      if (graph->valid(actual_edge)) {
61        graph->next(actual_edge);
62        if (graph->valid(actual_edge)) {
63          Node w=graph->bNode(actual_edge);
64          if (!reached[w]) {
65            bfs_queue.push(w);
66            reached.set(w, true);
67            b_node_newly_reached=true;
68          } else {
69            b_node_newly_reached=false;
70          }
71        }
72      } else {
73        bfs_queue.pop();
74        if (!bfs_queue.empty()) {
75          graph->first(actual_edge, bfs_queue.front());
76          if (graph->valid(actual_edge)) {
77            Node w=graph->bNode(actual_edge);
78            if (!reached[w]) {
79              bfs_queue.push(w);
80              reached.set(w, true);
81              b_node_newly_reached=true;
82            } else {
83              b_node_newly_reached=false;
84            }
85          }
86        }
87      }
88      return *this;
89    }
90    bool finished() const { return bfs_queue.empty(); }
91    /// The conversion operator makes for converting the bfs-iterator
92    /// to an \c out-edge-iterator.
93    operator OutEdgeIt() const { return actual_edge; }
94    bool isBNodeNewlyReached() const { return b_node_newly_reached; }
95    bool isANodeExamined() const { return !(graph->valid(actual_edge)); }
96    Node aNode() const { return bfs_queue.front(); }
97    Node bNode() const { return graph->bNode(actual_edge); }
98    const ReachedMap& getReachedMap() const { return reached; }
99    const std::queue<Node>& getBfsQueue() const { return bfs_queue; }
100  }; 
101
102  /// Bfs searches from s for the nodes wich are not marked in
103  /// \c reached_map
104  /// Reached is a read-write bool-map, Pred is a write-nodemap
105  /// and dist is an rw-nodemap, have to be.
106  template <typename Graph,
107            typename ReachedMap=typename Graph::template NodeMap<bool>,
108            typename PredMap
109            =typename Graph::template NodeMap<typename Graph::Edge>,
110            typename DistMap=typename Graph::template NodeMap<int> >
111  class Bfs : public BfsIterator<Graph, ReachedMap> {
112    typedef BfsIterator<Graph, ReachedMap> Parent;
113  protected:
114    typedef typename Parent::Node Node;
115    PredMap& pred;
116    DistMap& dist;
117  public:
118    Bfs<Graph, ReachedMap, PredMap, DistMap>(const Graph& _graph, ReachedMap& _reached, PredMap& _pred, DistMap& _dist) : BfsIterator<Graph, ReachedMap>(_graph, _reached), pred(&_pred), dist(&_dist) { }
119    /// s is marked to be reached and pushed in the bfs queue.
120    /// If the queue is empty, then the first out-edge is processed.
121    /// If s was not marked previously, then
122    /// in addition its pred is set to be INVALID, and dist to 0.
123    /// if s was marked previuosly, then it is simply pushed.
124    void push(Node s) {
125      if (this->reached[s]) {
126        Parent::pushAndSetReached(s);
127      } else {
128        Parent::pushAndSetReached(s);
129        pred.set(s, INVALID);
130        dist.set(s, 0);
131      }
132    }
133    /// A bfs is processed from s.
134    void run(Node s) {
135      push(s);
136      while (!this->finished()) this->operator++();
137    }
138    Bfs<Graph, ReachedMap, PredMap, DistMap> operator++() {
139      Parent::operator++();
140      if (this->graph->valid(this->actual_edge) && this->b_node_newly_reached)
141      {
142        pred.set(this->bNode(), this->actual_edge);
143        dist.set(this->bNode(), dist[this->aNode()]);
144      }
145      return *this;
146    }
147    const PredMap& getPredMap() const { return pred; }
148    const DistMap& getDistMap() const { return dist; }
149  };
150
151  template <typename Graph, /*typename OutEdgeIt,*/
152            typename ReachedMap/*=typename Graph::NodeMap<bool>*/ >
153  class DfsIterator {
154  protected:
155    typedef typename Graph::Node Node;
156    typedef typename Graph::OutEdgeIt OutEdgeIt;
157    const Graph* graph;
158    std::stack<OutEdgeIt> dfs_stack;
159    bool b_node_newly_reached;
160    OutEdgeIt actual_edge;
161    Node actual_node;
162    ReachedMap& reached;
163    bool own_reached_map;
164  public:
165    DfsIterator(const Graph& _graph, ReachedMap& _reached) :
166      graph(&_graph), reached(_reached),
167      own_reached_map(false) { }
168    DfsIterator(const Graph& _graph) :
169      graph(&_graph), reached(*(new ReachedMap(*graph /*, false*/))),
170      own_reached_map(true) { }
171    ~DfsIterator() { if (own_reached_map) delete &reached; }
172    void pushAndSetReached(Node s) {
173      actual_node=s;
174      reached.set(s, true);
175      OutEdgeIt e;
176      graph->first(e, s);
177      dfs_stack.push(e);
178    }
179    DfsIterator<Graph, /*OutEdgeIt,*/ ReachedMap>&
180    operator++() {
181      actual_edge=dfs_stack.top();
182      //actual_node=G.aNode(actual_edge);
183      if (graph->valid(actual_edge)/*.valid()*/) {
184        Node w=graph->bNode(actual_edge);
185        actual_node=w;
186        if (!reached[w]) {
187          OutEdgeIt e;
188          graph->first(e, w);
189          dfs_stack.push(e);
190          reached.set(w, true);
191          b_node_newly_reached=true;
192        } else {
193          actual_node=graph->aNode(actual_edge);
194          graph->next(dfs_stack.top());
195          b_node_newly_reached=false;
196        }
197      } else {
198        //actual_node=G.aNode(dfs_stack.top());
199        dfs_stack.pop();
200      }
201      return *this;
202    }
203    bool finished() const { return dfs_stack.empty(); }
204    operator OutEdgeIt() const { return actual_edge; }
205    bool isBNodeNewlyReached() const { return b_node_newly_reached; }
206    bool isANodeExamined() const { return !(graph->valid(actual_edge)); }
207    Node aNode() const { return actual_node; /*FIXME*/}
208    Node bNode() const { return graph->bNode(actual_edge); }
209    const ReachedMap& getReachedMap() const { return reached; }
210    const std::stack<OutEdgeIt>& getDfsStack() const { return dfs_stack; }
211  };
212
213  /// Dfs searches from s for the nodes wich are not marked in
214  /// \c reached_map
215  /// Reached is a read-write bool-map, Pred is a write-nodemap, have to be.
216  template <typename Graph,
217            typename ReachedMap=typename Graph::template NodeMap<bool>,
218            typename PredMap
219            =typename Graph::template NodeMap<typename Graph::Edge> >
220  class Dfs : public DfsIterator<Graph, ReachedMap> {
221    typedef DfsIterator<Graph, ReachedMap> Parent;
222  protected:
223    typedef typename Parent::Node Node;
224    PredMap& pred;
225  public:
226    Dfs<Graph, ReachedMap, PredMap>(const Graph& _graph, ReachedMap& _reached, PredMap& _pred) : DfsIterator<Graph, ReachedMap>(_graph, _reached), pred(&_pred) { }
227    /// s is marked to be reached and pushed in the bfs queue.
228    /// If the queue is empty, then the first out-edge is processed.
229    /// If s was not marked previously, then
230    /// in addition its pred is set to be INVALID.
231    /// if s was marked previuosly, then it is simply pushed.
232    void push(Node s) {
233      if (this->reached[s]) {
234        Parent::pushAndSetReached(s);
235      } else {
236        Parent::pushAndSetReached(s);
237        pred.set(s, INVALID);
238      }
239    }
240    /// A bfs is processed from s.
241    void run(Node s) {
242      push(s);
243      while (!this->finished()) this->operator++();
244    }
245    Dfs<Graph, ReachedMap, PredMap> operator++() {
246      Parent::operator++();
247      if (this->graph->valid(this->actual_edge) && this->b_node_newly_reached)
248      {
249        pred.set(this->bNode(), this->actual_edge);
250      }
251      return *this;
252    }
253    const PredMap& getPredMap() const { return pred; }
254  };
255
256
257} // namespace hugo
258
259#endif //HUGO_BFS_ITERATOR_H
Note: See TracBrowser for help on using the repository browser.