Hi all > IIRC the vertex order should be guarded by the vertexStack - maybe it > is just the handler be called in the wrong way
Simo you are right, the vertices have visited in the right way, but the edge handler has called in the wrong way. IMHO we have to modify the code in order to fire the edge handler in the right way to avoid any error for the user. > 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. > It's a good idea, Now we have implemented two separate methods that visit the graph for dfs and bfs. We should do a little refactoring and implement a unique method that switches between dfs and bfs simply changing the the type of visitedVertex. WDYT? > I think "visitedVertices" should rather be called "seenVertices", as it is > only needed to avoid adding vertices more than once to the stack/queue. Marco > (and all), please see if the implementations look nicer with that change in > mind (looks good to me). > +1 have a nice day guys ;) -- Marco Speranza <marcospera...@apache.org> Google Code: http://code.google.com/u/marco.speranza79/ Il giorno 25/feb/2012, alle ore 20:35, Claudio Squarcella ha scritto: > Hi, > > On 25/02/2012 19:51, James Carman wrote: >> 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. > > I think "visitedVertices" should rather be called "seenVertices", as it is > only needed to avoid adding vertices more than once to the stack/queue. Marco > (and all), please see if the implementations look nicer with that change in > mind (looks good to me). > > Claudio > >> >> 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 >> > > -- > Claudio Squarcella > PhD student at Roma Tre University > http://www.dia.uniroma3.it/~squarcel > http://squarcella.com/ > > > --------------------------------------------------------------------- > To unsubscribe, e-mail: dev-unsubscr...@commons.apache.org > For additional commands, e-mail: dev-h...@commons.apache.org >
signature.asc
Description: Message signed with OpenPGP using GPGMail
