Package org.drip.graph.mstgreedy

Class BoruvkaForest<V>

java.lang.Object

org.drip.graph.core.Forest<V>

org.drip.graph.mstgreedy.KruskalForest<V>

org.drip.graph.mstgreedy.BoruvkaForest<V>

public class BoruvkaForest<V>
extends KruskalForest<V>

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, Directed<?> graph, boolean descending)	Add a Named Tree to the Forest
boolean	conditionalBoruvkaMerge(Directed<?> graph, boolean maximum)	Perform a Conditional Boruvka Merge Using the Graph
boolean	unitVertexTree(java.lang.String vertexName, Directed<?> 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,
Directed<?> graph)

Create and add a Unit Vertex Tree into the Forest

Overrides:

unitVertexTree in class Forest<V>

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,
Directed<?> 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(Directed<?> 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