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 17:45:18 GMT
On 03/01/2012 09:10 AM, Simone Tripodi wrote:
> 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 :)

ok. It is fixed now.

The problem was basically, that once a vertex was pushed onto the stack,
it was immediately marked as visited. In case you have a custom visitor
that would instruct you to not visit the tail node for some reason, the
algorithm would never reach that vertex anymore as it thinks the vertex
was already visited.

Thomas

---------------------------------------------------------------------
To unsubscribe, e-mail: dev-unsubscribe@commons.apache.org
For additional commands, e-mail: dev-help@commons.apache.org


Mime
View raw message