org.jgrapht.alg.spanning

Class AbstractCapacitatedMinimumSpanningTree<V,E>

java.lang.Object

org.jgrapht.alg.spanning.AbstractCapacitatedMinimumSpanningTree<V,E>

Type Parameters:

V - the vertex type

E - the edge type

All Implemented Interfaces:

CapacitatedSpanningTreeAlgorithm<V,E>

Direct Known Subclasses:

AhujaOrlinSharmaCapacitatedMinimumSpanningTree, EsauWilliamsCapacitatedMinimumSpanningTree

public abstract class AbstractCapacitatedMinimumSpanningTree<V,E>
extends 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 and 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 and Description
protected AbstractCapacitatedMinimumSpanningTree.CapacitatedSpanningTreeSolutionRepresentation	bestSolution representation of the solution
protected double	capacity the maximal capacity for each subtree.
protected Map<V,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

Constructors

Modifier	Constructor and Description
protected	AbstractCapacitatedMinimumSpanningTree(Graph<V,E> graph, V root, double capacity, Map<V,Double> demands) Construct a new abstract capacitated minimum spanning tree algorithm.

Method Summary

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

Methods inherited from class java.lang.Object

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

Field Detail

graph

protected final Graph<V,E> graph

the input graph.

root

protected final V root

the designated root of the CMST.

capacity

protected final double capacity

the maximal capacity for each subtree.

demands

protected final Map<V,Double> demands

the demand function over all vertices.

bestSolution

protected AbstractCapacitatedMinimumSpanningTree.CapacitatedSpanningTreeSolutionRepresentation bestSolution

representation of the solution

Constructor Detail

AbstractCapacitatedMinimumSpanningTree

protected AbstractCapacitatedMinimumSpanningTree(Graph<V,E> graph,
                                                 V root,
                                                 double capacity,
                                                 Map<V,Double> demands)

Construct a new abstract capacitated minimum spanning tree algorithm.

Parameters:

graph - the base graph to calculate the capacitated spanning tree for

root - the root of the capacitated spanning tree

capacity - the edge capacity constraint

demands - the demands of the vertices

Method Detail

getCapacitatedSpanningTree

public abstract CapacitatedSpanningTreeAlgorithm.CapacitatedSpanningTree<V,E> getCapacitatedSpanningTree()

Description copied from interface: CapacitatedSpanningTreeAlgorithm

Computes a capacitated spanning tree.

Specified by:

getCapacitatedSpanningTree in interface CapacitatedSpanningTreeAlgorithm<V,E>

Returns:

a capacitated spanning tree