Package com.jgalgo.alg.span

Interface SteinerTreeAlgo

All Known Implementing Classes:

SteinerTreeAlgoAbstract, SteinerTreeMehlhorn

public interface SteinerTreeAlgo

An algorithm for the Steiner tree problem.

The Steiner tree problem is a generalization of the minimum spanning tree problem. Given a graph \(G=(V,E)\) and a set of terminals vertices \(T \subseteq V\), the Steiner tree problem is to find a minimum weight tree that spans all the terminals. The tree may contain additional vertices that are not terminals, which are usually called Steiner vertices. The Steiner tree problem is NP-hard, therefore algorithms implementing this interface are heuristics, and do not guarantee to find the optimal solution, only a solution with bounded approximation factor.

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

Author:

Barak Ugav

See Also:

Wikipedia, MinimumSpanningTree

Nested Class Summary

Nested Classes

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

Method Summary

Modifier and Type	Method	Description
<V,E> SteinerTreeAlgo.Result<V,E>	computeSteinerTree(Graph<V,E> g, WeightFunction<E> w, Collection<V> terminals)	Compute the minimum Steiner tree of a given graph.
static <V,E> boolean	isSteinerTree(Graph<V,E> g, Collection<V> terminals, Collection<E> edges)	Check whether a given set of edges is a valid Steiner tree for a given graph and terminals.
static SteinerTreeAlgo	newInstance()	Create a new Steiner tree algorithm object.

Method Detail

computeSteinerTree

<V,E> SteinerTreeAlgo.Result<V,E> computeSteinerTree(Graph<V,E> g,
                                                                 WeightFunction<E> w,
                                                                 Collection<V> terminals)

Compute the minimum Steiner tree of a given graph.

The algorithm with search for the minimum Steiner tree that spans all the terminals with respect to the given edge weight function. The tree may contain additional vertices that are not terminals.

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

Type Parameters:

V - the vertices type

E - the edges type

Parameters:

g - a graph

w - an edge weight function

terminals - a set of terminals vertices

Returns:

a result object containing all the edges of the computed tree

isSteinerTree

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

Check whether a given set of edges is a valid Steiner tree for a given graph and terminals.

A set of edges is a valid Steiner tree if it spans all the terminals, does not contain any cycles, form a single connected components, and there are no non-terminal leaves in the tree.

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

Type Parameters:

V - the vertices type

E - the edges type

Parameters:

g - a graph

terminals - a set of terminals vertices

edges - a set of edges

Returns:

true if the given set of edges is a valid Steiner tree

newInstance

static SteinerTreeAlgo newInstance()

Create a new Steiner tree algorithm object.

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

Returns:

a default implementation of SteinerTreeAlgo