Package org.drip.graph.mstgreedy

Class BoruvkaGenerator

java.lang.Object
org.drip.graph.treebuilder.OptimalSpanningForestGenerator
org.drip.graph.mstgreedy.BoruvkaGenerator
public class BoruvkaGenerator
extends OptimalSpanningForestGenerator
BoruvkaGenerator implements the Boruvka Algorithm for generating a Minimum Spanning Tree. The References are:

  • Bader, D. A., and G. Cong (2006): Fast Shared Memory Algorithms for computing the Minimum Spanning Forests of Sparse Graphs Journal of Parallel and Distributed Computing 66 (11) 1366-1378
  • Chazelle, B. (2000): A Minimum Spanning Tree ALgorithm with Inverse-Ackerman Type Complexity Journal of the Association for Computing Machinery 47 (6) 1028-1047
  • Karger, D. R., P. N. Klein, and R. E. Tarjan (1995): A Randomized Linear-Time Algorithm to find Minimum Spanning Trees Journal of the Association for Computing Machinery 42 (2) 321-328
  • Mares, M. (2004): Two Linear-Time Algorithms for MSTon Minor Closed Graph Classes Activium Mathematicum 40 (3) 315-320
  • Wikipedia (2019): Boruvka's Algorithm https://en.wikipedia.org/wiki/Bor%C5%AFvka's_algorithm




Author:
Lakshmi Krishnamurthy

  • Constructor Summary

    Constructors
    Constructor Description
    BoruvkaGenerator​(DirectedGraph graph, boolean maximum)
    BoruvkaGenerator Constructor

  • Method Summary

    Modifier and Type Method Description
    Forest optimalSpanningForest()
    Generate the Optimal Spanning Forest

    Methods inherited from class org.drip.graph.treebuilder.OptimalSpanningForestGenerator

    graph, maximum

    Methods inherited from class java.lang.Object

    equals, getClass, hashCode, notify, notifyAll, toString, wait, wait, wait

  • Constructor Details

    • BoruvkaGenerator

      public BoruvkaGenerator​(DirectedGraph graph, boolean maximum) throws java.lang.Exception
      BoruvkaGenerator Constructor
      Parameters:
      graph - The Graph
      maximum - TRUE - The Maximum Spanning Forest is to be generated
      Throws:
      java.lang.Exception - Thrown if the Inputs are Invalid

  • Method Details