You are viewing a plain text version of this content. The canonical link for it is here.
Posted to issues@commons.apache.org by "Thomas Neidhart (Updated) (JIRA)" <ji...@apache.org> on 2012/02/05 23:23:59 UTC
[jira] [Updated] (SANDBOX-348) Implement the Boruvka's algorithm
[ 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