equal
deleted
inserted
replaced
21 ///\file |
21 ///\file |
22 ///\brief %DFS algorithm. |
22 ///\brief %DFS algorithm. |
23 /// |
23 /// |
24 ///\todo Revise Manual. |
24 ///\todo Revise Manual. |
25 |
25 |
26 #include <lemon/bin_heap.h> |
26 #include <lemon/graph_utils.h> |
27 #include <lemon/invalid.h> |
27 #include <lemon/invalid.h> |
28 |
28 |
29 namespace lemon { |
29 namespace lemon { |
30 |
30 |
31 /// \addtogroup flowalgs |
31 /// \addtogroup flowalgs |
191 for ( NodeIt u(*G) ; u!=INVALID ; ++u ) { |
191 for ( NodeIt u(*G) ; u!=INVALID ; ++u ) { |
192 predecessor->set(u,INVALID); |
192 predecessor->set(u,INVALID); |
193 pred_node->set(u,INVALID); |
193 pred_node->set(u,INVALID); |
194 } |
194 } |
195 |
195 |
196 int N=G->nodeNum(); |
196 int N = countNodes(*G); |
197 std::vector<typename Graph::OutEdgeIt> Q(N); |
197 std::vector<typename Graph::OutEdgeIt> Q(N); |
198 |
198 |
199 int Qh=0; |
199 int Qh=0; |
200 |
200 |
201 G->first(Q[Qh],s); |
201 Q[Qh] = OutEdgeIt(*G, s); |
202 distance->set(s, 0); |
202 distance->set(s, 0); |
203 |
203 |
204 Node n=s; |
204 Node n=s; |
205 Node m; |
205 Node m; |
206 OutEdgeIt e; |
206 OutEdgeIt e; |
207 do { |
207 do { |
208 if((e=Q[Qh])!=INVALID) |
208 if((e=Q[Qh])!=INVALID) |
209 if((m=G->head(e))!=s && (*predecessor)[m=G->head(e)]==INVALID) { |
209 if((m=G->head(e))!=s && (*predecessor)[m=G->head(e)]==INVALID) { |
210 predecessor->set(m,e); |
210 predecessor->set(m,e); |
211 pred_node->set(m,n); |
211 pred_node->set(m,n); |
212 G->first(Q[++Qh],m); |
212 Q[++Qh] = OutEdgeIt(*G, m); |
213 distance->set(m,Qh); |
213 distance->set(m,Qh); |
214 n=m; |
214 n=m; |
215 } |
215 } |
216 else ++Q[Qh]; |
216 else ++Q[Qh]; |
217 else if(--Qh>=0) n=G->tail(Q[Qh]); |
217 else if(--Qh>=0) n=G->tail(Q[Qh]); |