BoruvkaForest

java.lang.Object

org.drip.graph.core.Forest

org.drip.graph.mstgreedy.KruskalForest

org.drip.graph.mstgreedy.BoruvkaForest

public class BoruvkaForest
extends KruskalForest

BoruvkaForest implements the Extensions to a Forest required by the Boruvka MSF Generator. The References are:

Bollobas, B. (1998): Modern Graph Theory Springer
Eppstein, D. (1999): Spanning Trees and Spanners https://www.ics.uci.edu/~eppstein/pubs/Epp-TR-96-16.pdf
Gross, J. L., and J. Yellen (2005): Graph Theory and its Applications Springer
Kocay, W., and D. L. Kreher (2004): Graphs, Algorithms, and Optimizations CRC Press
Wikipedia (2020): Spanning Tree https://en.wikipedia.org/wiki/Spanning_tree

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

BoruvkaForest(boolean minHeap)
BoruvkaForest Constructor

Method Summary

Modifier and Type	Method	Description
`boolean`	`addTree(java.lang.String treeName, Tree tree, DirectedGraph graph, boolean descending)`	Add a Named Tree to the Forest
`boolean`	`conditionalBoruvkaMerge(DirectedGraph graph, boolean maximum)`	Perform a Conditional Boruvka Merge Using the Graph
`boolean`	`unitVertexTree(java.lang.String vertexName, DirectedGraph graph)`	Create and add a Unit Vertex Tree into the Forest

Methods inherited from class org.drip.graph.core.Forest

addTree, conditionalMerge, containingTree, containingTreeNameMap, containsVertex, length, treeMap, treeNameSet, vertexSet

Methods inherited from class java.lang.Object

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

Constructor Details
- BoruvkaForest
  
  public BoruvkaForest(boolean minHeap)
  
  BoruvkaForest Constructor
  
  Parameters:
  
  minHeap - TRUE - Minimum Heap
Method Details
- unitVertexTree
  
  public boolean unitVertexTree(java.lang.String vertexName, DirectedGraph graph)
  
  Create and add a Unit Vertex Tree into the Forest
  
  Overrides:
  
  unitVertexTree in class Forest
  
  Parameters:
  
  vertexName - Vertex Name
  
  graph - Parent Graph
  
  Returns:
  
  TRUE - The Unit Vertex Tree successfully added into the Forest
- addTree
  
  public boolean addTree(java.lang.String treeName, Tree tree, DirectedGraph graph, boolean descending)
  
  Add a Named Tree to the Forest
  
  Parameters:
  
  treeName - The Tree Name
  
  tree - The Tree
  
  graph - The Graph
  
  descending - Tree Neighbor Set in Descending Order
  
  Returns:
  
  TRUE - The Keyed Tree successfully added to the Forest
- conditionalBoruvkaMerge
  
  public boolean conditionalBoruvkaMerge(DirectedGraph graph, boolean maximum)
  
  Perform a Conditional Boruvka Merge Using the Graph
  
  Parameters:
  
  graph - The Graph
  
  maximum - TRUE - The Maximum Spanning Forest is to be generated
  
  Returns:
  
  TRUE - The Boruvka Merge finished successfully