Module org.jgrapht.core
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 Details

    • 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 Details

    • 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<V,E>.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: