The code shouldn't "visit" each of the connected nodes during the iteration. It should only visit the "popped" node and then add all un-visited, connected nodes to the stack. Hopefully we've implemented this so that all we have to do to switch from dfs to bfs is to swap out the collection used. If you switch to a queue rather than a stack, it magically changes to bfs. I've done this before using the "buffer" abstraction in commons collections.
On Sat, Feb 25, 2012 at 1:48 PM, Simone Tripodi <simonetrip...@apache.org> wrote: > Hi Marco, > > IIRC the vertex order should be guarded by the vertexStack - maybe it > is just the handler be called in the wrong way. > > Do you have/can you provide please testcases? > > TIA, > -SImo > > http://people.apache.org/~simonetripodi/ > http://simonetripodi.livejournal.com/ > http://twitter.com/simonetripodi > http://www.99soft.org/ > > > > On Sat, Feb 25, 2012 at 6:47 PM, Marco Speranza > <marcospera...@apache.org> wrote: >> Hi all. I've a little doubt on DFS algorithm implemented in the >> DefaultVisitAlgorithmsSelector. >> >> I think that the visit doesn't serch in depth but in a breadth way. >> >> here is a little code snippet: >> >> [ ... ] >> >> while ( visitingGraph && !vertexStack.isEmpty() ) >> { >> V v = vertexStack.pop(); >> >> if ( handler.discoverVertex( v ) ) >> { >> Iterator<V> connected = ( graph instanceof DirectedGraph ) ? >> ( (DirectedGraph<V, E>) graph ).getOutbound( v ).iterator() >> : graph.getConnectedVertices( v ).iterator(); >> >> while ( connected.hasNext() ) >> { >> V w = connected.next(); >> if ( !visitedVertices.contains( w ) ) >> { >> E e = graph.getEdge( v, w ); >> >> if ( handler.discoverEdge( v, e, w ) ) >> { >> [ ... ] >> >> >> I think that the algo explores the edge, and than fires >> handler.discoverEdge( v, e, w ), in breadth and not in depth, doesn't it? >> >> best regards >> >> >> -- >> Marco Speranza <marcospera...@apache.org> >> Google Code: http://code.google.com/u/marco.speranza79/ >> > > --------------------------------------------------------------------- > To unsubscribe, e-mail: dev-unsubscr...@commons.apache.org > For additional commands, e-mail: dev-h...@commons.apache.org > --------------------------------------------------------------------- To unsubscribe, e-mail: dev-unsubscr...@commons.apache.org For additional commands, e-mail: dev-h...@commons.apache.org
