Sorry, the other half of the move comes here.
5 // ///\ingroup gwrappers
7 ///\brief Bfs and dfs iterators.
9 ///This file contains bfs and dfs iterator classes.
11 // ///\author Marton Makai
17 #include <hugo/invalid.h>
21 /// Bfs searches for the nodes wich are not marked in
23 /// Reached have to work as read-write bool Node-map.
24 template <typename Graph, /*typename OutEdgeIt,*/
25 typename ReachedMap/*=typename Graph::NodeMap<bool>*/ >
28 typedef typename Graph::Node Node;
29 typedef typename Graph::OutEdgeIt OutEdgeIt;
31 std::queue<Node> bfs_queue;
33 bool b_node_newly_reached;
34 OutEdgeIt actual_edge;
37 /// In that constructor \c _reached have to be a reference
38 /// for a bool Node-map. The algorithm will search in a bfs order for
39 /// the nodes which are \c false initially
40 BfsIterator(const Graph& _graph, ReachedMap& _reached) :
41 graph(&_graph), reached(_reached),
42 own_reached_map(false) { }
43 /// The same as above, but the map storing the reached nodes
44 /// is constructed dynamically to everywhere false.
45 BfsIterator(const Graph& _graph) :
46 graph(&_graph), reached(*(new ReachedMap(*graph /*, false*/))),
47 own_reached_map(true) { }
48 /// The map storing the reached nodes have to be destroyed if
49 /// it was constructed dynamically
50 ~BfsIterator() { if (own_reached_map) delete &reached; }
51 /// This method markes \c s reached.
52 /// If the queue is empty, then \c s is pushed in the bfs queue
53 /// and the first out-edge is processed.
54 /// If the queue is not empty, then \c s is simply pushed.
55 void pushAndSetReached(Node s) {
57 if (bfs_queue.empty()) {
59 graph->first(actual_edge, s);
60 if (graph->valid(actual_edge)) {
61 Node w=graph->bNode(actual_edge);
65 b_node_newly_reached=true;
67 b_node_newly_reached=false;
74 /// As \c BfsIterator<Graph, ReachedMap> works as an edge-iterator,
75 /// its \c operator++() iterates on the edges in a bfs order.
76 BfsIterator<Graph, /*OutEdgeIt,*/ ReachedMap>&
78 if (graph->valid(actual_edge)) {
79 graph->next(actual_edge);
80 if (graph->valid(actual_edge)) {
81 Node w=graph->bNode(actual_edge);
85 b_node_newly_reached=true;
87 b_node_newly_reached=false;
92 if (!bfs_queue.empty()) {
93 graph->first(actual_edge, bfs_queue.front());
94 if (graph->valid(actual_edge)) {
95 Node w=graph->bNode(actual_edge);
99 b_node_newly_reached=true;
101 b_node_newly_reached=false;
109 bool finished() const { return bfs_queue.empty(); }
110 /// The conversion operator makes for converting the bfs-iterator
111 /// to an \c out-edge-iterator.
112 ///\bug Edge have to be in HUGO 0.2
113 operator OutEdgeIt() const { return actual_edge; }
115 bool isBNodeNewlyReached() const { return b_node_newly_reached; }
117 bool isANodeExamined() const { return !(graph->valid(actual_edge)); }
119 Node aNode() const { return bfs_queue.front(); }
121 Node bNode() const { return graph->bNode(actual_edge); }
123 const ReachedMap& getReachedMap() const { return reached; }
125 const std::queue<Node>& getBfsQueue() const { return bfs_queue; }
128 /// Bfs searches for the nodes wich are not marked in
130 /// Reached have to work as a read-write bool Node-map,
131 /// Pred is a write Edge Node-map and
132 /// Dist is a read-write int Node-map, have to be.
133 ///\todo In fact onsly simple operations requirement are needed for
135 template <typename Graph,
136 typename ReachedMap=typename Graph::template NodeMap<bool>,
138 =typename Graph::template NodeMap<typename Graph::Edge>,
139 typename DistMap=typename Graph::template NodeMap<int> >
140 class Bfs : public BfsIterator<Graph, ReachedMap> {
141 typedef BfsIterator<Graph, ReachedMap> Parent;
143 typedef typename Parent::Node Node;
147 /// The algorithm will search in a bfs order for
148 /// the nodes which are \c false initially.
149 /// The constructor makes no initial changes on the maps.
150 Bfs<Graph, ReachedMap, PredMap, DistMap>(const Graph& _graph, ReachedMap& _reached, PredMap& _pred, DistMap& _dist) : BfsIterator<Graph, ReachedMap>(_graph, _reached), pred(&_pred), dist(&_dist) { }
151 /// \c s is marked to be reached and pushed in the bfs queue.
152 /// If the queue is empty, then the first out-edge is processed.
153 /// If \c s was not marked previously, then
154 /// in addition its pred is set to be \c INVALID, and dist to \c 0.
155 /// if \c s was marked previuosly, then it is simply pushed.
157 if (this->reached[s]) {
158 Parent::pushAndSetReached(s);
160 Parent::pushAndSetReached(s);
161 pred.set(s, INVALID);
165 /// A bfs is processed from \c s.
168 while (!this->finished()) this->operator++();
170 /// Beside the bfs iteration, \c pred and \dist are saved in a
171 /// newly reached node.
172 Bfs<Graph, ReachedMap, PredMap, DistMap>& operator++() {
173 Parent::operator++();
174 if (this->graph->valid(this->actual_edge) && this->b_node_newly_reached)
176 pred.set(this->bNode(), this->actual_edge);
177 dist.set(this->bNode(), dist[this->aNode()]);
182 const PredMap& getPredMap() const { return pred; }
184 const DistMap& getDistMap() const { return dist; }
187 /// Dfs searches for the nodes wich are not marked in
189 /// Reached have to be a read-write bool Node-map.
190 template <typename Graph, /*typename OutEdgeIt,*/
191 typename ReachedMap/*=typename Graph::NodeMap<bool>*/ >
194 typedef typename Graph::Node Node;
195 typedef typename Graph::OutEdgeIt OutEdgeIt;
197 std::stack<OutEdgeIt> dfs_stack;
198 bool b_node_newly_reached;
199 OutEdgeIt actual_edge;
202 bool own_reached_map;
204 /// In that constructor \c _reached have to be a reference
205 /// for a bool Node-map. The algorithm will search in a dfs order for
206 /// the nodes which are \c false initially
207 DfsIterator(const Graph& _graph, ReachedMap& _reached) :
208 graph(&_graph), reached(_reached),
209 own_reached_map(false) { }
210 /// The same as above, but the map of reached nodes is
211 /// constructed dynamically
212 /// to everywhere false.
213 DfsIterator(const Graph& _graph) :
214 graph(&_graph), reached(*(new ReachedMap(*graph /*, false*/))),
215 own_reached_map(true) { }
216 ~DfsIterator() { if (own_reached_map) delete &reached; }
217 /// This method markes s reached and first out-edge is processed.
218 void pushAndSetReached(Node s) {
220 reached.set(s, true);
225 /// As \c DfsIterator<Graph, ReachedMap> works as an edge-iterator,
226 /// its \c operator++() iterates on the edges in a dfs order.
227 DfsIterator<Graph, /*OutEdgeIt,*/ ReachedMap>&
229 actual_edge=dfs_stack.top();
230 //actual_node=G.aNode(actual_edge);
231 if (graph->valid(actual_edge)/*.valid()*/) {
232 Node w=graph->bNode(actual_edge);
238 reached.set(w, true);
239 b_node_newly_reached=true;
241 actual_node=graph->aNode(actual_edge);
242 graph->next(dfs_stack.top());
243 b_node_newly_reached=false;
246 //actual_node=G.aNode(dfs_stack.top());
252 bool finished() const { return dfs_stack.empty(); }
254 operator OutEdgeIt() const { return actual_edge; }
256 bool isBNodeNewlyReached() const { return b_node_newly_reached; }
258 bool isANodeExamined() const { return !(graph->valid(actual_edge)); }
260 Node aNode() const { return actual_node; /*FIXME*/}
262 Node bNode() const { return graph->bNode(actual_edge); }
264 const ReachedMap& getReachedMap() const { return reached; }
266 const std::stack<OutEdgeIt>& getDfsStack() const { return dfs_stack; }
269 /// Dfs searches for the nodes wich are not marked in
271 /// Reached is a read-write bool Node-map,
272 /// Pred is a write Node-map, have to be.
273 template <typename Graph,
274 typename ReachedMap=typename Graph::template NodeMap<bool>,
276 =typename Graph::template NodeMap<typename Graph::Edge> >
277 class Dfs : public DfsIterator<Graph, ReachedMap> {
278 typedef DfsIterator<Graph, ReachedMap> Parent;
280 typedef typename Parent::Node Node;
283 /// The algorithm will search in a dfs order for
284 /// the nodes which are \c false initially.
285 /// The constructor makes no initial changes on the maps.
286 Dfs<Graph, ReachedMap, PredMap>(const Graph& _graph, ReachedMap& _reached, PredMap& _pred) : DfsIterator<Graph, ReachedMap>(_graph, _reached), pred(&_pred) { }
287 /// \c s is marked to be reached and pushed in the bfs queue.
288 /// If the queue is empty, then the first out-edge is processed.
289 /// If \c s was not marked previously, then
290 /// in addition its pred is set to be \c INVALID.
291 /// if \c s was marked previuosly, then it is simply pushed.
293 if (this->reached[s]) {
294 Parent::pushAndSetReached(s);
296 Parent::pushAndSetReached(s);
297 pred.set(s, INVALID);
300 /// A bfs is processed from \c s.
303 while (!this->finished()) this->operator++();
305 /// Beside the dfs iteration, \c pred is saved in a
306 /// newly reached node.
307 Dfs<Graph, ReachedMap, PredMap>& operator++() {
308 Parent::operator++();
309 if (this->graph->valid(this->actual_edge) && this->b_node_newly_reached)
311 pred.set(this->bNode(), this->actual_edge);
316 const PredMap& getPredMap() const { return pred; }
322 #endif //HUGO_BFS_DFS_H