Module org.jgrapht.core
Package org.jgrapht.alg.spanning
Class AbstractCapacitatedMinimumSpanningTree<V,E>
java.lang.Object
org.jgrapht.alg.spanning.AbstractCapacitatedMinimumSpanningTree<V,E>
- Type Parameters:
V
- the vertex typeE
- the edge type
- All Implemented Interfaces:
CapacitatedSpanningTreeAlgorithm<V,E>
- Direct Known Subclasses:
AhujaOrlinSharmaCapacitatedMinimumSpanningTree
,EsauWilliamsCapacitatedMinimumSpanningTree
public abstract class AbstractCapacitatedMinimumSpanningTree<V,E> extends java.lang.Object implements CapacitatedSpanningTreeAlgorithm<V,E>
This is an abstract class for capacitated minimum spanning tree algorithms. This class manages
the basic instance information and a solution representation {see
CapacitatedSpanningTreeSolutionRepresentation} for a capacitated spanning tree.
- Since:
- July 18, 2018
- Author:
- Christoph GrĂ¼ne
-
Nested Class Summary
Nested Classes Modifier and Type Class Description protected class
AbstractCapacitatedMinimumSpanningTree.CapacitatedSpanningTreeSolutionRepresentation
This class represents a solution instance by managing the labels and the partition mapping.Nested classes/interfaces inherited from interface org.jgrapht.alg.interfaces.CapacitatedSpanningTreeAlgorithm
CapacitatedSpanningTreeAlgorithm.CapacitatedSpanningTree<V,E>, CapacitatedSpanningTreeAlgorithm.CapacitatedSpanningTreeImpl<V,E>
-
Field Summary
Fields Modifier and Type Field Description protected AbstractCapacitatedMinimumSpanningTree.CapacitatedSpanningTreeSolutionRepresentation
bestSolution
representation of the solutionprotected double
capacity
the maximal capacity for each subtree.protected java.util.Map<V,java.lang.Double>
demands
the demand function over all vertices.protected Graph<V,E>
graph
the input graph.protected V
root
the designated root of the CMST. -
Constructor Summary
-
Method Summary
Modifier and Type Method Description abstract CapacitatedSpanningTreeAlgorithm.CapacitatedSpanningTree<V,E>
getCapacitatedSpanningTree()
Computes a capacitated spanning tree.
-
Field Details
-
graph
the input graph. -
root
the designated root of the CMST. -
capacity
protected final double capacitythe maximal capacity for each subtree. -
demands
the demand function over all vertices. -
bestSolution
protected AbstractCapacitatedMinimumSpanningTree.CapacitatedSpanningTreeSolutionRepresentation bestSolutionrepresentation of the solution
-
-
Constructor Details
-
AbstractCapacitatedMinimumSpanningTree
protected AbstractCapacitatedMinimumSpanningTree(Graph<V,E> graph, V root, double capacity, java.util.Map<V,java.lang.Double> demands)Construct a new abstract capacitated minimum spanning tree algorithm.- Parameters:
graph
- the base graph to calculate the capacitated spanning tree forroot
- the root of the capacitated spanning treecapacity
- the edge capacity constraintdemands
- the demands of the vertices
-
-
Method Details
-
getCapacitatedSpanningTree
public abstract CapacitatedSpanningTreeAlgorithm.CapacitatedSpanningTree<V,E> getCapacitatedSpanningTree()Description copied from interface:CapacitatedSpanningTreeAlgorithm
Computes a capacitated spanning tree.- Specified by:
getCapacitatedSpanningTree
in interfaceCapacitatedSpanningTreeAlgorithm<V,E>
- Returns:
- a capacitated spanning tree
-