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 18:06:48 GMT
Hi Thomas,

I run the test and it seems that the BSF explore twice the same edge. 

====

Tests run: 3, Failures: 0, Errors: 1, Skipped: 0, Time elapsed: 0.025 sec <<< FAILURE!

Results :

Tests in error: 
  verifyBreadthFirstSearch(org.apache.commons.graph.visit.VisitTestCase): Edge x <->
y() is already present in the Graph

Tests run: 109, Failures: 0, Errors: 1, Skipped: 0

====

I think that we have to add also a list of the visited edges to avoid that. 

Do you agree with me?

Ciao

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

Il giorno 01/mar/2012, alle ore 18:45, Thomas Neidhart ha scritto:

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


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


Mime
View raw message