commons-dev mailing list archives

Site index · List index
Message view « Date » · « Thread »
Top « Date » · « Thread »
From Marco Speranza <marcospera...@apache.org>
Subject Re: [graph] Doubts on DFS algorithm implementation
Date Sun, 26 Feb 2012 13:33:21 GMT
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 <marcosperanza@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
>> <simonetripodi@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
>>> <marcosperanza@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<marcosperanza@apache.org>
>>>> Google Code: http://code.google.com/u/marco.speranza79/
>>>> 
>>> ---------------------------------------------------------------------
>>> To unsubscribe, e-mail: dev-unsubscribe@commons.apache.org
>>> For additional commands, e-mail: dev-help@commons.apache.org
>>> 
>> ---------------------------------------------------------------------
>> To unsubscribe, e-mail: dev-unsubscribe@commons.apache.org
>> For additional commands, e-mail: dev-help@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-unsubscribe@commons.apache.org
> For additional commands, e-mail: dev-help@commons.apache.org
> 


Mime
View raw message