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