61 if (bfs_queue.empty()) { |
61 if (bfs_queue.empty()) { |
62 bfs_queue.push(s); |
62 bfs_queue.push(s); |
63 actual_edge=OutEdgeIt(*graph, s); |
63 actual_edge=OutEdgeIt(*graph, s); |
64 //graph->first(actual_edge, s); |
64 //graph->first(actual_edge, s); |
65 if (actual_edge!=INVALID) { |
65 if (actual_edge!=INVALID) { |
66 Node w=graph->head(actual_edge); |
66 Node w=graph->target(actual_edge); |
67 if (!reached[w]) { |
67 if (!reached[w]) { |
68 bfs_queue.push(w); |
68 bfs_queue.push(w); |
69 reached.set(w, true); |
69 reached.set(w, true); |
70 b_node_newly_reached=true; |
70 b_node_newly_reached=true; |
71 } else { |
71 } else { |
83 operator++() { |
83 operator++() { |
84 if (actual_edge!=INVALID) { |
84 if (actual_edge!=INVALID) { |
85 actual_edge=++OutEdgeIt(*graph, actual_edge); |
85 actual_edge=++OutEdgeIt(*graph, actual_edge); |
86 //++actual_edge; |
86 //++actual_edge; |
87 if (actual_edge!=INVALID) { |
87 if (actual_edge!=INVALID) { |
88 Node w=graph->head(actual_edge); |
88 Node w=graph->target(actual_edge); |
89 if (!reached[w]) { |
89 if (!reached[w]) { |
90 bfs_queue.push(w); |
90 bfs_queue.push(w); |
91 reached.set(w, true); |
91 reached.set(w, true); |
92 b_node_newly_reached=true; |
92 b_node_newly_reached=true; |
93 } else { |
93 } else { |
98 bfs_queue.pop(); |
98 bfs_queue.pop(); |
99 if (!bfs_queue.empty()) { |
99 if (!bfs_queue.empty()) { |
100 actual_edge=OutEdgeIt(*graph, bfs_queue.front()); |
100 actual_edge=OutEdgeIt(*graph, bfs_queue.front()); |
101 //graph->first(actual_edge, bfs_queue.front()); |
101 //graph->first(actual_edge, bfs_queue.front()); |
102 if (actual_edge!=INVALID) { |
102 if (actual_edge!=INVALID) { |
103 Node w=graph->head(actual_edge); |
103 Node w=graph->target(actual_edge); |
104 if (!reached[w]) { |
104 if (!reached[w]) { |
105 bfs_queue.push(w); |
105 bfs_queue.push(w); |
106 reached.set(w, true); |
106 reached.set(w, true); |
107 b_node_newly_reached=true; |
107 b_node_newly_reached=true; |
108 } else { |
108 } else { |
122 /// Returns if b-node has been reached just now. |
122 /// Returns if b-node has been reached just now. |
123 bool isBNodeNewlyReached() const { return b_node_newly_reached; } |
123 bool isBNodeNewlyReached() const { return b_node_newly_reached; } |
124 /// Returns if a-node is examined. |
124 /// Returns if a-node is examined. |
125 bool isANodeExamined() const { return actual_edge==INVALID; } |
125 bool isANodeExamined() const { return actual_edge==INVALID; } |
126 /// 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. |
127 Node tail() const { return bfs_queue.front(); } |
127 Node source() const { return bfs_queue.front(); } |
128 /// \pre The actual edge have to be valid. |
128 /// \pre The actual edge have to be valid. |
129 Node head() const { return graph->head(actual_edge); } |
129 Node target() const { return graph->target(actual_edge); } |
130 /// Guess what? |
130 /// Guess what? |
131 /// \deprecated |
131 /// \deprecated |
132 const ReachedMap& getReachedMap() const { return reached; } |
132 const ReachedMap& getReachedMap() const { return reached; } |
133 /// Guess what? |
133 /// Guess what? |
134 /// \deprecated |
134 /// \deprecated |
184 /// newly reached node. |
184 /// newly reached node. |
185 Bfs<Graph, ReachedMap, PredMap, DistMap>& operator++() { |
185 Bfs<Graph, ReachedMap, PredMap, DistMap>& operator++() { |
186 Parent::operator++(); |
186 Parent::operator++(); |
187 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) |
188 { |
188 { |
189 pred.set(this->head(), this->actual_edge); |
189 pred.set(this->target(), this->actual_edge); |
190 dist.set(this->head(), dist[this->tail()]); |
190 dist.set(this->target(), dist[this->source()]); |
191 } |
191 } |
192 return *this; |
192 return *this; |
193 } |
193 } |
194 /// Guess what? |
194 /// Guess what? |
195 /// \deprecated |
195 /// \deprecated |
244 /// its \c operator++() iterates on the edges in a dfs order. |
244 /// its \c operator++() iterates on the edges in a dfs order. |
245 DfsIterator<Graph, /*OutEdgeIt,*/ ReachedMap>& |
245 DfsIterator<Graph, /*OutEdgeIt,*/ ReachedMap>& |
246 operator++() { |
246 operator++() { |
247 actual_edge=dfs_stack.top(); |
247 actual_edge=dfs_stack.top(); |
248 if (actual_edge!=INVALID/*.valid()*/) { |
248 if (actual_edge!=INVALID/*.valid()*/) { |
249 Node w=graph->head(actual_edge); |
249 Node w=graph->target(actual_edge); |
250 actual_node=w; |
250 actual_node=w; |
251 if (!reached[w]) { |
251 if (!reached[w]) { |
252 OutEdgeIt e(*graph, w); |
252 OutEdgeIt e(*graph, w); |
253 //graph->first(e, w); |
253 //graph->first(e, w); |
254 dfs_stack.push(e); |
254 dfs_stack.push(e); |
255 reached.set(w, true); |
255 reached.set(w, true); |
256 b_node_newly_reached=true; |
256 b_node_newly_reached=true; |
257 } else { |
257 } else { |
258 actual_node=graph->tail(actual_edge); |
258 actual_node=graph->source(actual_edge); |
259 ++dfs_stack.top(); |
259 ++dfs_stack.top(); |
260 b_node_newly_reached=false; |
260 b_node_newly_reached=false; |
261 } |
261 } |
262 } else { |
262 } else { |
263 //actual_node=G.aNode(dfs_stack.top()); |
263 //actual_node=G.aNode(dfs_stack.top()); |
274 /// Returns if b-node has been reached just now. |
274 /// Returns if b-node has been reached just now. |
275 bool isBNodeNewlyReached() const { return b_node_newly_reached; } |
275 bool isBNodeNewlyReached() const { return b_node_newly_reached; } |
276 /// Returns if a-node is examined. |
276 /// Returns if a-node is examined. |
277 bool isANodeExamined() const { return actual_edge==INVALID; } |
277 bool isANodeExamined() const { return actual_edge==INVALID; } |
278 /// 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. |
279 Node tail() const { return actual_node; /*FIXME*/} |
279 Node source() const { return actual_node; /*FIXME*/} |
280 /// Returns b-node of the actual edge. |
280 /// Returns b-node of the actual edge. |
281 /// \pre The actual edge have to be valid. |
281 /// \pre The actual edge have to be valid. |
282 Node head() const { return graph->head(actual_edge); } |
282 Node target() const { return graph->target(actual_edge); } |
283 /// Guess what? |
283 /// Guess what? |
284 /// \deprecated |
284 /// \deprecated |
285 const ReachedMap& getReachedMap() const { return reached; } |
285 const ReachedMap& getReachedMap() const { return reached; } |
286 /// Guess what? |
286 /// Guess what? |
287 /// \deprecated |
287 /// \deprecated |
331 /// newly reached node. |
331 /// newly reached node. |
332 Dfs<Graph, ReachedMap, PredMap>& operator++() { |
332 Dfs<Graph, ReachedMap, PredMap>& operator++() { |
333 Parent::operator++(); |
333 Parent::operator++(); |
334 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) |
335 { |
335 { |
336 pred.set(this->head(), this->actual_edge); |
336 pred.set(this->target(), this->actual_edge); |
337 } |
337 } |
338 return *this; |
338 return *this; |
339 } |
339 } |
340 /// Guess what? |
340 /// Guess what? |
341 /// \deprecated |
341 /// \deprecated |