Package com.jgalgo.alg

Interface MinimumDirectedSpanningTree

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. A builder obtained via newBuilder() may support different options to obtain different implementations.

Author:

Barak Ugav

Nested Class Summary

Nested Classes

Modifier and Type	Interface	Description
static interface	MinimumDirectedSpanningTree.Builder	A builder for MinimumDirectedSpanningTree objects.

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.Builder	newBuilder()	Create a new minimum directed spanning tree algorithm builder.
static MinimumDirectedSpanningTree	newInstance()	Create a new directed-MST algorithm object.

Method Detail

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. The MinimumDirectedSpanningTree.Builder might support different options to obtain different implementations.

Returns:

a default implementation of MinimumDirectedSpanningTree

newBuilder

static MinimumDirectedSpanningTree.Builder newBuilder()

Create a new minimum directed spanning tree algorithm builder.

Use newInstance() for a default implementation.

Returns:

a new builder that can build MinimumDirectedSpanningTree objects