Package com.jgalgo.alg.span

Class MinimumSpanningTreeAbstract

java.lang.Object

com.jgalgo.alg.span.MinimumSpanningTreeAbstract

All Implemented Interfaces:

MinimumSpanningTree

Direct Known Subclasses:

MinimumSpanningTreeBoruvka, MinimumSpanningTreeFredmanTarjan, MinimumSpanningTreeKargerKleinTarjan, MinimumSpanningTreeKruskal, MinimumSpanningTreePrim, MinimumSpanningTreeYao

public abstract class MinimumSpanningTreeAbstract
extends Object
implements MinimumSpanningTree

Abstract class for computing a minimum spanning trees in undirected graphs.

The class implements the interface by solving the problem on the index graph and then maps the results back to the original graph. The implementation for index graphs is abstract and left to the subclasses.

Author:

Barak Ugav

Nested Class Summary

Nested classes/interfaces inherited from interface com.jgalgo.alg.span.MinimumSpanningTree

MinimumSpanningTree.IResult, MinimumSpanningTree.Result<V,E>

Constructor Summary

Constructors

Constructor	Description
MinimumSpanningTreeAbstract()	Default constructor.

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.

Methods inherited from class java.lang.Object

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

Constructor Details

MinimumSpanningTreeAbstract

public MinimumSpanningTreeAbstract()

Default constructor.

Method Details

computeMinimumSpanningTree

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

Description copied from interface: MinimumSpanningTree

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.

Specified by:

computeMinimumSpanningTree in interface MinimumSpanningTree

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)