Package com.jgalgo.alg.span

Class MinimumDirectedSpanningTreeAbstract

java.lang.Object

com.jgalgo.alg.span.MinimumDirectedSpanningTreeAbstract

All Implemented Interfaces:

MinimumDirectedSpanningTree

Direct Known Subclasses:

MinimumDirectedSpanningTreeTarjan

public abstract class MinimumDirectedSpanningTreeAbstract
extends Object
implements MinimumDirectedSpanningTree

Abstract class for computing minimum spanning trees in directed 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

Constructor Summary

Constructors

Constructor	Description
MinimumDirectedSpanningTreeAbstract()	Default constructor.

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.

Methods inherited from class java.lang.Object

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

Constructor Details

MinimumDirectedSpanningTreeAbstract

public MinimumDirectedSpanningTreeAbstract()

Default constructor.

Method Details

computeMinimumDirectedSpanningTree

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

Description copied from interface: MinimumDirectedSpanningTree

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.

Specified by:

computeMinimumDirectedSpanningTree in interface MinimumDirectedSpanningTree

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