commons-dev mailing list archives

Site index · List index
Message view « Date » · « Thread »
Top « Date » · « Thread »
From Claudio Squarcella <squar...@dia.uniroma3.it>
Subject Re: [graph] Doubts on DFS algorithm implementation
Date Sat, 25 Feb 2012 19:35:59 GMT
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