commons-dev mailing list archives

Site index · List index
Message view « Date » · « Thread »
Top « Date » · « Thread »
From Simone Tripodi <simonetrip...@apache.org>
Subject Re: [graph] Doubts on DFS algorithm implementation
Date Sat, 25 Feb 2012 18:48:49 GMT
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


Mime
View raw message