Package org.drip.graph.treebuilder

Class KOptimalSpanningForestsGenerator

java.lang.Object
org.drip.graph.treebuilder.KOptimalSpanningForestsGenerator
public abstract class KOptimalSpanningForestsGenerator
extends java.lang.Object
KOptimalSpanningForestsGenerator exposes the Functionality behind generating the k Smallest/Largest Spanning Forests for a given Graph and a k. 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
  • Pettie, S., and V. Ramachandran (2002): An Optimal Minimum Spanning Tree Algorithm Journal of the ACM 49 (1) 16-34
  • Wikipedia (2020): Minimum Spanning Tree https://en.wikipedia.org/wiki/Minimum_spanning_tree




Author:
Lakshmi Krishnamurthy

  • Method Summary

    Modifier and Type Method Description
    DirectedGraph graph()
    Retrieve the Graph
    int k()
    Retrieve the Tree Count k
    boolean maximum()
    Indicate if the Forest contains Minimum or Maximum Spanning Forests
    abstract java.util.List<Forest> smallestSpanningForestList()
    Generate the List of the Smallest Spanning Forests

    Methods inherited from class java.lang.Object

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

  • Method Details

    • graph

      public DirectedGraph graph()
      Retrieve the Graph
      Returns:
      The Graph

    • maximum

      public boolean maximum()
      Indicate if the Forest contains Minimum or Maximum Spanning Forests
      Returns:
      TRUE - The Forest contains Maximum Spanning Forests

    • k

      public int k()
      Retrieve the Tree Count k
      Returns:
      The Tree Count k

    • smallestSpanningForestList

      public abstract java.util.List<Forest> smallestSpanningForestList()
      Generate the List of the Smallest Spanning Forests
      Returns:
      List of the Smallest Spanning Forests