equal
deleted
inserted
replaced
58 void pushAndSetReached(Node s) { |
58 void pushAndSetReached(Node s) { |
59 reached.set(s, true); |
59 reached.set(s, true); |
60 if (bfs_queue.empty()) { |
60 if (bfs_queue.empty()) { |
61 bfs_queue.push(s); |
61 bfs_queue.push(s); |
62 graph->first(actual_edge, s); |
62 graph->first(actual_edge, s); |
63 if (graph->valid(actual_edge)) { |
63 if (actual_edge!=INVALID) { |
64 Node w=graph->bNode(actual_edge); |
64 Node w=graph->head(actual_edge); |
65 if (!reached[w]) { |
65 if (!reached[w]) { |
66 bfs_queue.push(w); |
66 bfs_queue.push(w); |
67 reached.set(w, true); |
67 reached.set(w, true); |
68 b_node_newly_reached=true; |
68 b_node_newly_reached=true; |
69 } else { |
69 } else { |
76 } |
76 } |
77 /// As \c BfsIterator<Graph, ReachedMap> works as an edge-iterator, |
77 /// As \c BfsIterator<Graph, ReachedMap> works as an edge-iterator, |
78 /// its \c operator++() iterates on the edges in a bfs order. |
78 /// its \c operator++() iterates on the edges in a bfs order. |
79 BfsIterator<Graph, /*OutEdgeIt,*/ ReachedMap>& |
79 BfsIterator<Graph, /*OutEdgeIt,*/ ReachedMap>& |
80 operator++() { |
80 operator++() { |
81 if (graph->valid(actual_edge)) { |
81 if (actual_edge!=INVALID) { |
82 graph->next(actual_edge); |
82 ++actual_edge; |
83 if (graph->valid(actual_edge)) { |
83 if (actual_edge!=INVALID) { |
84 Node w=graph->bNode(actual_edge); |
84 Node w=graph->head(actual_edge); |
85 if (!reached[w]) { |
85 if (!reached[w]) { |
86 bfs_queue.push(w); |
86 bfs_queue.push(w); |
87 reached.set(w, true); |
87 reached.set(w, true); |
88 b_node_newly_reached=true; |
88 b_node_newly_reached=true; |
89 } else { |
89 } else { |
92 } |
92 } |
93 } else { |
93 } else { |
94 bfs_queue.pop(); |
94 bfs_queue.pop(); |
95 if (!bfs_queue.empty()) { |
95 if (!bfs_queue.empty()) { |
96 graph->first(actual_edge, bfs_queue.front()); |
96 graph->first(actual_edge, bfs_queue.front()); |
97 if (graph->valid(actual_edge)) { |
97 if (actual_edge!=INVALID) { |
98 Node w=graph->bNode(actual_edge); |
98 Node w=graph->head(actual_edge); |
99 if (!reached[w]) { |
99 if (!reached[w]) { |
100 bfs_queue.push(w); |
100 bfs_queue.push(w); |
101 reached.set(w, true); |
101 reached.set(w, true); |
102 b_node_newly_reached=true; |
102 b_node_newly_reached=true; |
103 } else { |
103 } else { |
115 ///\bug Edge have to be in HUGO 0.2 |
115 ///\bug Edge have to be in HUGO 0.2 |
116 operator OutEdgeIt() const { return actual_edge; } |
116 operator OutEdgeIt() const { return actual_edge; } |
117 /// Returns if b-node has been reached just now. |
117 /// Returns if b-node has been reached just now. |
118 bool isBNodeNewlyReached() const { return b_node_newly_reached; } |
118 bool isBNodeNewlyReached() const { return b_node_newly_reached; } |
119 /// Returns if a-node is examined. |
119 /// Returns if a-node is examined. |
120 bool isANodeExamined() const { return !(graph->valid(actual_edge)); } |
120 bool isANodeExamined() const { return actual_edge==INVALID; } |
121 /// Returns a-node of the actual edge, so does if the edge is invalid. |
121 /// Returns a-node of the actual edge, so does if the edge is invalid. |
122 Node aNode() const { return bfs_queue.front(); } |
122 Node aNode() const { return bfs_queue.front(); } |
123 /// \pre The actual edge have to be valid. |
123 /// \pre The actual edge have to be valid. |
124 Node bNode() const { return graph->bNode(actual_edge); } |
124 Node bNode() const { return graph->bNode(actual_edge); } |
125 /// Guess what? |
125 /// Guess what? |
235 /// its \c operator++() iterates on the edges in a dfs order. |
235 /// its \c operator++() iterates on the edges in a dfs order. |
236 DfsIterator<Graph, /*OutEdgeIt,*/ ReachedMap>& |
236 DfsIterator<Graph, /*OutEdgeIt,*/ ReachedMap>& |
237 operator++() { |
237 operator++() { |
238 actual_edge=dfs_stack.top(); |
238 actual_edge=dfs_stack.top(); |
239 //actual_node=G.aNode(actual_edge); |
239 //actual_node=G.aNode(actual_edge); |
240 if (graph->valid(actual_edge)/*.valid()*/) { |
240 if (actual_edge!=INVALID/*.valid()*/) { |
241 Node w=graph->bNode(actual_edge); |
241 Node w=graph->head(actual_edge); |
242 actual_node=w; |
242 actual_node=w; |
243 if (!reached[w]) { |
243 if (!reached[w]) { |
244 OutEdgeIt e; |
244 OutEdgeIt e; |
245 graph->first(e, w); |
245 graph->first(e, w); |
246 dfs_stack.push(e); |
246 dfs_stack.push(e); |
247 reached.set(w, true); |
247 reached.set(w, true); |
248 b_node_newly_reached=true; |
248 b_node_newly_reached=true; |
249 } else { |
249 } else { |
250 actual_node=graph->aNode(actual_edge); |
250 actual_node=graph->tail(actual_edge); |
251 graph->next(dfs_stack.top()); |
251 ++dfs_stack.top(); |
252 b_node_newly_reached=false; |
252 b_node_newly_reached=false; |
253 } |
253 } |
254 } else { |
254 } else { |
255 //actual_node=G.aNode(dfs_stack.top()); |
255 //actual_node=G.aNode(dfs_stack.top()); |
256 dfs_stack.pop(); |
256 dfs_stack.pop(); |
264 ///\bug Edge have to be in HUGO 0.2 |
264 ///\bug Edge have to be in HUGO 0.2 |
265 operator OutEdgeIt() const { return actual_edge; } |
265 operator OutEdgeIt() const { return actual_edge; } |
266 /// Returns if b-node has been reached just now. |
266 /// Returns if b-node has been reached just now. |
267 bool isBNodeNewlyReached() const { return b_node_newly_reached; } |
267 bool isBNodeNewlyReached() const { return b_node_newly_reached; } |
268 /// Returns if a-node is examined. |
268 /// Returns if a-node is examined. |
269 bool isANodeExamined() const { return !(graph->valid(actual_edge)); } |
269 bool isANodeExamined() const { return actual_edge==INVALID; } |
270 /// Returns a-node of the actual edge, so does if the edge is invalid. |
270 /// Returns a-node of the actual edge, so does if the edge is invalid. |
271 Node aNode() const { return actual_node; /*FIXME*/} |
271 Node aNode() const { return actual_node; /*FIXME*/} |
272 /// Returns b-node of the actual edge. |
272 /// Returns b-node of the actual edge. |
273 /// \pre The actual edge have to be valid. |
273 /// \pre The actual edge have to be valid. |
274 Node bNode() const { return graph->bNode(actual_edge); } |
274 Node bNode() const { return graph->bNode(actual_edge); } |