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 Thu, 01 Mar 2012 08:10:04 GMT
Hi +,

I can report the same test failure:

Failed tests:
findMaxFlowAndVerify(org.apache.commons.graph.flow.EdmondsKarpTestCase):
expected:<3> but was:<5>

I just applied trivial modifications without altering the algorithms
behavior, I am sure the fix is under our eyes :)

Thanks all, have a nice day!
-Simo

http://people.apache.org/~simonetripodi/
http://simonetripodi.livejournal.com/
http://twitter.com/simonetripodi
http://www.99soft.org/



On Thu, Mar 1, 2012 at 8:59 AM, Thomas Neidhart
<thomas.neidhart@gmail.com> wrote:
> 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