You are viewing a plain text version of this content. The canonical link for it is here.
Posted to dev@commons.apache.org by Marco Speranza <ma...@apache.org> on 2012/03/01 08:34:56 UTC
Re: [graph] Doubts on DFS algorithm implementation
> 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 <ma...@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
Re: [graph] Doubts on DFS algorithm implementation
Posted by Marco Speranza <ma...@gmail.com>.
> But I would like to discuss the visitor behavior in general, as I was
> working on a SCC algorithm (Kosaraju), and found it quite difficult to
> implement the recursive traversal using the visitor.
yep, yesterday night I was trying to implementing Kosaraju algo and I found the same difficulties.
IMHO the problem is that the DFS is a recursive algo, in our implementation we are trying to implement it in a iterative way.
The result of course is the same but the internal steps are different and this for Kosaraju algo can be a problem.
Some days ago I opened in Jira the issue SANDBOX-353 I think that we can put there our doubts on the implementation.
hav a nice day
--
Marco Speranza <ma...@gmail.com>
Flickr: http://www.flickr.com/photos/marcosperanza79/
Google Code: http://code.google.com/u/marco.speranza79/
Il giorno 01/mar/2012, alle ore 08:59, Thomas Neidhart ha scritto:
> On Thu, Mar 1, 2012 at 8:34 AM, Marco Speranza <ma...@apache.org>wrote:
>
>>
>>> 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.
>>
>
> ah you are right.
>
> There is a bug in the new BFS, in that a vertex is marked visited although
> it has not been discovered yet. This should be changed.
>
> But I would like to discuss the visitor behavior in general, as I was
> working on a SCC algorithm (Kosaraju), and found it quite difficult to
> implement the recursive traversal using the visitor.
>
> Thomas
---------------------------------------------------------------------
To unsubscribe, e-mail: dev-unsubscribe@commons.apache.org
For additional commands, e-mail: dev-help@commons.apache.org
Re: [graph] Doubts on DFS algorithm implementation
Posted by Claudio Squarcella <sq...@dia.uniroma3.it>.
Hi,
> Added an extra check to prevent
> discovering multiple edges that lead to the same (already visited) vertex.
cool stuff, thanks for turning human words into computer words :)
I spent a couple minutes running the tests on max-flow algos with
breakpoints and stuff, and apparently they keep avoiding zero-capacity
links during graph visit. Excellent!
Claudio
--
Claudio Squarcella
PhD student at Roma Tre University
http://www.dia.uniroma3.it/~squarcel
http://squarcella.com/
---------------------------------------------------------------------
To unsubscribe, e-mail: dev-unsubscribe@commons.apache.org
For additional commands, e-mail: dev-help@commons.apache.org
Re: [graph] Doubts on DFS algorithm implementation
Posted by Simone Tripodi <si...@apache.org>.
terrific, indeed!!!
very well done!
-Simo
http://people.apache.org/~simonetripodi/
http://simonetripodi.livejournal.com/
http://twitter.com/simonetripodi
http://www.99soft.org/
On Thu, Mar 1, 2012 at 7:38 PM, Marco Speranza <ma...@apache.org> wrote:
> Ok great! now works
> thanks you!
>
> --
> Marco Speranza <ma...@apache.org>
> Google Code: http://code.google.com/u/marco.speranza79/
>
> Il giorno 01/mar/2012, alle ore 19:32, Thomas Neidhart ha scritto:
>
>> On 03/01/2012 07:06 PM, Marco Speranza wrote:
>>> 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?
>>
>> yes, sorry, I was too fast committing. Added an extra check to prevent
>> discovering multiple edges that lead to the same (already visited) vertex.
>>
>> 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
>
---------------------------------------------------------------------
To unsubscribe, e-mail: dev-unsubscribe@commons.apache.org
For additional commands, e-mail: dev-help@commons.apache.org
Re: [graph] Doubts on DFS algorithm implementation
Posted by Marco Speranza <ma...@apache.org>.
Ok great! now works
thanks you!
--
Marco Speranza <ma...@apache.org>
Google Code: http://code.google.com/u/marco.speranza79/
Il giorno 01/mar/2012, alle ore 19:32, Thomas Neidhart ha scritto:
> On 03/01/2012 07:06 PM, Marco Speranza wrote:
>> 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?
>
> yes, sorry, I was too fast committing. Added an extra check to prevent
> discovering multiple edges that lead to the same (already visited) vertex.
>
> 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
Re: [graph] Doubts on DFS algorithm implementation
Posted by Thomas Neidhart <th...@gmail.com>.
On 03/01/2012 07:06 PM, Marco Speranza wrote:
> 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?
yes, sorry, I was too fast committing. Added an extra check to prevent
discovering multiple edges that lead to the same (already visited) vertex.
Thomas
---------------------------------------------------------------------
To unsubscribe, e-mail: dev-unsubscribe@commons.apache.org
For additional commands, e-mail: dev-help@commons.apache.org
Re: [graph] Doubts on DFS algorithm implementation
Posted by Marco Speranza <ma...@apache.org>.
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 <ma...@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
Re: [graph] Doubts on DFS algorithm implementation
Posted by Thomas Neidhart <th...@gmail.com>.
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
Re: [graph] Doubts on DFS algorithm implementation
Posted by Simone Tripodi <si...@apache.org>.
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 :)
Thanks all, have a nice day!
-Simo
http://people.apache.org/~simonetripodi/
http://simonetripodi.livejournal.com/
http://twitter.com/simonetripodi
http://www.99soft.org/
On Thu, Mar 1, 2012 at 8:59 AM, Thomas Neidhart
<th...@gmail.com> wrote:
> On Thu, Mar 1, 2012 at 8:34 AM, Marco Speranza <ma...@apache.org>wrote:
>
>>
>> > 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.
>>
>
> ah you are right.
>
> There is a bug in the new BFS, in that a vertex is marked visited although
> it has not been discovered yet. This should be changed.
>
> But I would like to discuss the visitor behavior in general, as I was
> working on a SCC algorithm (Kosaraju), and found it quite difficult to
> implement the recursive traversal using the visitor.
>
> Thomas
---------------------------------------------------------------------
To unsubscribe, e-mail: dev-unsubscribe@commons.apache.org
For additional commands, e-mail: dev-help@commons.apache.org
Re: [graph] Doubts on DFS algorithm implementation
Posted by Thomas Neidhart <th...@gmail.com>.
On Thu, Mar 1, 2012 at 8:34 AM, Marco Speranza <ma...@apache.org>wrote:
>
> > 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.
>
ah you are right.
There is a bug in the new BFS, in that a vertex is marked visited although
it has not been discovered yet. This should be changed.
But I would like to discuss the visitor behavior in general, as I was
working on a SCC algorithm (Kosaraju), and found it quite difficult to
implement the recursive traversal using the visitor.
Thomas