Package com.jgalgo.alg.span

Class SteinerTreeAlgoAbstract

java.lang.Object

com.jgalgo.alg.span.SteinerTreeAlgoAbstract

All Implemented Interfaces:

SteinerTreeAlgo

Direct Known Subclasses:

SteinerTreeMehlhorn

public abstract class SteinerTreeAlgoAbstract
extends Object
implements SteinerTreeAlgo

Abstract class for computing Steiner trees in 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.SteinerTreeAlgo

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

Constructor Summary

Constructors

Constructor	Description
SteinerTreeAlgoAbstract()	Default constructor.

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.

Methods inherited from class java.lang.Object

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

Constructor Details

SteinerTreeAlgoAbstract

public SteinerTreeAlgoAbstract()

Default constructor.

Method Details

computeSteinerTree

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

Description copied from interface: SteinerTreeAlgo

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.

Specified by:

computeSteinerTree in interface SteinerTreeAlgo

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