Package org.jgrapht.alg.interfaces
Interface CapacitatedSpanningTreeAlgorithm<V,E>
-
- Type Parameters:
V
- the graph vertex typeE
- 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
-
-