69 if (bfs_queue.empty()) { |
69 if (bfs_queue.empty()) { |
70 bfs_queue.push(s); |
70 bfs_queue.push(s); |
71 actual_edge=OutEdgeIt(*graph, s); |
71 actual_edge=OutEdgeIt(*graph, s); |
72 //graph->first(actual_edge, s); |
72 //graph->first(actual_edge, s); |
73 if (actual_edge!=INVALID) { |
73 if (actual_edge!=INVALID) { |
74 Node w=graph->head(actual_edge); |
74 Node w=graph->target(actual_edge); |
75 if (!(*reached_map)[w]) { |
75 if (!(*reached_map)[w]) { |
76 bfs_queue.push(w); |
76 bfs_queue.push(w); |
77 reached_map->set(w, true); |
77 reached_map->set(w, true); |
78 b_node_newly_reached=true; |
78 b_node_newly_reached=true; |
79 } else { |
79 } else { |
91 operator++() { |
91 operator++() { |
92 if (actual_edge!=INVALID) { |
92 if (actual_edge!=INVALID) { |
93 actual_edge=++OutEdgeIt(*graph, actual_edge); |
93 actual_edge=++OutEdgeIt(*graph, actual_edge); |
94 //++actual_edge; |
94 //++actual_edge; |
95 if (actual_edge!=INVALID) { |
95 if (actual_edge!=INVALID) { |
96 Node w=graph->head(actual_edge); |
96 Node w=graph->target(actual_edge); |
97 if (!(*reached_map)[w]) { |
97 if (!(*reached_map)[w]) { |
98 bfs_queue.push(w); |
98 bfs_queue.push(w); |
99 reached_map->set(w, true); |
99 reached_map->set(w, true); |
100 b_node_newly_reached=true; |
100 b_node_newly_reached=true; |
101 } else { |
101 } else { |
106 bfs_queue.pop(); |
106 bfs_queue.pop(); |
107 if (!bfs_queue.empty()) { |
107 if (!bfs_queue.empty()) { |
108 actual_edge=OutEdgeIt(*graph, bfs_queue.front()); |
108 actual_edge=OutEdgeIt(*graph, bfs_queue.front()); |
109 //graph->first(actual_edge, bfs_queue.front()); |
109 //graph->first(actual_edge, bfs_queue.front()); |
110 if (actual_edge!=INVALID) { |
110 if (actual_edge!=INVALID) { |
111 Node w=graph->head(actual_edge); |
111 Node w=graph->target(actual_edge); |
112 if (!(*reached_map)[w]) { |
112 if (!(*reached_map)[w]) { |
113 bfs_queue.push(w); |
113 bfs_queue.push(w); |
114 reached_map->set(w, true); |
114 reached_map->set(w, true); |
115 b_node_newly_reached=true; |
115 b_node_newly_reached=true; |
116 } else { |
116 } else { |
130 /// Returns if b-node has been reached just now. |
130 /// Returns if b-node has been reached just now. |
131 bool isBNodeNewlyReached() const { return b_node_newly_reached; } |
131 bool isBNodeNewlyReached() const { return b_node_newly_reached; } |
132 /// Returns if a-node is examined. |
132 /// Returns if a-node is examined. |
133 bool isANodeExamined() const { return actual_edge==INVALID; } |
133 bool isANodeExamined() const { return actual_edge==INVALID; } |
134 /// Returns a-node of the actual edge, so does if the edge is invalid. |
134 /// Returns a-node of the actual edge, so does if the edge is invalid. |
135 Node tail() const { return bfs_queue.front(); } |
135 Node source() const { return bfs_queue.front(); } |
136 /// \pre The actual edge have to be valid. |
136 /// \pre The actual edge have to be valid. |
137 Node head() const { return graph->head(actual_edge); } |
137 Node target() const { return graph->target(actual_edge); } |
138 /// Guess what? |
138 /// Guess what? |
139 /// \deprecated |
139 /// \deprecated |
140 const ReachedMap& reachedMap() const { return *reached_map; } |
140 const ReachedMap& reachedMap() const { return *reached_map; } |
141 /// Guess what? |
141 /// Guess what? |
142 /// \deprecated |
142 /// \deprecated |
229 /// newly reached node. |
229 /// newly reached node. |
230 Bfs<Graph, RM, PM, PNM, DM>& operator++() { |
230 Bfs<Graph, RM, PM, PNM, DM>& operator++() { |
231 Parent::operator++(); |
231 Parent::operator++(); |
232 if ((this->actual_edge)!=INVALID && this->b_node_newly_reached) |
232 if ((this->actual_edge)!=INVALID && this->b_node_newly_reached) |
233 { |
233 { |
234 pred_map->set(this->head(), this->actual_edge); |
234 pred_map->set(this->target(), this->actual_edge); |
235 pred_node_map->set(this->head(), this->tail()); |
235 pred_node_map->set(this->target(), this->source()); |
236 dist_map->set(this->head(), (*dist_map)[this->tail()]); |
236 dist_map->set(this->target(), (*dist_map)[this->source()]); |
237 } |
237 } |
238 return *this; |
238 return *this; |
239 } |
239 } |
240 /// Guess what? |
240 /// Guess what? |
241 /// \deprecated |
241 /// \deprecated |
455 /// its \c operator++() iterates on the edges in a dfs order. |
455 /// its \c operator++() iterates on the edges in a dfs order. |
456 DfsIterator<Graph, /*OutEdgeIt,*/ ReachedMap>& |
456 DfsIterator<Graph, /*OutEdgeIt,*/ ReachedMap>& |
457 operator++() { |
457 operator++() { |
458 actual_edge=dfs_stack.top(); |
458 actual_edge=dfs_stack.top(); |
459 if (actual_edge!=INVALID/*.valid()*/) { |
459 if (actual_edge!=INVALID/*.valid()*/) { |
460 Node w=graph->head(actual_edge); |
460 Node w=graph->target(actual_edge); |
461 actual_node=w; |
461 actual_node=w; |
462 if (!reached[w]) { |
462 if (!reached[w]) { |
463 OutEdgeIt e(*graph, w); |
463 OutEdgeIt e(*graph, w); |
464 //graph->first(e, w); |
464 //graph->first(e, w); |
465 dfs_stack.push(e); |
465 dfs_stack.push(e); |
466 reached.set(w, true); |
466 reached.set(w, true); |
467 b_node_newly_reached=true; |
467 b_node_newly_reached=true; |
468 } else { |
468 } else { |
469 actual_node=graph->tail(actual_edge); |
469 actual_node=graph->source(actual_edge); |
470 ++dfs_stack.top(); |
470 ++dfs_stack.top(); |
471 b_node_newly_reached=false; |
471 b_node_newly_reached=false; |
472 } |
472 } |
473 } else { |
473 } else { |
474 //actual_node=G.aNode(dfs_stack.top()); |
474 //actual_node=G.aNode(dfs_stack.top()); |
485 /// Returns if b-node has been reached just now. |
485 /// Returns if b-node has been reached just now. |
486 bool isBNodeNewlyReached() const { return b_node_newly_reached; } |
486 bool isBNodeNewlyReached() const { return b_node_newly_reached; } |
487 /// Returns if a-node is examined. |
487 /// Returns if a-node is examined. |
488 bool isANodeExamined() const { return actual_edge==INVALID; } |
488 bool isANodeExamined() const { return actual_edge==INVALID; } |
489 /// Returns a-node of the actual edge, so does if the edge is invalid. |
489 /// Returns a-node of the actual edge, so does if the edge is invalid. |
490 Node tail() const { return actual_node; /*FIXME*/} |
490 Node source() const { return actual_node; /*FIXME*/} |
491 /// Returns b-node of the actual edge. |
491 /// Returns b-node of the actual edge. |
492 /// \pre The actual edge have to be valid. |
492 /// \pre The actual edge have to be valid. |
493 Node head() const { return graph->head(actual_edge); } |
493 Node target() const { return graph->target(actual_edge); } |
494 /// Guess what? |
494 /// Guess what? |
495 /// \deprecated |
495 /// \deprecated |
496 const ReachedMap& getReachedMap() const { return reached; } |
496 const ReachedMap& getReachedMap() const { return reached; } |
497 /// Guess what? |
497 /// Guess what? |
498 /// \deprecated |
498 /// \deprecated |
542 /// newly reached node. |
542 /// newly reached node. |
543 Dfs<Graph, ReachedMap, PredMap>& operator++() { |
543 Dfs<Graph, ReachedMap, PredMap>& operator++() { |
544 Parent::operator++(); |
544 Parent::operator++(); |
545 if (this->graph->valid(this->actual_edge) && this->b_node_newly_reached) |
545 if (this->graph->valid(this->actual_edge) && this->b_node_newly_reached) |
546 { |
546 { |
547 pred.set(this->head(), this->actual_edge); |
547 pred.set(this->target(), this->actual_edge); |
548 } |
548 } |
549 return *this; |
549 return *this; |
550 } |
550 } |
551 /// Guess what? |
551 /// Guess what? |
552 /// \deprecated |
552 /// \deprecated |