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