Package com.jgalgo.alg.span

Interface MinimumSpanningTree

All Known Implementing Classes:

MinimumSpanningTreeAbstract, MinimumSpanningTreeBoruvka, MinimumSpanningTreeFredmanTarjan, MinimumSpanningTreeKargerKleinTarjan, MinimumSpanningTreeKruskal, MinimumSpanningTreePrim, MinimumSpanningTreeYao

public interface MinimumSpanningTree

Minimum spanning tree algorithm.

A spanning tree is an edge sub set of the graph edges which form a tree and connect (span) all the vertices of the graph. A minimum spanning tree (MST) is a spanning tree with the minimum edge weights sum over all spanning trees.

If a maximum spanning tree is needed, the edge weights can be negated and the MST algorithm can be used to compute the maximum spanning tree.

Use newInstance() to get a default implementation of this interface.

Author:

Barak Ugav

See Also:

Wikipedia, MinimumDirectedSpanningTree

Nested Class Summary

Nested Classes

Modifier and Type	Interface	Description
static interface	MinimumSpanningTree.IResult	A result object for MinimumSpanningTree computation for IntGraph.
static interface	MinimumSpanningTree.Result<V,E>	A result object for MinimumSpanningTree computation.

Method Summary

Modifier and Type	Method	Description
<V,E> MinimumSpanningTree.Result<V,E>	computeMinimumSpanningTree(Graph<V,E> g, WeightFunction<E> w)	Compute the minimum spanning tree (MST) of a given graph.
static <V,E> boolean	isSpanningForest(Graph<V,E> g, Collection<E> edges)	Check whether a given set of edges is a spanning forest of a given graph.
static <V,E> boolean	isSpanningTree(Graph<V,E> g, Collection<E> edges)	Check whether a given set of edges is a spanning tree of a given graph.
static MinimumSpanningTree	newInstance()	Create a new MST algorithm object.

Method Detail

computeMinimumSpanningTree

<V,E> MinimumSpanningTree.Result<V,E> computeMinimumSpanningTree(Graph<V,E> g,
                                                                             WeightFunction<E> w)

Compute the minimum spanning tree (MST) of a given graph.

If g is an IntGraph, a MinimumSpanningTree.IResult object will be returned. In that case, its better to pass a IWeightFunction as w to avoid boxing/unboxing.

Type Parameters:

V - the vertices type

E - the edges type

Parameters:

g - a graph

w - an edge weight function

Returns:

a result object containing all the edges of the computed spanning tree, which there are \(n-1\) of them (or less, forming a forest if the graph is not connected)

isSpanningTree

static <V,E> boolean isSpanningTree(Graph<V,E> g,
                                          Collection<E> edges)

Check whether a given set of edges is a spanning tree of a given graph.

A set of edges is spanning tree if it is a tree and connects all the vertices of the graph. Specifically, if the graph is not empty, the number of edges must be \(n-1\) where \(n\) denote the number of vertices in the graph. The edge set should not contain any duplicate edges.

If g is an IntGraph, its better to pass a IntCollection as edges to avoid boxing/unboxing.

Type Parameters:

V - the vertices type

E - the edges type

Parameters:

g - a graph

edges - a set of edges that should form a spanning tree

Returns:

true if the given set of edges is a spanning tree of the given graph, false otherwise

isSpanningForest

static <V,E> boolean isSpanningForest(Graph<V,E> g,
                                            Collection<E> edges)

Check whether a given set of edges is a spanning forest of a given graph.

A set of edges is spanning forest if it is a forest (do not contains cycles) which connected any pair of vertices that are connected in the original graph, namely its connected components are identical to the connected components of the original graph. Specifically, the number of edges must be \(n-c\) where \(n\) denote the number of vertices in the graph and \(c\) denote the number of connected components in the graph. The edge set should not contain any duplicate edges.

Type Parameters:

V - the vertices type

E - the edges type

Parameters:

g - a graph

edges - a set of edges that should form a spanning forest

Returns:

true if the given set of edges is a spanning forest of the given graph, false otherwise

newInstance

static MinimumSpanningTree newInstance()

Create a new MST algorithm object.

This is the recommended way to instantiate a new MinimumSpanningTree object.

Returns:

a default implementation of MinimumSpanningTree