You are viewing a plain text version of this content. The canonical link for it is here.
Posted to issues@commons.apache.org by "Marco Speranza (Created) (JIRA)" <ji...@apache.org> on 2012/02/02 23:12:54 UTC
[jira] [Created] (SANDBOX-385) Provide Edmonds-Karp algorithm
Provide Edmonds-Karp algorithm
------------------------------
Key: SANDBOX-385
URL: https://issues.apache.org/jira/browse/SANDBOX-385
Project: Commons Sandbox
Issue Type: Improvement
Components: Graph
Reporter: Marco Speranza
Add the [Edmonds-Karp|http://en.wikipedia.org/wiki/Edmonds-Karp_algorithm] algorithm into org.apache.commons.graph.flow package.
--
This message is automatically generated by JIRA.
If you think it was sent incorrectly, please contact your JIRA administrators: https://issues.apache.org/jira/secure/ContactAdministrators!default.jspa
For more information on JIRA, see: http://www.atlassian.com/software/jira
[jira] [Commented] (SANDBOX-385) Provide Edmonds-Karp algorithm
Posted by "Simone Tripodi (Commented) (JIRA)" <ji...@apache.org>.
[ https://issues.apache.org/jira/browse/SANDBOX-385?page=com.atlassian.jira.plugin.system.issuetabpanels:comment-tabpanel&focusedCommentId=13200050#comment-13200050 ]
Simone Tripodi commented on SANDBOX-385:
----------------------------------------
Ciao Claudio,
great, looking forward to apply your patch!!!
> Provide Edmonds-Karp algorithm
> ------------------------------
>
> Key: SANDBOX-385
> URL: https://issues.apache.org/jira/browse/SANDBOX-385
> Project: Commons Sandbox
> Issue Type: Improvement
> Components: Graph
> Reporter: Marco Speranza
>
> Add the [Edmonds-Karp|http://en.wikipedia.org/wiki/Edmonds-Karp_algorithm] algorithm into org.apache.commons.graph.flow package.
--
This message is automatically generated by JIRA.
If you think it was sent incorrectly, please contact your JIRA administrators: https://issues.apache.org/jira/secure/ContactAdministrators!default.jspa
For more information on JIRA, see: http://www.atlassian.com/software/jira
[jira] [Resolved] (SANDBOX-385) Provide Edmonds-Karp algorithm
Posted by "Simone Tripodi (Resolved) (JIRA)" <ji...@apache.org>.
[ https://issues.apache.org/jira/browse/SANDBOX-385?page=com.atlassian.jira.plugin.system.issuetabpanels:all-tabpanel ]
Simone Tripodi resolved SANDBOX-385.
------------------------------------
Resolution: Fixed
Assignee: Simone Tripodi
Claudio,
amazing. Patch applied, check [r1241056|http://svn.apache.org/viewvc?rev=1241056&view=rev].
The only modification I applied, is transforming the {{FlowNetwork}} as class, in simpler a method.
Thanks again for your contribution!!!
> Provide Edmonds-Karp algorithm
> ------------------------------
>
> Key: SANDBOX-385
> URL: https://issues.apache.org/jira/browse/SANDBOX-385
> Project: Commons Sandbox
> Issue Type: Improvement
> Components: Graph
> Reporter: Marco Speranza
> Assignee: Simone Tripodi
> Attachments: SANDBOX-385_AddedEdmondsKarpImplementationAndTest.patch
>
>
> Add the [Edmonds-Karp|http://en.wikipedia.org/wiki/Edmonds-Karp_algorithm] algorithm into org.apache.commons.graph.flow package.
--
This message is automatically generated by JIRA.
If you think it was sent incorrectly, please contact your JIRA administrators: https://issues.apache.org/jira/secure/ContactAdministrators!default.jspa
For more information on JIRA, see: http://www.atlassian.com/software/jira
[jira] [Commented] (SANDBOX-385) Provide Edmonds-Karp algorithm
Posted by "Claudio Squarcella (Commented) (JIRA)" <ji...@apache.org>.
[ https://issues.apache.org/jira/browse/SANDBOX-385?page=com.atlassian.jira.plugin.system.issuetabpanels:comment-tabpanel&focusedCommentId=13199956#comment-13199956 ]
Claudio Squarcella commented on SANDBOX-385:
--------------------------------------------
Hi,
just an acknowledgement to say that I am working on this. I'll be back when I have a patch ready.
Ciao,
Claudio
> Provide Edmonds-Karp algorithm
> ------------------------------
>
> Key: SANDBOX-385
> URL: https://issues.apache.org/jira/browse/SANDBOX-385
> Project: Commons Sandbox
> Issue Type: Improvement
> Components: Graph
> Reporter: Marco Speranza
>
> Add the [Edmonds-Karp|http://en.wikipedia.org/wiki/Edmonds-Karp_algorithm] algorithm into org.apache.commons.graph.flow package.
--
This message is automatically generated by JIRA.
If you think it was sent incorrectly, please contact your JIRA administrators: https://issues.apache.org/jira/secure/ContactAdministrators!default.jspa
For more information on JIRA, see: http://www.atlassian.com/software/jira
[jira] [Updated] (SANDBOX-385) Provide Edmonds-Karp algorithm
Posted by "Claudio Squarcella (Updated) (JIRA)" <ji...@apache.org>.
[ https://issues.apache.org/jira/browse/SANDBOX-385?page=com.atlassian.jira.plugin.system.issuetabpanels:all-tabpanel ]
Claudio Squarcella updated SANDBOX-385:
---------------------------------------
Attachment: SANDBOX-385_AddedEdmondsKarpImplementationAndTest.patch
Hello,
I implemented Edmonds-Karp plus a test for it.
I also found a bug in the previous implementation of {{DefaultVisitAlgorithmsSelector}} and fixed it: vertices are added to the visit stack/queue only if the edge leading to them is actually discovered.
Finally I extracted common code in the {{FlowNetworkHandler}} creating a utility class called {{FlowNetwork}}, that represents a directed graph with flow capacity.
Hoping this helps,
Claudio
> Provide Edmonds-Karp algorithm
> ------------------------------
>
> Key: SANDBOX-385
> URL: https://issues.apache.org/jira/browse/SANDBOX-385
> Project: Commons Sandbox
> Issue Type: Improvement
> Components: Graph
> Reporter: Marco Speranza
> Attachments: SANDBOX-385_AddedEdmondsKarpImplementationAndTest.patch
>
>
> Add the [Edmonds-Karp|http://en.wikipedia.org/wiki/Edmonds-Karp_algorithm] algorithm into org.apache.commons.graph.flow package.
--
This message is automatically generated by JIRA.
If you think it was sent incorrectly, please contact your JIRA administrators: https://issues.apache.org/jira/secure/ContactAdministrators!default.jspa
For more information on JIRA, see: http://www.atlassian.com/software/jira