Package com.jgalgo.alg.span

Interface MinimumDirectedSpanningTree

All Known Implementing Classes:

MinimumDirectedSpanningTreeAbstract, MinimumDirectedSpanningTreeTarjan

public interface MinimumDirectedSpanningTree

Minimum spanning tree algorithm for directed graphs.

A spanning tree in directed graph is defined similarly to a spanning tree in undirected graph, but the 'spanning tree' does not yield a strongly connected graph, rather a tree in which all the vertices are reachable from the root. Note that differing from the undirected MinimumSpanningTree, the root is given as part of the input, and the result spanning tree will span only the vertices reachable from the root with a single tree, and not a forest.

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

Author:

Barak Ugav

Method Summary

Modifier and Type	Method	Description
<V, E> MinimumSpanningTree.Result<V,E>	computeMinimumDirectedSpanningTree(Graph<V,E> g, WeightFunction<E> w, V root)	Compute a minimum directed spanning tree (MDST) in a directed graph, rooted at the given vertex.
static MinimumDirectedSpanningTree	newInstance()	Create a new directed-MST algorithm object.

Method Details

computeMinimumDirectedSpanningTree

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

Compute a minimum directed spanning tree (MDST) in a directed graph, rooted at the given vertex.

Note that the returned spanning tree is a single tree that span only the vertices reachable from the root, and not a forest that span the whole 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 directed graph

w - an edge weight function

root - vertex in the graph the spanning tree will be rooted from

Returns:

all edges composing the spanning tree

Throws:

IllegalArgumentException - if g is not directed

newInstance

static MinimumDirectedSpanningTree newInstance()

Create a new directed-MST algorithm object.

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

Returns:

a default implementation of MinimumDirectedSpanningTree