Package org.graph4j.spanning

Class BoruvkaMinimumSpanningTreeParallel

java.lang.Object

org.graph4j.GraphAlgorithm

org.graph4j.spanning.MinimumSpanningTreeBase

org.graph4j.spanning.BoruvkaMinimumSpanningTreeBase

org.graph4j.spanning.BoruvkaMinimumSpanningTreeParallel

All Implemented Interfaces:

MinimumSpanningTreeAlgorithm

public class BoruvkaMinimumSpanningTreeParallel
extends BoruvkaMinimumSpanningTreeBase

Parallel implementation of the Boruvka algorithm for finding a minimum spanning tree. You can see more : https://web.archive.org/web/20110410100229id_/http://www.globalstf.org:80/docs/proceedings/adpc/ADPC_22.pdf SECTION 5 - EXPERIMENTS

Author:

Sorodoc Cosmin

Field Summary

Fields inherited from class org.graph4j.spanning.BoruvkaMinimumSpanningTreeBase

cheapest, 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
BoruvkaMinimumSpanningTreeParallel(Graph graph)
BoruvkaMinimumSpanningTreeParallel(Graph graph, int nrThreads)

Method Summary

Modifier and Type	Method	Description
protected void	compute()
protected 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

Constructor Details

BoruvkaMinimumSpanningTreeParallel

public BoruvkaMinimumSpanningTreeParallel(Graph graph)

BoruvkaMinimumSpanningTreeParallel

public BoruvkaMinimumSpanningTreeParallel(Graph graph,
 int nrThreads)

Parameters:

graph - the input graph.

nrThreads - the number of threads.

Method Details

compute

protected void compute()

Overrides:

compute in class BoruvkaMinimumSpanningTreeBase

updateCheapestEdges

protected boolean updateCheapestEdges()

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

Specified by:

updateCheapestEdges in class BoruvkaMinimumSpanningTreeBase

Returns:

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