commons-dev mailing list archives

Site index · List index
Message view « Date » · « Thread »
Top « Date » · « Thread »
From Thomas Neidhart <thomas.neidh...@gmail.com>
Subject Re: [graph] Doubts on DFS algorithm implementation
Date Thu, 01 Mar 2012 07:59:54 GMT
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

Mime
  • Unnamed multipart/alternative (inline, None, 0 bytes)
View raw message