Completions.
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>
21 /// Bfs searches for the nodes wich are not marked in
23 /// Reached have to be a read-write bool node-map.
25 template <typename Graph, /*typename OutEdgeIt,*/
26 typename ReachedMap/*=typename Graph::NodeMap<bool>*/ >
29 typedef typename Graph::Node Node;
30 typedef typename Graph::Edge Edge;
31 typedef typename Graph::OutEdgeIt OutEdgeIt;
33 std::queue<Node> bfs_queue;
35 bool b_node_newly_reached;
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
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.
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) {
61 if (bfs_queue.empty()) {
63 actual_edge=OutEdgeIt(*graph, s);
64 //graph->first(actual_edge, s);
65 if (actual_edge!=INVALID) {
66 Node w=graph->target(actual_edge);
70 b_node_newly_reached=true;
72 b_node_newly_reached=false;
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>&
84 if (actual_edge!=INVALID) {
85 actual_edge=++OutEdgeIt(*graph, actual_edge);
87 if (actual_edge!=INVALID) {
88 Node w=graph->target(actual_edge);
92 b_node_newly_reached=true;
94 b_node_newly_reached=false;
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);
106 reached.set(w, true);
107 b_node_newly_reached=true;
109 b_node_newly_reached=false;
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); }
132 const ReachedMap& getReachedMap() const { return reached; }
135 const std::queue<Node>& getBfsQueue() const { return bfs_queue; }
138 /// Bfs searches for the nodes wich are not marked in
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.
144 template <typename Graph,
145 typename ReachedMap=typename Graph::template NodeMap<bool>,
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;
152 typedef typename Parent::Node Node;
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);
171 Parent::pushAndSetReached(s);
172 pred.set(s, INVALID);
177 /// A bfs is processed from \c s.
178 Bfs<Graph, ReachedMap, PredMap, DistMap>& run(Node s) {
180 while (!this->finished()) this->operator++();
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)
189 pred.set(this->target(), this->actual_edge);
190 dist.set(this->target(), dist[this->source()]);
196 const PredMap& getPredMap() const { return pred; }
199 const DistMap& getDistMap() const { return dist; }
202 /// Dfs searches for the nodes wich are not marked in
204 /// Reached have to be a read-write bool Node-map.
206 template <typename Graph, /*typename OutEdgeIt,*/
207 typename ReachedMap/*=typename Graph::NodeMap<bool>*/ >
210 typedef typename Graph::Node Node;
211 typedef typename Graph::Edge Edge;
212 typedef typename Graph::OutEdgeIt OutEdgeIt;
214 std::stack<OutEdgeIt> dfs_stack;
215 bool b_node_newly_reached;
219 bool own_reached_map;
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) {
237 reached.set(s, true);
238 OutEdgeIt e(*graph, s);
239 //graph->first(e, s);
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>&
247 actual_edge=dfs_stack.top();
248 if (actual_edge!=INVALID/*.valid()*/) {
249 Node w=graph->target(actual_edge);
252 OutEdgeIt e(*graph, w);
253 //graph->first(e, w);
255 reached.set(w, true);
256 b_node_newly_reached=true;
258 actual_node=graph->source(actual_edge);
260 b_node_newly_reached=false;
263 //actual_node=G.aNode(dfs_stack.top());
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); }
285 const ReachedMap& getReachedMap() const { return reached; }
288 const std::stack<OutEdgeIt>& getDfsStack() const { return dfs_stack; }
291 /// Dfs searches for the nodes wich are not marked in
293 /// Reached is a read-write bool node-map,
294 /// Pred is a write node-map, have to be.
296 template <typename Graph,
297 typename ReachedMap=typename Graph::template NodeMap<bool>,
299 =typename Graph::template NodeMap<typename Graph::Edge> >
300 class Dfs : public DfsIterator<Graph, ReachedMap> {
301 typedef DfsIterator<Graph, ReachedMap> Parent;
303 typedef typename Parent::Node Node;
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);
319 Parent::pushAndSetReached(s);
320 pred.set(s, INVALID);
324 /// A bfs is processed from \c s.
325 Dfs<Graph, ReachedMap, PredMap>& run(Node s) {
327 while (!this->finished()) this->operator++();
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)
336 pred.set(this->target(), this->actual_edge);
342 const PredMap& getPredMap() const { return pred; }
348 #endif //LEMON_BFS_DFS_H