commons-dev mailing list archives

Site index · List index
Message view « Date » · « Thread »
Top « Date » · « Thread »
From James Carman <ja...@carmanconsulting.com>
Subject Re: [graph] Doubts on DFS algorithm implementation
Date Sat, 25 Feb 2012 18:51:25 GMT
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
<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


Mime
View raw message