You are viewing a plain text version of this content. The canonical link for it is here.
Posted to issues@commons.apache.org by "Simone Tripodi (Created) (JIRA)" <ji...@apache.org> on 2011/12/20 10:11:30 UTC
[jira] [Created] (SANDBOX-348) Implement the Boruvka's algorithm
Implement the Boruvka's algorithm
---------------------------------
Key: SANDBOX-348
URL: https://issues.apache.org/jira/browse/SANDBOX-348
Project: Commons Sandbox
Issue Type: Sub-task
Reporter: Simone Tripodi
Assignee: Simone Tripodi
The class {{org.apache.commons.graph.spanning.Boruvka}} contains an empty implementation of [Boruvka|http://en.wikipedia.org/wiki/Bor%C5%AFvka's_algorithm]'s algorithm, that needs to be filled.
--
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-348) Implement the Boruvka's algorithm
Posted by "Marco Speranza (Updated) (JIRA)" <ji...@apache.org>.
[ https://issues.apache.org/jira/browse/SANDBOX-348?page=com.atlassian.jira.plugin.system.issuetabpanels:all-tabpanel ]
Marco Speranza updated SANDBOX-348:
-----------------------------------
Attachment: SANDBOX-348_Boruvka_algorithm_implementation.patch
Hi guys, here is my implementation of Boruvka's algo.
I'm available for comments and tips
ciao
> Implement the Boruvka's algorithm
> ---------------------------------
>
> Key: SANDBOX-348
> URL: https://issues.apache.org/jira/browse/SANDBOX-348
> Project: Commons Sandbox
> Issue Type: Sub-task
> Components: Graph
> Reporter: Simone Tripodi
> Assignee: Simone Tripodi
> Attachments: SANDBOX-348-ConnectivityAlgo.patch, SANDBOX-348_Boruvka_algorithm_implementation.patch
>
>
> The class {{org.apache.commons.graph.spanning.Boruvka}} contains an empty implementation of [Boruvka|http://en.wikipedia.org/wiki/Bor%C5%AFvka's_algorithm]'s algorithm, that needs to be filled.
--
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-348) Implement the Boruvka's algorithm
Posted by "Simone Tripodi (Commented) (JIRA)" <ji...@apache.org>.
[ https://issues.apache.org/jira/browse/SANDBOX-348?page=com.atlassian.jira.plugin.system.issuetabpanels:comment-tabpanel&focusedCommentId=13196827#comment-13196827 ]
Simone Tripodi commented on SANDBOX-348:
----------------------------------------
maybe - even if related to the Boruvka's algorithm - that's the wrong location :P
I 'll fill a new issue just to track the type of patch we are applying ;)
> Implement the Boruvka's algorithm
> ---------------------------------
>
> Key: SANDBOX-348
> URL: https://issues.apache.org/jira/browse/SANDBOX-348
> Project: Commons Sandbox
> Issue Type: Sub-task
> Components: Graph
> Reporter: Simone Tripodi
> Assignee: Simone Tripodi
> Attachments: SANDBOX-348-ConnectivityAlgo.patch
>
>
> The class {{org.apache.commons.graph.spanning.Boruvka}} contains an empty implementation of [Boruvka|http://en.wikipedia.org/wiki/Bor%C5%AFvka's_algorithm]'s algorithm, that needs to be filled.
--
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-348) Implement the Boruvka's algorithm
Posted by "Thomas Neidhart (Commented) (JIRA)" <ji...@apache.org>.
[ https://issues.apache.org/jira/browse/SANDBOX-348?page=com.atlassian.jira.plugin.system.issuetabpanels:comment-tabpanel&focusedCommentId=13201226#comment-13201226 ]
Thomas Neidhart commented on SANDBOX-348:
-----------------------------------------
Ok, I have committed the changes with your suggestions in r1240978.
> Implement the Boruvka's algorithm
> ---------------------------------
>
> Key: SANDBOX-348
> URL: https://issues.apache.org/jira/browse/SANDBOX-348
> Project: Commons Sandbox
> Issue Type: Sub-task
> Components: Graph
> Reporter: Simone Tripodi
> Assignee: Simone Tripodi
> Attachments: BoruvkaTestCase2.java, DefaultSpanningTreeAlgorithmSelector.java, SANDBOX-348-ConnectivityAlgo.patch, SANDBOX-348_Boruvka_algorithm_implementation.patch
>
>
> The class {{org.apache.commons.graph.spanning.Boruvka}} contains an empty implementation of [Boruvka|http://en.wikipedia.org/wiki/Bor%C5%AFvka's_algorithm]'s algorithm, that needs to be filled.
--
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-348) Implement the Boruvka's algorithm
Posted by "Simone Tripodi (Commented) (JIRA)" <ji...@apache.org>.
[ https://issues.apache.org/jira/browse/SANDBOX-348?page=com.atlassian.jira.plugin.system.issuetabpanels:comment-tabpanel&focusedCommentId=13197195#comment-13197195 ]
Simone Tripodi commented on SANDBOX-348:
----------------------------------------
Hi Thomas,
welcome in the graph brotherhood!!! ;)
Indeed, Boruvka is the less performant algorithm for the MST search, the reason to keep it is that commons-graph aims to be a graph-pedia reference implementation, so users are free to use the algorithm they prefer - I cannot immagine why they would prefer Boruvka instead of Kruskal, but maybe there are conditions under which it could work.
That means that, if you are interested on graph/have any proposal, please feel free to fill an issue and provide an impl! Have a look also to current open issues/task and, if you are using eclipse, there are some type inference errors detected that need to be fixed ;)
As a side note: do you mind sharing the benchmarks you wrote on MST algos?
Many thanks in advance,
-Simo
> Implement the Boruvka's algorithm
> ---------------------------------
>
> Key: SANDBOX-348
> URL: https://issues.apache.org/jira/browse/SANDBOX-348
> Project: Commons Sandbox
> Issue Type: Sub-task
> Components: Graph
> Reporter: Simone Tripodi
> Assignee: Simone Tripodi
> Attachments: SANDBOX-348-ConnectivityAlgo.patch, SANDBOX-348_Boruvka_algorithm_implementation.patch
>
>
> The class {{org.apache.commons.graph.spanning.Boruvka}} contains an empty implementation of [Boruvka|http://en.wikipedia.org/wiki/Bor%C5%AFvka's_algorithm]'s algorithm, that needs to be filled.
--
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-348) Implement the Boruvka's algorithm
Posted by "Simone Tripodi (Commented) (JIRA)" <ji...@apache.org>.
[ https://issues.apache.org/jira/browse/SANDBOX-348?page=com.atlassian.jira.plugin.system.issuetabpanels:comment-tabpanel&focusedCommentId=13201233#comment-13201233 ]
Simone Tripodi commented on SANDBOX-348:
----------------------------------------
Thank you Thomas, and welcome to the brotherhood! :)
> Implement the Boruvka's algorithm
> ---------------------------------
>
> Key: SANDBOX-348
> URL: https://issues.apache.org/jira/browse/SANDBOX-348
> Project: Commons Sandbox
> Issue Type: Sub-task
> Components: Graph
> Reporter: Simone Tripodi
> Assignee: Simone Tripodi
> Attachments: BoruvkaTestCase2.java, DefaultSpanningTreeAlgorithmSelector.java, SANDBOX-348-ConnectivityAlgo.patch, SANDBOX-348_Boruvka_algorithm_implementation.patch
>
>
> The class {{org.apache.commons.graph.spanning.Boruvka}} contains an empty implementation of [Boruvka|http://en.wikipedia.org/wiki/Bor%C5%AFvka's_algorithm]'s algorithm, that needs to be filled.
--
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-348) Implement the Boruvka's algorithm
Posted by "Simone Tripodi (Commented) (JIRA)" <ji...@apache.org>.
[ https://issues.apache.org/jira/browse/SANDBOX-348?page=com.atlassian.jira.plugin.system.issuetabpanels:comment-tabpanel&focusedCommentId=13196836#comment-13196836 ]
Simone Tripodi commented on SANDBOX-348:
----------------------------------------
I tracked the progress on SANDBOX-375, thanks for the patch!
> Implement the Boruvka's algorithm
> ---------------------------------
>
> Key: SANDBOX-348
> URL: https://issues.apache.org/jira/browse/SANDBOX-348
> Project: Commons Sandbox
> Issue Type: Sub-task
> Components: Graph
> Reporter: Simone Tripodi
> Assignee: Simone Tripodi
> Attachments: SANDBOX-348-ConnectivityAlgo.patch
>
>
> The class {{org.apache.commons.graph.spanning.Boruvka}} contains an empty implementation of [Boruvka|http://en.wikipedia.org/wiki/Bor%C5%AFvka's_algorithm]'s algorithm, that needs to be filled.
--
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-348) Implement the Boruvka's algorithm
Posted by "Thomas Neidhart (Updated) (JIRA)" <ji...@apache.org>.
[ https://issues.apache.org/jira/browse/SANDBOX-348?page=com.atlassian.jira.plugin.system.issuetabpanels:all-tabpanel ]
Thomas Neidhart updated SANDBOX-348:
------------------------------------
Attachment: BoruvkaTestCase2.java
DefaultSpanningTreeAlgorithmSelector.java
Hi Simone,
I took the time and updated my attempt on Boruvka's algorithm, and you can find it in attachment together with a quite simple performance test case.
It is based on the SuperVertex idea, and can be further improved by updating the edge list for each SuperVertex instead of re-calculating it each time.
The files are provided as is, please take a look at it and if you find it useful, I can create a proper patch.
Thomas
> Implement the Boruvka's algorithm
> ---------------------------------
>
> Key: SANDBOX-348
> URL: https://issues.apache.org/jira/browse/SANDBOX-348
> Project: Commons Sandbox
> Issue Type: Sub-task
> Components: Graph
> Reporter: Simone Tripodi
> Assignee: Simone Tripodi
> Attachments: BoruvkaTestCase2.java, DefaultSpanningTreeAlgorithmSelector.java, SANDBOX-348-ConnectivityAlgo.patch, SANDBOX-348_Boruvka_algorithm_implementation.patch
>
>
> The class {{org.apache.commons.graph.spanning.Boruvka}} contains an empty implementation of [Boruvka|http://en.wikipedia.org/wiki/Bor%C5%AFvka's_algorithm]'s algorithm, that needs to be filled.
--
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-348) Implement the Boruvka's algorithm
Posted by "Simone Tripodi (Commented) (JIRA)" <ji...@apache.org>.
[ https://issues.apache.org/jira/browse/SANDBOX-348?page=com.atlassian.jira.plugin.system.issuetabpanels:comment-tabpanel&focusedCommentId=13200949#comment-13200949 ]
Simone Tripodi commented on SANDBOX-348:
----------------------------------------
Hi Thomas!
simply brilliant, thanks for your effort! There's no need to provide a patch, since you are already a commons committer feel free to commit the modifications and don't forget to add yourself in the developers list in the pom ;)
I have just 2 minor observations:
* There is no reason to keep 2 Boruvka implementations, so let's keep just the fastest
* I just suggest to move the {{SuperVertex}} in its proper classfile, to simplify the algorithms class.
Very well done, thanks!
> Implement the Boruvka's algorithm
> ---------------------------------
>
> Key: SANDBOX-348
> URL: https://issues.apache.org/jira/browse/SANDBOX-348
> Project: Commons Sandbox
> Issue Type: Sub-task
> Components: Graph
> Reporter: Simone Tripodi
> Assignee: Simone Tripodi
> Attachments: BoruvkaTestCase2.java, DefaultSpanningTreeAlgorithmSelector.java, SANDBOX-348-ConnectivityAlgo.patch, SANDBOX-348_Boruvka_algorithm_implementation.patch
>
>
> The class {{org.apache.commons.graph.spanning.Boruvka}} contains an empty implementation of [Boruvka|http://en.wikipedia.org/wiki/Bor%C5%AFvka's_algorithm]'s algorithm, that needs to be filled.
--
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-348) Implement the Boruvka's algorithm
Posted by "Simone Tripodi (Resolved) (JIRA)" <ji...@apache.org>.
[ https://issues.apache.org/jira/browse/SANDBOX-348?page=com.atlassian.jira.plugin.system.issuetabpanels:all-tabpanel ]
Simone Tripodi resolved SANDBOX-348.
------------------------------------
Resolution: Fixed
Patch applied, see [r1238692|http://svn.apache.org/viewvc?rev=1238692&view=rev] for details.
Thanks for contributing!
> Implement the Boruvka's algorithm
> ---------------------------------
>
> Key: SANDBOX-348
> URL: https://issues.apache.org/jira/browse/SANDBOX-348
> Project: Commons Sandbox
> Issue Type: Sub-task
> Components: Graph
> Reporter: Simone Tripodi
> Assignee: Simone Tripodi
> Attachments: SANDBOX-348-ConnectivityAlgo.patch, SANDBOX-348_Boruvka_algorithm_implementation.patch
>
>
> The class {{org.apache.commons.graph.spanning.Boruvka}} contains an empty implementation of [Boruvka|http://en.wikipedia.org/wiki/Bor%C5%AFvka's_algorithm]'s algorithm, that needs to be filled.
--
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-348) Implement the Boruvka's algorithm
Posted by "Thomas Neidhart (Commented) (JIRA)" <ji...@apache.org>.
[ https://issues.apache.org/jira/browse/SANDBOX-348?page=com.atlassian.jira.plugin.system.issuetabpanels:comment-tabpanel&focusedCommentId=13197177#comment-13197177 ]
Thomas Neidhart commented on SANDBOX-348:
-----------------------------------------
Hi,
actually I was also working on a patch for Boruvka's algorithm, but decided to stop it, as it is really hard to come up with a performant version of it given the current graph interface (and considering that there are already faster alternatives).
Using the current implementation, a non-trivial test case with ~10000 vertices results in the following execution times:
Boruvka took 174559 ms
Prim took 1100 ms
Kruskal took 199 ms
I do not want to spoil Marco's effort, but from my point of view, there is no reason to keep Boruvka's algorithm.
> Implement the Boruvka's algorithm
> ---------------------------------
>
> Key: SANDBOX-348
> URL: https://issues.apache.org/jira/browse/SANDBOX-348
> Project: Commons Sandbox
> Issue Type: Sub-task
> Components: Graph
> Reporter: Simone Tripodi
> Assignee: Simone Tripodi
> Attachments: SANDBOX-348-ConnectivityAlgo.patch, SANDBOX-348_Boruvka_algorithm_implementation.patch
>
>
> The class {{org.apache.commons.graph.spanning.Boruvka}} contains an empty implementation of [Boruvka|http://en.wikipedia.org/wiki/Bor%C5%AFvka's_algorithm]'s algorithm, that needs to be filled.
--
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-348) Implement the Boruvka's algorithm
Posted by "Marco Speranza (Updated) (JIRA)" <ji...@apache.org>.
[ https://issues.apache.org/jira/browse/SANDBOX-348?page=com.atlassian.jira.plugin.system.issuetabpanels:all-tabpanel ]
Marco Speranza updated SANDBOX-348:
-----------------------------------
Attachment: SANDBOX-348-ConnectivityAlgo.patch
Hi all, I provided a simple implementation of connectivity problem. This algo finds the number of the connected component for an input graph.
The algo returns a collection of list of vertices, and it's possible find the connected component for a specific set of vertices.
I am available for comments and tips :-)
ciao
Marco
> Implement the Boruvka's algorithm
> ---------------------------------
>
> Key: SANDBOX-348
> URL: https://issues.apache.org/jira/browse/SANDBOX-348
> Project: Commons Sandbox
> Issue Type: Sub-task
> Components: Graph
> Reporter: Simone Tripodi
> Assignee: Simone Tripodi
> Attachments: SANDBOX-348-ConnectivityAlgo.patch
>
>
> The class {{org.apache.commons.graph.spanning.Boruvka}} contains an empty implementation of [Boruvka|http://en.wikipedia.org/wiki/Bor%C5%AFvka's_algorithm]'s algorithm, that needs to be filled.
--
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