commons-dev mailing list archives

Site index · List index
Message view « Date » · « Thread »
Top « Date » · « Thread »
From Marco Speranza <marcospera...@apache.org>
Subject Re: [graph] Doubts on DFS algorithm implementation
Date Thu, 01 Mar 2012 07:34:56 GMT

> 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.

I think that there are some problem with the new visit, but I don't still found it. 
The test case checks this example http://en.wikipedia.org/wiki/Edmonds–Karp_algorithm and
the expectation of max flow equals to 5 is right. 

have a nice day

--
Marco Speranza <marcosperanza@apache.org>
Google Code: http://code.google.com/u/marco.speranza79/

Il giorno 29/feb/2012, alle ore 23:58, Thomas Neidhart ha scritto:

> On 02/29/2012 11:07 PM, Marco Speranza wrote:
>> Cool good job...
>> 
>> Only one think.. I ran the tests and I experienced one failure: 
>> 
>> ====
>> Results :
>> 
>> Failed tests:   findMaxFlowAndVerify(org.apache.commons.graph.flow.EdmondsKarpTestCase):
expected:<3> but was:<5>
>> 
>> Tests run: 109, Failures: 1, Errors: 0, Skipped: 1
>> 
>> [INFO] ------------------------------------------------------------------------
>> [INFO] BUILD FAILURE
>> [INFO] ------------------------------------------------------------------------
>> ====
>> 
>> the Edmonds and Karp algo uses the Breadth First Search, maybe there are some problem
in bsf  visit.
> 
> ah, thanks for pointing that out. I debugged the Edmonds algorithm, and
> I have an idea where this problem may come from:
> 
> 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?
> 
> Thomas
> 
> ---------------------------------------------------------------------
> 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


Mime
View raw message