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 Wed, 29 Feb 2012 22:58:30 GMT
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


Mime
View raw message