Package org.drip.graph.treebuilder

Class OptimalSpanningForestGenerator

java.lang.Object
org.drip.graph.treebuilder.OptimalSpanningForestGenerator
Direct Known Subclasses:
BoruvkaGenerator, CapacitatedMSTGenerator, DegreeConstrainedMSTGenerator, DirectedGraphMSTGenerator, DynamicMSTGenerator, EuclideanMSTGenerator, KMSTGenerator, KruskalGenerator, OptimalBottleneckSpanningTreeGenerator, OptimalLabelingSpanningTreeGenerator, PrimGenerator, RectilinearMSTGenerator, ReverseDeleteGenerator, SteinerTreeGenerator
public abstract class OptimalSpanningForestGenerator
extends java.lang.Object
OptimalSpanningForestGenerator exposes the Algorithmic Implementation for the Generation of the Minimum/Maximum Spanning Forest. The References are:

  • Grama, A., A. Gupta, G. Karypis, and V. Kumar (2003): Introduction to Parallel Computing 2nd Edition Addison Wesley
  • Kepner, J., and J. Gilbert (2011): Graph Algorithms in the Language of Linear Algebra Society for Industrial and Applied Mathematics
  • Pettie, S., and V. Ramachandran (2002): An Optimal Minimum Spanning Tree Algorithm Journal of the ACM 49 (1) 16-34
  • Sedgewick, R. E., and K. D. Wayne (2011): Algorithms 4th Edition Addison-Wesley
  • Setia, R., A. Nedunchezhian, and S. Balachandran (2015): A New Parallel Algorithm for Minimum Spanning Tree Problem https://hipcor.fatcow.com/hipc2009/documents/HIPCSS09Papers/1569250351.pdf
  • Wikipedia (2019): Prim's Algorithm https://en.wikipedia.org/wiki/Prim%27s_algorithm




Author:
Lakshmi Krishnamurthy

  • Method Summary

    Modifier and Type Method Description
    DirectedGraph graph()
    Retrieve the Graph
    boolean maximum()
    Indicate if the Forest contains Minimum or Maximum Spanning Trees
    abstract Forest optimalSpanningForest()
    Generate the Optimal Spanning Forest

    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 Trees
      Returns:
      TRUE - The Forest contains Maximum Spanning Trees

    • optimalSpanningForest

      public abstract Forest optimalSpanningForest()
      Generate the Optimal Spanning Forest
      Returns:
      Optimal Spanning Forest