PrimGenerator

java.lang.Object

org.drip.graph.treebuilder.OptimalSpanningForestGenerator

org.drip.graph.mstgreedy.PrimGenerator

public class PrimGenerator
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 2^nd 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 4^th 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

Module = Computational Core Module
Library = Graph Algorithm Library
Project = Graph Optimization and Tree Construction Algorithms
Package = Greedy Algorithms for MSTs and Forests

Author:: Lakshmi Krishnamurthy

Constructor Summary

Constructors

Constructor Description

PrimGenerator(DirectedGraph 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(DirectedGraph 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