Package org.drip.graph.mstgreedy

Class PrimGenerator<V>

java.lang.Object
org.drip.graph.treebuilder.OptimalSpanningForestGenerator
org.drip.graph.mstgreedy.PrimGenerator<V>
public class PrimGenerator<V>
extends OptimalSpanningForestGenerator
PrimGenerator implements the Prim's Algorithm for generating a Minimum Spanning Tree. 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

  • Constructor Summary

    Constructors
    Constructor Description
    PrimGenerator​(Directed<?> graph, boolean maximum)
    PrimGenerator Constructor

  • Method Summary

    Modifier and Type Method Description
    Forest<?> minimumSpanningForest​(java.lang.String initialVertexName)
    Generate the Minimum Spanning Forest from the specified Initial Vertex
    Tree<?> minimumSpanningTree​(java.lang.String initialVertexName)
    Generate the Minimum Spanning Tree from the Initial Vertex
    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

    • PrimGenerator

      public PrimGenerator​(Directed<?> graph, boolean maximum) throws java.lang.Exception
      PrimGenerator 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

    • minimumSpanningTree

      public Tree<?> minimumSpanningTree​(java.lang.String initialVertexName)
      Generate the Minimum Spanning Tree from the Initial Vertex
      Parameters:
      initialVertexName - The Initial Vertex Name
      Returns:
      The Minimum Spanning Tree

    • minimumSpanningForest

      public Forest<?> minimumSpanningForest​(java.lang.String initialVertexName)
      Generate the Minimum Spanning Forest from the specified Initial Vertex
      Parameters:
      initialVertexName - Initial Vertex Name
      Returns:
      The Minimum Spanning Forest

    • optimalSpanningForest

      public Forest<?> optimalSpanningForest()
      Description copied from class: OptimalSpanningForestGenerator
      Generate the Optimal Spanning Forest
      Specified by:
      optimalSpanningForest in class OptimalSpanningForestGenerator
      Returns:
      Optimal Spanning Forest