CapacitatedSpanningTreeAlgorithm (JGraphT : a free Java graph library)

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	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

All Methods Instance Methods Abstract Methods
Modifier and Type	Method	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