Package org.graph4j.spanning

Class BoruvkaMinimumSpanningTreeBase

java.lang.Object

org.graph4j.GraphAlgorithm

org.graph4j.spanning.MinimumSpanningTreeBase

org.graph4j.spanning.BoruvkaMinimumSpanningTreeBase

All Implemented Interfaces:

MinimumSpanningTreeAlgorithm

Direct Known Subclasses:

BoruvkaMinimumSpanningTreeDefault, BoruvkaMinimumSpanningTreeParallel

public abstract class BoruvkaMinimumSpanningTreeBase
extends MinimumSpanningTreeBase

Base class for Boruvka's minimum spanning tree implementations.

Author:

Sorodoc Cosmin

Field Summary

Fields

Modifier and Type	Field	Description
protected final Edge[]	cheapest
protected final UnionFind	uf

Fields inherited from class org.graph4j.spanning.MinimumSpanningTreeBase

minWeight, tree, treeEdges

Fields inherited from class org.graph4j.GraphAlgorithm

directed, graph

Constructor Summary

Constructors

Constructor	Description
BoruvkaMinimumSpanningTreeBase(Graph graph)

Method Summary

Modifier and Type	Method	Description
protected void	compute()
protected abstract boolean	updateCheapestEdges()	For each component, find the smallest weighted edge and update the cheapest array

Methods inherited from class org.graph4j.spanning.MinimumSpanningTreeBase

getEdges, getTree, getWeight

Methods inherited from class org.graph4j.GraphAlgorithm

getGraph

Methods inherited from class java.lang.Object

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

Field Details

uf

protected final UnionFind uf

cheapest

protected final Edge[] cheapest

Constructor Details

BoruvkaMinimumSpanningTreeBase

public BoruvkaMinimumSpanningTreeBase(Graph graph)

Method Details

compute

protected void compute()

Specified by:

compute in class MinimumSpanningTreeBase

updateCheapestEdges

protected abstract boolean updateCheapestEdges()

For each component, find the smallest weighted edge and update the cheapest array

Returns:

true if there is at least one outgoing edge from the components, false otherwise