Package org.jgrapht.alg.spanning

Class AbstractCapacitatedMinimumSpanningTree.CapacitatedSpanningTreeSolutionRepresentation

  • All Implemented Interfaces:
    java.lang.Cloneable
    Enclosing class:
    AbstractCapacitatedMinimumSpanningTree<V,​E>
    protected class AbstractCapacitatedMinimumSpanningTree.CapacitatedSpanningTreeSolutionRepresentation
extends java.lang.Object
implements java.lang.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.

    • Method Summary

      All Methods Instance Methods Concrete Methods 
      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.
      java.util.Set<java.lang.Integer> getLabels()
      Returns all labels of all subsets.
      int getNextFreeLabel()
      Returns the next free label in the label map respectively partition
      java.util.Set<V> getPartitionSet​(java.lang.Integer label)
      Returns the set of vertices that are in the subset with label label.
      double getPartitionWeight​(java.lang.Integer label)
      Returns the sum of the weights of all vertices that are in the subset with label label.
      void moveVertex​(V vertex, java.lang.Integer fromLabel, java.lang.Integer toLabel)
      Moves vertex from the subset represented by fromLabel to the subset represented by toLabel.
      void moveVertices​(java.util.Set<V> vertices, java.lang.Integer fromLabel, java.lang.Integer toLabel)
      Moves all vertices in vertices from the subset represented by fromLabel to the subset represented by toLabel.
      java.util.Set<java.lang.Integer> partitionSubtreesOfSubset​(java.util.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​(java.util.Map<V,​java.lang.Integer> labels,
                                                     java.util.Map<java.lang.Integer,​Pair<java.util.Set<V>,​java.lang.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,
                       java.lang.Integer fromLabel,
                       java.lang.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​(java.util.Set<V> vertices,
                         java.lang.Integer fromLabel,
                         java.lang.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 java.util.Set<java.lang.Integer> partitionSubtreesOfSubset​(java.util.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 java.util.Set<java.lang.Integer> getLabels()
        Returns all labels of all subsets.
        Returns:
        the labels of all subsets

      • getPartitionSet

        public java.util.Set<V> getPartitionSet​(java.lang.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​(java.lang.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