org.jgrapht.alg.interfaces

Interface CapacitatedSpanningTreeAlgorithm<V,E>

Type Parameters:

V - the graph vertex type

E - the graph edge type

All Known Implementing Classes:

AbstractCapacitatedMinimumSpanningTree, AhujaOrlinSharmaCapacitatedMinimumSpanningTree, EsauWilliamsCapacitatedMinimumSpanningTree

public interface CapacitatedSpanningTreeAlgorithm<V,E>

An algorithm which computes a capacitated (minimum) spanning tree of a given connected graph with a designated root vertex. The input is a connected undirected graph G = (V, E) with a designated root r \in V, a capacity constraint K \in \mathbb{N}, a demand function d: V \rightarrow \mathbb{N} and a capacity function c: E \rightarrow \mathbb{N}. A Capacitated Minimum Spanning Tree (CMST) is a rooted minimal cost spanning tree that satisfies the capacity constraint on all trees that are connected to the designated root. That is, the sum of the demands of all vertices is smaller or equal than K. These trees build up a partition on the vertex set of the graph. The problem is NP-hard.

Nested Class Summary

Nested Classes

Modifier and Type	Interface and Description
static interface	CapacitatedSpanningTreeAlgorithm.CapacitatedSpanningTree<V,E> A spanning tree.
static class	CapacitatedSpanningTreeAlgorithm.CapacitatedSpanningTreeImpl<V,E> Default implementation of the spanning tree interface.

Method Summary

Modifier and Type	Method and Description
CapacitatedSpanningTreeAlgorithm.CapacitatedSpanningTree<V,E>	getCapacitatedSpanningTree() Computes a capacitated spanning tree.

Method Detail

getCapacitatedSpanningTree

CapacitatedSpanningTreeAlgorithm.CapacitatedSpanningTree<V,E> getCapacitatedSpanningTree()

Computes a capacitated spanning tree.

Returns:

a capacitated spanning tree