commons-dev mailing list archives

Site index · List index
Message view « Date » · « Thread »
Top « Date » · « Thread »
From Marco Speranza <marco.speranz...@gmail.com>
Subject Re: [graph] Doubts on DFS algorithm implementation
Date Thu, 01 Mar 2012 08:15:01 GMT
> But I would like to discuss the visitor behavior in general, as I was
> working on a SCC algorithm (Kosaraju), and found it quite difficult to
> implement the recursive traversal using the visitor.

yep, yesterday night I was trying to implementing Kosaraju algo and I found the same difficulties.

IMHO the problem is that the DFS is a recursive algo, in our implementation we are trying
to implement it in a iterative way. 
The result of course is the same but the internal steps are different and this for Kosaraju
algo can be a problem.

Some days ago I opened in Jira the issue SANDBOX-353 I think that we can put there our doubts
on the implementation.

hav a nice day 

--
Marco Speranza <marco.speranza79@gmail.com>

Flickr: http://www.flickr.com/photos/marcosperanza79/
Google Code: http://code.google.com/u/marco.speranza79/




Il giorno 01/mar/2012, alle ore 08:59, Thomas Neidhart ha scritto:

> On Thu, Mar 1, 2012 at 8:34 AM, Marco Speranza <marcosperanza@apache.org>wrote:
> 
>> 
>>> In the old BFS implementation, the discoverEdge method in the visitor
>>> was even called for nodes that have been already visited, which is not
>>> the case anymore. From my understanding the new behavior is correct, or
>>> am I missing something?
>> 
>> I don't think so. in the old algo there was a check to avoid to call
>> already visited nodes.
>> 
> 
> ah you are right.
> 
> There is a bug in the new BFS, in that a vertex is marked visited although
> it has not been discovered yet. This should be changed.
> 
> But I would like to discuss the visitor behavior in general, as I was
> working on a SCC algorithm (Kosaraju), and found it quite difficult to
> implement the recursive traversal using the visitor.
> 
> Thomas


---------------------------------------------------------------------
To unsubscribe, e-mail: dev-unsubscribe@commons.apache.org
For additional commands, e-mail: dev-help@commons.apache.org


Mime
View raw message