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

Modifier and Type	Method	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

See Also:

Object.clone()