> 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 <[email protected]> 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: [email protected] > For additional commands, e-mail: [email protected] > --------------------------------------------------------------------- To unsubscribe, e-mail: [email protected] For additional commands, e-mail: [email protected]
