org.jgrapht.alg.spanning

## Class AbstractCapacitatedMinimumSpanningTree.CapacitatedSpanningTreeSolutionRepresentation

• java.lang.Object
• org.jgrapht.alg.spanning.AbstractCapacitatedMinimumSpanningTree.CapacitatedSpanningTreeSolutionRepresentation
• All Implemented Interfaces:
Cloneable
Enclosing class:
AbstractCapacitatedMinimumSpanningTree<V,E>

protected class AbstractCapacitatedMinimumSpanningTree.CapacitatedSpanningTreeSolutionRepresentation
extends Object
implements Cloneable
This class represents a solution instance by managing the labels and the partition mapping. With the help of this class, a capacitated spanning tree based on the label and partition mapping can be calculated.
• ### Constructor Summary

Constructors
Constructor and Description
CapacitatedSpanningTreeSolutionRepresentation()
Constructs a new solution representation for the CMST problem.
CapacitatedSpanningTreeSolutionRepresentation(Map<V,Integer> labels, Map<Integer,Pair<Set<V>,Double>> partition)
Constructs a new solution representation for the CMST problem based on labels and partition.
• ### Method Summary

All Methods
Modifier and Type Method and Description
CapacitatedSpanningTreeAlgorithm.CapacitatedSpanningTree<V,E> calculateResultingSpanningTree()
Calculates the resulting spanning tree based on this solution representation.
void cleanUp()
Cleans up the solution representation by removing all empty sets from the partition.
AbstractCapacitatedMinimumSpanningTree.CapacitatedSpanningTreeSolutionRepresentation clone()
Returns a shallow copy of this solution representation instance.
int getLabel(V vertex)
Returns the label of the subset that contains vertex.
Set<Integer> getLabels()
Returns all labels of all subsets.
int getNextFreeLabel()
Returns the next free label in the label map respectively partition
Set<V> getPartitionSet(Integer label)
Returns the set of vertices that are in the subset with label label.
double getPartitionWeight(Integer label)
Returns the sum of the weights of all vertices that are in the subset with label label.
void moveVertex(V vertex, Integer fromLabel, Integer toLabel)
Moves vertex from the subset represented by fromLabel to the subset represented by toLabel.
void moveVertices(Set<V> vertices, Integer fromLabel, Integer toLabel)
Moves all vertices in vertices from the subset represented by fromLabel to the subset represented by toLabel.
Set<Integer> partitionSubtreesOfSubset(Set<V> vertexSubset, int label)
Refines the partition by adding new subsets if the designated root has more than one subtree in the subset label of the partition.
• ### Methods inherited from class java.lang.Object

equals, finalize, getClass, hashCode, notify, notifyAll, toString, wait, wait, wait
• ### Constructor Detail

• #### CapacitatedSpanningTreeSolutionRepresentation

public CapacitatedSpanningTreeSolutionRepresentation()
Constructs a new solution representation for the CMST problem.
• #### CapacitatedSpanningTreeSolutionRepresentation

public CapacitatedSpanningTreeSolutionRepresentation(Map<V,Integer> labels,
Map<Integer,Pair<Set<V>,Double>> partition)
Constructs a new solution representation for the CMST problem based on labels and partition. All labels have to be positive.
Parameters:
labels - the labels of the subsets in the partition
partition - the partition map
• ### Method Detail

• #### calculateResultingSpanningTree

public CapacitatedSpanningTreeAlgorithm.CapacitatedSpanningTree<V,E> calculateResultingSpanningTree()
Calculates the resulting spanning tree based on this solution representation.
Returns:
the resulting spanning tree based on this solution representation
• #### moveVertex

public void moveVertex(V vertex,
Integer fromLabel,
Integer toLabel)
Moves vertex from the subset represented by fromLabel to the subset represented by toLabel.
Parameters:
vertex - the vertex to move
fromLabel - the subset to move the vertex from
toLabel - the subset to move the vertex to
• #### moveVertices

public void moveVertices(Set<V> vertices,
Integer fromLabel,
Integer toLabel)
Moves all vertices in vertices from the subset represented by fromLabel to the subset represented by toLabel.
Parameters:
vertices - the vertices to move
fromLabel - the subset to move the vertices from
toLabel - the subset to move the vertices to
• #### partitionSubtreesOfSubset

public Set<Integer> partitionSubtreesOfSubset(Set<V> vertexSubset,
int label)
Refines the partition by adding new subsets if the designated root has more than one subtree in the subset label of the partition.
Parameters:
vertexSubset - the subset represented by label, that is the subset that has to be refined
label - the label of the subset of the partition that were refined
Returns:
the set of all labels of subsets that were changed during the refinement
• #### cleanUp

public void cleanUp()
Cleans up the solution representation by removing all empty sets from the partition.
• #### getNextFreeLabel

public int getNextFreeLabel()
Returns the next free label in the label map respectively partition
Returns:
the next free label in the label map respectively partition
• #### getLabel

public int getLabel(V vertex)
Returns the label of the subset that contains vertex.
Parameters:
vertex - the vertex to return the label from
Returns:
the label of vertex
• #### getLabels

public Set<Integer> getLabels()
Returns all labels of all subsets.
Returns:
the labels of all subsets
• #### getPartitionSet

public Set<V> getPartitionSet(Integer label)
Returns the set of vertices that are in the subset with label label.
Parameters:
label - the label of the subset to return the vertices from
Returns:
the set of vertices that are in the subset with label label
• #### getPartitionWeight

public double getPartitionWeight(Integer label)
Returns the sum of the weights of all vertices that are in the subset with label label.
Parameters:
label - the label of the subset to return the weight from
Returns:
the sum of the weights of all vertices that are in the subset with label label
• #### clone

public AbstractCapacitatedMinimumSpanningTree.CapacitatedSpanningTreeSolutionRepresentation clone()
Returns a shallow copy of this solution representation instance. Vertices are not cloned.
Overrides:
clone in class Object
Returns:
a shallow copy of this solution representation.
Throws:
RuntimeException - in case the clone is not supported
Object.clone()