This is not ready yet, but I have to go home...
2 #ifndef LEMON_BFS_DFS_H
3 #define LEMON_BFS_DFS_H
7 /// \brief Bfs and dfs iterators.
9 /// This file contains bfs and dfs iterator classes.
11 // /// \author Marton Makai
17 #include <lemon/invalid.h>
22 /// Bfs searches for the nodes wich are not marked in
24 /// RM have to be a read-write bool node-map.
26 template <typename Graph, /*typename OutEdgeIt,*/
27 typename RM/*=typename Graph::NodeMap<bool>*/ >
30 typedef RM ReachedMap;
32 typedef typename Graph::Node Node;
33 typedef typename Graph::Edge Edge;
34 typedef typename Graph::OutEdgeIt OutEdgeIt;
36 std::queue<Node> bfs_queue;
37 ReachedMap* reached_map;
38 bool b_node_newly_reached;
39 //OutEdgeIt actual_edge;
42 BfsIterator(const Graph& _graph) : graph(&_graph), reached_map(0) { }
43 /// RM have to be set before any bfs operation.
44 BfsIterator<Graph, RM>& setReached(RM& _reached_map) {
45 reached_map=&_reached_map;
48 /// In that constructor \c _reached_map have to be a reference
49 /// for a bool bode-map. The algorithm will search for the
50 /// initially \c false nodes
52 BfsIterator(const Graph& _graph, ReachedMap& _reached_map) :
53 graph(&_graph), reached_map(&_reached_map) { }
54 /// The same as above, but the map storing the reached nodes
55 /// is constructed dynamically to everywhere false.
57 // BfsIterator(const Graph& _graph) :
58 // graph(&_graph), reached_map(new ReachedMap(*graph /*, false*/)),
59 // own_reached_map(true) { }
60 // /// The map storing the reached nodes have to be destroyed if
61 // /// it was constructed dynamically
62 // ~BfsIterator() { if (own_reached_map) delete reached_map; }
63 /// This method markes \c s reached.
64 /// If the queue is empty, then \c s is pushed in the bfs queue
65 /// and the first out-edge is processed.
66 /// If the queue is not empty, then \c s is simply pushed.
67 BfsIterator<Graph, /*OutEdgeIt,*/ ReachedMap>& pushAndSetReached(Node s) {
68 reached_map->set(s, true);
69 if (bfs_queue.empty()) {
71 actual_edge=OutEdgeIt(*graph, s);
72 //graph->first(actual_edge, s);
73 if (actual_edge!=INVALID) {
74 Node w=graph->target(actual_edge);
75 if (!(*reached_map)[w]) {
77 reached_map->set(w, true);
78 b_node_newly_reached=true;
80 b_node_newly_reached=false;
88 /// As \c BfsIterator<Graph, ReachedMap> works as an edge-iterator,
89 /// its \c operator++() iterates on the edges in a bfs order.
90 BfsIterator<Graph, /*OutEdgeIt,*/ ReachedMap>&
92 if (actual_edge!=INVALID) {
93 actual_edge=++OutEdgeIt(*graph, actual_edge);
95 if (actual_edge!=INVALID) {
96 Node w=graph->target(actual_edge);
97 if (!(*reached_map)[w]) {
99 reached_map->set(w, true);
100 b_node_newly_reached=true;
102 b_node_newly_reached=false;
107 if (!bfs_queue.empty()) {
108 actual_edge=OutEdgeIt(*graph, bfs_queue.front());
109 //graph->first(actual_edge, bfs_queue.front());
110 if (actual_edge!=INVALID) {
111 Node w=graph->target(actual_edge);
112 if (!(*reached_map)[w]) {
114 reached_map->set(w, true);
115 b_node_newly_reached=true;
117 b_node_newly_reached=false;
124 /// Returns true iff the algorithm is finished.
125 bool finished() const { return bfs_queue.empty(); }
126 /// The conversion operator makes for converting the bfs-iterator
127 /// to an \c out-edge-iterator.
128 ///\bug Edge have to be in LEMON 0.2
129 operator Edge() const { return actual_edge; }
130 /// Returns if b-node has been reached just now.
131 bool isBNodeNewlyReached() const { return b_node_newly_reached; }
132 /// Returns if a-node is examined.
133 bool isANodeExamined() const { return actual_edge==INVALID; }
134 /// Returns a-node of the actual edge, so does if the edge is invalid.
135 Node source() const { return bfs_queue.front(); }
136 /// \pre The actual edge have to be valid.
137 Node target() const { return graph->target(actual_edge); }
140 const ReachedMap& reachedMap() const { return *reached_map; }
143 typename ReachedMap::Value reached(const Node& n) const {
144 return (*reached_map)[n];
148 const std::queue<Node>& getBfsQueue() const { return bfs_queue; }
151 /// Bfs searches for the nodes wich are not marked in
153 /// RM have to work as a read-write bool Node-map,
154 /// PM is a write edge node-map and
155 /// PNM is a write node node-map and
156 /// DM is a read-write node-map of integral value, have to be.
158 template <typename Graph,
159 typename RM=typename Graph::template NodeMap<bool>,
161 =typename Graph::template NodeMap<typename Graph::Edge>,
163 =typename Graph::template NodeMap<typename Graph::Node>,
164 typename DM=typename Graph::template NodeMap<int> >
165 class Bfs : public BfsIterator<Graph, RM> {
166 typedef BfsIterator<Graph, RM> Parent;
168 typedef RM ReachedMap;
170 typedef PNM PredNodeMap;
173 typedef typename Parent::Node Node;
175 PredNodeMap* pred_node_map;
178 Bfs<Graph, RM, PM, PNM, DM>
179 (const Graph& _graph) : BfsIterator<Graph, RM>(_graph) { }
180 /// PM have to be set before any bfs operation.
181 Bfs<Graph, RM, PM, PNM, DM>&
182 setPredMap(PredMap& _pred_map) {
185 /// PredNodeMap have to be set before any bfs operation.
186 Bfs<Graph, RM, PM, PNM, DM>&
187 setPredNodeMap(PredNodeMap& _pred_node_map) {
188 pred_node_map=&_pred_node_map;
190 /// DistMap have to be set before any bfs operation.
191 Bfs<Graph, RM, PM, PNM, DM>&
192 setDistMap(DistMap& _dist_map) {
196 /// The algorithm will search in a bfs order for
197 /// the nodes which are \c false initially.
198 /// The constructor makes no initial changes on the maps.
199 Bfs<Graph, RM, PM, PNM, DM>
200 (const Graph& _graph, ReachedMap& _reached_map,
201 PredMap& _pred_map, PredNodeMap& _pred_node_map,
202 DistMap& _dist_map) : BfsIterator<Graph, RM>(_graph, _reached_map),
203 pred_map(&_pred_map), pred_node_map(&_pred_node_map),
204 dist_map(&_dist_map) { }
205 /// \c s is marked to be reached and pushed in the bfs queue.
206 /// If the queue is empty, then the first out-edge is processed.
207 /// If \c s was not marked previously, then
208 /// in addition its pred_map is set to be \c INVALID,
209 /// and dist_map to \c 0.
210 /// if \c s was marked previuosly, then it is simply pushed.
211 Bfs<Graph, RM, PM, PNM, DM>& push(Node s) {
212 if ((*(this->reached_map))[s]) {
213 Parent::pushAndSetReached(s);
215 Parent::pushAndSetReached(s);
216 pred_map->set(s, INVALID);
217 pred_node_map->set(s, INVALID);
222 /// A bfs is processed from \c s.
223 Bfs<Graph, RM, PM, PNM, DM>& run(Node s) {
225 while (!this->finished()) this->operator++();
228 /// Beside the bfs iteration, \c pred_map and \dist_map are saved in a
229 /// newly reached node.
230 Bfs<Graph, RM, PM, PNM, DM>& operator++() {
231 Parent::operator++();
232 if ((this->actual_edge)!=INVALID && this->b_node_newly_reached)
234 pred_map->set(this->target(), this->actual_edge);
235 pred_node_map->set(this->target(), this->source());
236 dist_map->set(this->target(), (*dist_map)[this->source()]);
242 const PredMap& predMap() const { return *pred_map; }
245 typename PredMap::Value pred(const Node& n) const {
246 return (*pred_map)[n];
250 const PredNodeMap& predNodeMap() const { return *pred_node_map; }
253 typename PredNodeMap::Value predNode(const Node& n) const {
254 return (*pred_node_map)[n];
258 const DistMap& distMap() const { return *dist_map; }
261 typename DistMap::Value dist(const Node& n) const {
262 return (*dist_map)[n];
266 // template <typename Graph,
267 // typename RM=typename Graph::template NodeMap<bool>,
269 // =typename Graph::template NodeMap<typename Graph::Edge>,
270 // typename PredNodeMap
271 // =typename Graph::template NodeMap<typename Graph::Node>,
272 // typename DistMap=typename Graph::template NodeMap<int> >
273 // class BfsWizard : public Bfs<Graph> {
275 // typedef Bfs<Graph, PM, PredNodeMap, DistMap> Parent;
277 // typedef typename Parent::Node Node;
278 // bool own_reached_map;
279 // bool own_pred_map;
280 // bool own_pred_node_map;
281 // bool own_dist_map;
283 // BfsWizard<Graph, RM, PM, PredNodeMap, DistMap>&
285 // own_reached_map=true;
286 // reached=new ReachedMap(*graph, false);
288 // BfsWizard<Graph, RM, PM, PredNodeMap, DistMap>&
289 // deleteReachedMap() {
290 // own_reached_map=false;
294 // BfsWizard<Graph, RM, PM, PredNodeMap, DistMap>&
296 // own_pred_map=true;
297 // pred_map=new PM(*graph, INVALID);
299 // BfsWizard<Graph, ReachedMap, PM, PredNodeMap, DistMap>&
301 // own_pred_map=false;
305 // BfsWizard<Graph, RM, PM, PredNodeMap, DistMap>&
306 // makePredNodeMap() {
307 // own_pred_node_map=true;
308 // pred_node_map=new PredNodeMap(*graph, INVALID);
310 // BfsWizard<Graph, RM, PM, PredNodeMap, DistMap>&
311 // deletePredNodeMap() {
312 // own_pred_node_map=false;
313 // delete pred_node_map;
316 // BfsWizard<Graph, RM, PM, PredNodeMap, DistMap>&
318 // own_dist_map=true;
319 // dist_map=new DistMap(*graph, 0);
321 // BfsWizard<Graph, RM, PM, PredNodeMap, DistMap>&
323 // own_dist_map=false;
328 // /// User friendly Bfs class.
329 // /// The maps which are not explicitly given by the user are
330 // /// constructed with false, INVALID, INVALID and 0 values.
331 // /// For the user defined maps, the values are not modified, and
332 // /// the bfs is processed without any preset on maps. Therefore,
333 // /// the bfs will search only the nodes which are set false previously
334 // /// in reached, and in the nodes wich are not newly reached by the
335 // /// search, the map values are not modified.
336 // BfsWizard<Graph, RM, PM, PredNodeMap, DistMap>
337 // (const Graph& _graph) :
338 // own_reached_map(false),
339 // own_pred_map(false),
340 // own_pred_node_map(false),
341 // own_dist_map(false) {
345 // ~BfsWizard<Graph, RM, PM, PredNodeMap, DistMap>() {
346 // if (own_reached_map) deleteReachedMap();
347 // if (own_pred_map) deletePM();
348 // if (own_pred_node_map) deletePredNodeMap();
349 // if (own_dist_map) deleteDistMap();
353 // BfsWizard<Graph, RM, PM, PredNodeMap, DistMap>&
354 // setReachedMap(ReachedMap& _reached) {
355 // if (own_reached_map) deleteReachedMap();
356 // Parent::setReachedMap(_reached);
359 // BfsWizard<Graph, RM, PM, PredNodeMap, DistMap>&
360 // setPM(PM& _pred) {
361 // if (own_pred_map) deletePM();
362 // Parent::setPM(_pred);
365 // BfsWizard<Graph, RM, PM, PredNodeMap, DistMap>&
366 // setPredNodeMap(PredNodeMap& _pred_node) {
367 // if (own_pred_node_map) deletePredNodeMap();
368 // Parent::setPredNodeMap(_pred_node);
371 // BfsWizard<Graph, RM, PM, PredNodeMap, DistMap>&
372 // setDistMap(DistMap& _dist) {
373 // if (own_dist_map) deleteDistMap();
374 // Parent::setDistMap(_dist);
378 // BfsWizard<Graph, RM, PM, PredNodeMap, DistMap>&
380 // if (!reached) makeReachedMap();
381 // if (!pred_map) makePMMap();
382 // if (!pred_node_map) makePredNodeMap();
383 // if (!dist_map) makeDistMap();
389 // BfsWizard<Graph, RM, PM, PredNodeMap, DistMap>&
391 // if (!reached) makeRM();
392 // if (!pred_map) makePMMap();
393 // if (!pred_node_map) makePredNodeMap();
394 // if (!dist_map) makeDistMap();
400 // BfsWizard<Graph, RM, PM, PredNodeMap, DistMap>&
402 // if (!reached) makeRM();
403 // if (!pred_map) makePMMap();
404 // if (!pred_node_map) makePredNodeMap();
405 // if (!dist_map) makeDistMap();
413 /// Dfs searches for the nodes wich are not marked in
415 /// Reached have to be a read-write bool Node-map.
417 template <typename Graph, /*typename OutEdgeIt,*/
418 typename ReachedMap/*=typename Graph::NodeMap<bool>*/ >
421 typedef typename Graph::Node Node;
422 typedef typename Graph::Edge Edge;
423 typedef typename Graph::OutEdgeIt OutEdgeIt;
425 std::stack<OutEdgeIt> dfs_stack;
426 bool b_node_newly_reached;
430 bool own_reached_map;
432 /// In that constructor \c _reached have to be a reference
433 /// for a bool node-map. The algorithm will search in a dfs order for
434 /// the nodes which are \c false initially
435 DfsIterator(const Graph& _graph, ReachedMap& _reached) :
436 graph(&_graph), reached(_reached),
437 own_reached_map(false) { }
438 /// The same as above, but the map of reached nodes is
439 /// constructed dynamically
440 /// to everywhere false.
441 DfsIterator(const Graph& _graph) :
442 graph(&_graph), reached(*(new ReachedMap(*graph /*, false*/))),
443 own_reached_map(true) { }
444 ~DfsIterator() { if (own_reached_map) delete &reached; }
445 /// This method markes s reached and first out-edge is processed.
446 DfsIterator<Graph, /*OutEdgeIt,*/ ReachedMap>& pushAndSetReached(Node s) {
448 reached.set(s, true);
449 OutEdgeIt e(*graph, s);
450 //graph->first(e, s);
454 /// As \c DfsIterator<Graph, ReachedMap> works as an edge-iterator,
455 /// its \c operator++() iterates on the edges in a dfs order.
456 DfsIterator<Graph, /*OutEdgeIt,*/ ReachedMap>&
458 actual_edge=dfs_stack.top();
459 if (actual_edge!=INVALID/*.valid()*/) {
460 Node w=graph->target(actual_edge);
463 OutEdgeIt e(*graph, w);
464 //graph->first(e, w);
466 reached.set(w, true);
467 b_node_newly_reached=true;
469 actual_node=graph->source(actual_edge);
471 b_node_newly_reached=false;
474 //actual_node=G.aNode(dfs_stack.top());
479 /// Returns true iff the algorithm is finished.
480 bool finished() const { return dfs_stack.empty(); }
481 /// The conversion operator makes for converting the bfs-iterator
482 /// to an \c out-edge-iterator.
483 ///\bug Edge have to be in LEMON 0.2
484 operator Edge() const { return actual_edge; }
485 /// Returns if b-node has been reached just now.
486 bool isBNodeNewlyReached() const { return b_node_newly_reached; }
487 /// Returns if a-node is examined.
488 bool isANodeExamined() const { return actual_edge==INVALID; }
489 /// Returns a-node of the actual edge, so does if the edge is invalid.
490 Node source() const { return actual_node; /*FIXME*/}
491 /// Returns b-node of the actual edge.
492 /// \pre The actual edge have to be valid.
493 Node target() const { return graph->target(actual_edge); }
496 const ReachedMap& getReachedMap() const { return reached; }
499 const std::stack<OutEdgeIt>& getDfsStack() const { return dfs_stack; }
502 /// Dfs searches for the nodes wich are not marked in
504 /// Reached is a read-write bool node-map,
505 /// Pred is a write node-map, have to be.
507 template <typename Graph,
508 typename ReachedMap=typename Graph::template NodeMap<bool>,
510 =typename Graph::template NodeMap<typename Graph::Edge> >
511 class Dfs : public DfsIterator<Graph, ReachedMap> {
512 typedef DfsIterator<Graph, ReachedMap> Parent;
514 typedef typename Parent::Node Node;
517 /// The algorithm will search in a dfs order for
518 /// the nodes which are \c false initially.
519 /// The constructor makes no initial changes on the maps.
520 Dfs<Graph, ReachedMap, PredMap>(const Graph& _graph, ReachedMap& _reached, PredMap& _pred) : DfsIterator<Graph, ReachedMap>(_graph, _reached), pred(_pred) { }
521 /// \c s is marked to be reached and pushed in the bfs queue.
522 /// If the queue is empty, then the first out-edge is processed.
523 /// If \c s was not marked previously, then
524 /// in addition its pred is set to be \c INVALID.
525 /// if \c s was marked previuosly, then it is simply pushed.
526 Dfs<Graph, ReachedMap, PredMap>& push(Node s) {
527 if (this->reached[s]) {
528 Parent::pushAndSetReached(s);
530 Parent::pushAndSetReached(s);
531 pred.set(s, INVALID);
535 /// A bfs is processed from \c s.
536 Dfs<Graph, ReachedMap, PredMap>& run(Node s) {
538 while (!this->finished()) this->operator++();
541 /// Beside the dfs iteration, \c pred is saved in a
542 /// newly reached node.
543 Dfs<Graph, ReachedMap, PredMap>& operator++() {
544 Parent::operator++();
545 if (this->graph->valid(this->actual_edge) && this->b_node_newly_reached)
547 pred.set(this->target(), this->actual_edge);
553 const PredMap& getPredMap() const { return pred; }
559 #endif //LEMON_BFS_DFS_H