25 template <typename Graph, /*typename OutEdgeIt,*/ |
25 template <typename Graph, /*typename OutEdgeIt,*/ |
26 typename ReachedMap/*=typename Graph::NodeMap<bool>*/ > |
26 typename ReachedMap/*=typename Graph::NodeMap<bool>*/ > |
27 class BfsIterator { |
27 class BfsIterator { |
28 protected: |
28 protected: |
29 typedef typename Graph::Node Node; |
29 typedef typename Graph::Node Node; |
|
30 typedef typename Graph::Edge Edge; |
30 typedef typename Graph::OutEdgeIt OutEdgeIt; |
31 typedef typename Graph::OutEdgeIt OutEdgeIt; |
31 const Graph* graph; |
32 const Graph* graph; |
32 std::queue<Node> bfs_queue; |
33 std::queue<Node> bfs_queue; |
33 ReachedMap& reached; |
34 ReachedMap& reached; |
34 bool b_node_newly_reached; |
35 bool b_node_newly_reached; |
35 OutEdgeIt actual_edge; |
36 Edge actual_edge; |
36 bool own_reached_map; |
37 bool own_reached_map; |
37 public: |
38 public: |
38 /// In that constructor \c _reached have to be a reference |
39 /// In that constructor \c _reached have to be a reference |
39 /// for a bool bode-map. The algorithm will search for the |
40 /// for a bool bode-map. The algorithm will search for the |
40 /// initially \c false nodes |
41 /// initially \c false nodes |
53 ~BfsIterator() { if (own_reached_map) delete &reached; } |
54 ~BfsIterator() { if (own_reached_map) delete &reached; } |
54 /// This method markes \c s reached. |
55 /// This method markes \c s reached. |
55 /// If the queue is empty, then \c s is pushed in the bfs queue |
56 /// If the queue is empty, then \c s is pushed in the bfs queue |
56 /// and the first out-edge is processed. |
57 /// and the first out-edge is processed. |
57 /// If the queue is not empty, then \c s is simply pushed. |
58 /// If the queue is not empty, then \c s is simply pushed. |
58 void pushAndSetReached(Node s) { |
59 BfsIterator<Graph, /*OutEdgeIt,*/ ReachedMap>& pushAndSetReached(Node s) { |
59 reached.set(s, true); |
60 reached.set(s, true); |
60 if (bfs_queue.empty()) { |
61 if (bfs_queue.empty()) { |
61 bfs_queue.push(s); |
62 bfs_queue.push(s); |
62 graph->first(actual_edge, s); |
63 actual_edge=OutEdgeIt(*graph, s); |
|
64 //graph->first(actual_edge, s); |
63 if (actual_edge!=INVALID) { |
65 if (actual_edge!=INVALID) { |
64 Node w=graph->head(actual_edge); |
66 Node w=graph->head(actual_edge); |
65 if (!reached[w]) { |
67 if (!reached[w]) { |
66 bfs_queue.push(w); |
68 bfs_queue.push(w); |
67 reached.set(w, true); |
69 reached.set(w, true); |
71 } |
73 } |
72 } |
74 } |
73 } else { |
75 } else { |
74 bfs_queue.push(s); |
76 bfs_queue.push(s); |
75 } |
77 } |
|
78 return *this; |
76 } |
79 } |
77 /// As \c BfsIterator<Graph, ReachedMap> works as an edge-iterator, |
80 /// As \c BfsIterator<Graph, ReachedMap> works as an edge-iterator, |
78 /// its \c operator++() iterates on the edges in a bfs order. |
81 /// its \c operator++() iterates on the edges in a bfs order. |
79 BfsIterator<Graph, /*OutEdgeIt,*/ ReachedMap>& |
82 BfsIterator<Graph, /*OutEdgeIt,*/ ReachedMap>& |
80 operator++() { |
83 operator++() { |
81 if (actual_edge!=INVALID) { |
84 if (actual_edge!=INVALID) { |
82 ++actual_edge; |
85 actual_edge=++OutEdgeIt(*graph, actual_edge); |
|
86 //++actual_edge; |
83 if (actual_edge!=INVALID) { |
87 if (actual_edge!=INVALID) { |
84 Node w=graph->head(actual_edge); |
88 Node w=graph->head(actual_edge); |
85 if (!reached[w]) { |
89 if (!reached[w]) { |
86 bfs_queue.push(w); |
90 bfs_queue.push(w); |
87 reached.set(w, true); |
91 reached.set(w, true); |
91 } |
95 } |
92 } |
96 } |
93 } else { |
97 } else { |
94 bfs_queue.pop(); |
98 bfs_queue.pop(); |
95 if (!bfs_queue.empty()) { |
99 if (!bfs_queue.empty()) { |
96 graph->first(actual_edge, bfs_queue.front()); |
100 actual_edge=OutEdgeIt(*graph, bfs_queue.front()); |
|
101 //graph->first(actual_edge, bfs_queue.front()); |
97 if (actual_edge!=INVALID) { |
102 if (actual_edge!=INVALID) { |
98 Node w=graph->head(actual_edge); |
103 Node w=graph->head(actual_edge); |
99 if (!reached[w]) { |
104 if (!reached[w]) { |
100 bfs_queue.push(w); |
105 bfs_queue.push(w); |
101 reached.set(w, true); |
106 reached.set(w, true); |
111 /// Returns true iff the algorithm is finished. |
116 /// Returns true iff the algorithm is finished. |
112 bool finished() const { return bfs_queue.empty(); } |
117 bool finished() const { return bfs_queue.empty(); } |
113 /// The conversion operator makes for converting the bfs-iterator |
118 /// The conversion operator makes for converting the bfs-iterator |
114 /// to an \c out-edge-iterator. |
119 /// to an \c out-edge-iterator. |
115 ///\bug Edge have to be in HUGO 0.2 |
120 ///\bug Edge have to be in HUGO 0.2 |
116 operator OutEdgeIt() const { return actual_edge; } |
121 operator Edge() const { return actual_edge; } |
117 /// Returns if b-node has been reached just now. |
122 /// Returns if b-node has been reached just now. |
118 bool isBNodeNewlyReached() const { return b_node_newly_reached; } |
123 bool isBNodeNewlyReached() const { return b_node_newly_reached; } |
119 /// Returns if a-node is examined. |
124 /// Returns if a-node is examined. |
120 bool isANodeExamined() const { return actual_edge==INVALID; } |
125 bool isANodeExamined() const { return actual_edge==INVALID; } |
121 /// Returns a-node of the actual edge, so does if the edge is invalid. |
126 /// Returns a-node of the actual edge, so does if the edge is invalid. |
122 Node aNode() const { return bfs_queue.front(); } |
127 Node tail() const { return bfs_queue.front(); } |
123 /// \pre The actual edge have to be valid. |
128 /// \pre The actual edge have to be valid. |
124 Node bNode() const { return graph->bNode(actual_edge); } |
129 Node head() const { return graph->head(actual_edge); } |
125 /// Guess what? |
130 /// Guess what? |
126 /// \deprecated |
131 /// \deprecated |
127 const ReachedMap& getReachedMap() const { return reached; } |
132 const ReachedMap& getReachedMap() const { return reached; } |
128 /// Guess what? |
133 /// Guess what? |
129 /// \deprecated |
134 /// \deprecated |
157 /// \c s is marked to be reached and pushed in the bfs queue. |
162 /// \c s is marked to be reached and pushed in the bfs queue. |
158 /// If the queue is empty, then the first out-edge is processed. |
163 /// If the queue is empty, then the first out-edge is processed. |
159 /// If \c s was not marked previously, then |
164 /// If \c s was not marked previously, then |
160 /// in addition its pred is set to be \c INVALID, and dist to \c 0. |
165 /// in addition its pred is set to be \c INVALID, and dist to \c 0. |
161 /// if \c s was marked previuosly, then it is simply pushed. |
166 /// if \c s was marked previuosly, then it is simply pushed. |
162 void push(Node s) { |
167 Bfs<Graph, ReachedMap, PredMap, DistMap>& push(Node s) { |
163 if (this->reached[s]) { |
168 if (this->reached[s]) { |
164 Parent::pushAndSetReached(s); |
169 Parent::pushAndSetReached(s); |
165 } else { |
170 } else { |
166 Parent::pushAndSetReached(s); |
171 Parent::pushAndSetReached(s); |
167 pred.set(s, INVALID); |
172 pred.set(s, INVALID); |
168 dist.set(s, 0); |
173 dist.set(s, 0); |
169 } |
174 } |
|
175 return *this; |
170 } |
176 } |
171 /// A bfs is processed from \c s. |
177 /// A bfs is processed from \c s. |
172 void run(Node s) { |
178 Bfs<Graph, ReachedMap, PredMap, DistMap>& run(Node s) { |
173 push(s); |
179 push(s); |
174 while (!this->finished()) this->operator++(); |
180 while (!this->finished()) this->operator++(); |
|
181 return *this; |
175 } |
182 } |
176 /// Beside the bfs iteration, \c pred and \dist are saved in a |
183 /// Beside the bfs iteration, \c pred and \dist are saved in a |
177 /// newly reached node. |
184 /// newly reached node. |
178 Bfs<Graph, ReachedMap, PredMap, DistMap>& operator++() { |
185 Bfs<Graph, ReachedMap, PredMap, DistMap>& operator++() { |
179 Parent::operator++(); |
186 Parent::operator++(); |
180 if (this->graph->valid(this->actual_edge) && this->b_node_newly_reached) |
187 if (this->graph->valid(this->actual_edge) && this->b_node_newly_reached) |
181 { |
188 { |
182 pred.set(this->bNode(), this->actual_edge); |
189 pred.set(this->head(), this->actual_edge); |
183 dist.set(this->bNode(), dist[this->aNode()]); |
190 dist.set(this->head(), dist[this->tail()]); |
184 } |
191 } |
185 return *this; |
192 return *this; |
186 } |
193 } |
187 /// Guess what? |
194 /// Guess what? |
188 /// \deprecated |
195 /// \deprecated |
199 template <typename Graph, /*typename OutEdgeIt,*/ |
206 template <typename Graph, /*typename OutEdgeIt,*/ |
200 typename ReachedMap/*=typename Graph::NodeMap<bool>*/ > |
207 typename ReachedMap/*=typename Graph::NodeMap<bool>*/ > |
201 class DfsIterator { |
208 class DfsIterator { |
202 protected: |
209 protected: |
203 typedef typename Graph::Node Node; |
210 typedef typename Graph::Node Node; |
|
211 typedef typename Graph::Edge Edge; |
204 typedef typename Graph::OutEdgeIt OutEdgeIt; |
212 typedef typename Graph::OutEdgeIt OutEdgeIt; |
205 const Graph* graph; |
213 const Graph* graph; |
206 std::stack<OutEdgeIt> dfs_stack; |
214 std::stack<OutEdgeIt> dfs_stack; |
207 bool b_node_newly_reached; |
215 bool b_node_newly_reached; |
208 OutEdgeIt actual_edge; |
216 Edge actual_edge; |
209 Node actual_node; |
217 Node actual_node; |
210 ReachedMap& reached; |
218 ReachedMap& reached; |
211 bool own_reached_map; |
219 bool own_reached_map; |
212 public: |
220 public: |
213 /// In that constructor \c _reached have to be a reference |
221 /// In that constructor \c _reached have to be a reference |
222 DfsIterator(const Graph& _graph) : |
230 DfsIterator(const Graph& _graph) : |
223 graph(&_graph), reached(*(new ReachedMap(*graph /*, false*/))), |
231 graph(&_graph), reached(*(new ReachedMap(*graph /*, false*/))), |
224 own_reached_map(true) { } |
232 own_reached_map(true) { } |
225 ~DfsIterator() { if (own_reached_map) delete &reached; } |
233 ~DfsIterator() { if (own_reached_map) delete &reached; } |
226 /// This method markes s reached and first out-edge is processed. |
234 /// This method markes s reached and first out-edge is processed. |
227 void pushAndSetReached(Node s) { |
235 DfsIterator<Graph, /*OutEdgeIt,*/ ReachedMap>& pushAndSetReached(Node s) { |
228 actual_node=s; |
236 actual_node=s; |
229 reached.set(s, true); |
237 reached.set(s, true); |
230 OutEdgeIt e; |
238 OutEdgeIt e(*graph, s); |
231 graph->first(e, s); |
239 //graph->first(e, s); |
232 dfs_stack.push(e); |
240 dfs_stack.push(e); |
|
241 return *this; |
233 } |
242 } |
234 /// As \c DfsIterator<Graph, ReachedMap> works as an edge-iterator, |
243 /// As \c DfsIterator<Graph, ReachedMap> works as an edge-iterator, |
235 /// its \c operator++() iterates on the edges in a dfs order. |
244 /// its \c operator++() iterates on the edges in a dfs order. |
236 DfsIterator<Graph, /*OutEdgeIt,*/ ReachedMap>& |
245 DfsIterator<Graph, /*OutEdgeIt,*/ ReachedMap>& |
237 operator++() { |
246 operator++() { |
238 actual_edge=dfs_stack.top(); |
247 actual_edge=dfs_stack.top(); |
239 //actual_node=G.aNode(actual_edge); |
|
240 if (actual_edge!=INVALID/*.valid()*/) { |
248 if (actual_edge!=INVALID/*.valid()*/) { |
241 Node w=graph->head(actual_edge); |
249 Node w=graph->head(actual_edge); |
242 actual_node=w; |
250 actual_node=w; |
243 if (!reached[w]) { |
251 if (!reached[w]) { |
244 OutEdgeIt e; |
252 OutEdgeIt e(*graph, w); |
245 graph->first(e, w); |
253 //graph->first(e, w); |
246 dfs_stack.push(e); |
254 dfs_stack.push(e); |
247 reached.set(w, true); |
255 reached.set(w, true); |
248 b_node_newly_reached=true; |
256 b_node_newly_reached=true; |
249 } else { |
257 } else { |
250 actual_node=graph->tail(actual_edge); |
258 actual_node=graph->tail(actual_edge); |
260 /// Returns true iff the algorithm is finished. |
268 /// Returns true iff the algorithm is finished. |
261 bool finished() const { return dfs_stack.empty(); } |
269 bool finished() const { return dfs_stack.empty(); } |
262 /// The conversion operator makes for converting the bfs-iterator |
270 /// The conversion operator makes for converting the bfs-iterator |
263 /// to an \c out-edge-iterator. |
271 /// to an \c out-edge-iterator. |
264 ///\bug Edge have to be in HUGO 0.2 |
272 ///\bug Edge have to be in HUGO 0.2 |
265 operator OutEdgeIt() const { return actual_edge; } |
273 operator Edge() const { return actual_edge; } |
266 /// Returns if b-node has been reached just now. |
274 /// Returns if b-node has been reached just now. |
267 bool isBNodeNewlyReached() const { return b_node_newly_reached; } |
275 bool isBNodeNewlyReached() const { return b_node_newly_reached; } |
268 /// Returns if a-node is examined. |
276 /// Returns if a-node is examined. |
269 bool isANodeExamined() const { return actual_edge==INVALID; } |
277 bool isANodeExamined() const { return actual_edge==INVALID; } |
270 /// Returns a-node of the actual edge, so does if the edge is invalid. |
278 /// Returns a-node of the actual edge, so does if the edge is invalid. |
271 Node aNode() const { return actual_node; /*FIXME*/} |
279 Node tail() const { return actual_node; /*FIXME*/} |
272 /// Returns b-node of the actual edge. |
280 /// Returns b-node of the actual edge. |
273 /// \pre The actual edge have to be valid. |
281 /// \pre The actual edge have to be valid. |
274 Node bNode() const { return graph->bNode(actual_edge); } |
282 Node head() const { return graph->head(actual_edge); } |
275 /// Guess what? |
283 /// Guess what? |
276 /// \deprecated |
284 /// \deprecated |
277 const ReachedMap& getReachedMap() const { return reached; } |
285 const ReachedMap& getReachedMap() const { return reached; } |
278 /// Guess what? |
286 /// Guess what? |
279 /// \deprecated |
287 /// \deprecated |
302 /// \c s is marked to be reached and pushed in the bfs queue. |
310 /// \c s is marked to be reached and pushed in the bfs queue. |
303 /// If the queue is empty, then the first out-edge is processed. |
311 /// If the queue is empty, then the first out-edge is processed. |
304 /// If \c s was not marked previously, then |
312 /// If \c s was not marked previously, then |
305 /// in addition its pred is set to be \c INVALID. |
313 /// in addition its pred is set to be \c INVALID. |
306 /// if \c s was marked previuosly, then it is simply pushed. |
314 /// if \c s was marked previuosly, then it is simply pushed. |
307 void push(Node s) { |
315 Dfs<Graph, ReachedMap, PredMap>& push(Node s) { |
308 if (this->reached[s]) { |
316 if (this->reached[s]) { |
309 Parent::pushAndSetReached(s); |
317 Parent::pushAndSetReached(s); |
310 } else { |
318 } else { |
311 Parent::pushAndSetReached(s); |
319 Parent::pushAndSetReached(s); |
312 pred.set(s, INVALID); |
320 pred.set(s, INVALID); |
313 } |
321 } |
|
322 return *this; |
314 } |
323 } |
315 /// A bfs is processed from \c s. |
324 /// A bfs is processed from \c s. |
316 void run(Node s) { |
325 Dfs<Graph, ReachedMap, PredMap>& run(Node s) { |
317 push(s); |
326 push(s); |
318 while (!this->finished()) this->operator++(); |
327 while (!this->finished()) this->operator++(); |
|
328 return *this; |
319 } |
329 } |
320 /// Beside the dfs iteration, \c pred is saved in a |
330 /// Beside the dfs iteration, \c pred is saved in a |
321 /// newly reached node. |
331 /// newly reached node. |
322 Dfs<Graph, ReachedMap, PredMap>& operator++() { |
332 Dfs<Graph, ReachedMap, PredMap>& operator++() { |
323 Parent::operator++(); |
333 Parent::operator++(); |
324 if (this->graph->valid(this->actual_edge) && this->b_node_newly_reached) |
334 if (this->graph->valid(this->actual_edge) && this->b_node_newly_reached) |
325 { |
335 { |
326 pred.set(this->bNode(), this->actual_edge); |
336 pred.set(this->head(), this->actual_edge); |
327 } |
337 } |
328 return *this; |
338 return *this; |
329 } |
339 } |
330 /// Guess what? |
340 /// Guess what? |
331 /// \deprecated |
341 /// \deprecated |