commons-issues mailing list archives

Site index · List index
Message view « Date » · « Thread »
Top « Date » · « Thread »
From "Thomas Neidhart (Commented) (JIRA)" <j...@apache.org>
Subject [jira] [Commented] (SANDBOX-348) Implement the Boruvka's algorithm
Date Tue, 31 Jan 2012 20:16:11 GMT

    [ 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

        

Mime
View raw message