Spanning tree and spanner algorithms.
-
mapping form all improvement graph vertices to their labels corresponding to the base
graph for the CMST problem
AhujaOrlinSharmaCapacitatedMinimumSpanningTree.ImprovementGraph.improvementGraph
the improvement graph itself
AhujaOrlinSharmaCapacitatedMinimumSpanningTree.ImprovementGraph.origin
mapping from the pseudo vertices to the label of the subset they are representing
mapping from the label of the subsets to the corresponding vertex mapping
AhujaOrlinSharmaCapacitatedMinimumSpanningTree.ImprovementGraphVertexType.valueOf(String name)
Returns the enum constant of this class with the specified name.
AhujaOrlinSharmaCapacitatedMinimumSpanningTree.ImprovementGraphVertexType.values()
Returns an array containing the constants of this enum class, in
the order they are declared.
Initializes the improvement graph, i.e.
Returns the mapping that is used in the valid cycle detection algorithm, i.e.
AhujaOrlinSharmaCapacitatedMinimumSpanningTree.executeNeighborhoodOperation(AbstractCapacitatedMinimumSpanningTree<V,E>.CapacitatedSpanningTreeSolutionRepresentation currentSolution,
Map<Integer,V> improvementGraphVertexMapping,
Map<Pair<Integer,AhujaOrlinSharmaCapacitatedMinimumSpanningTree.ImprovementGraphVertexType>,Integer> pathExchangeVertexMapping,
Map<V,Pair<Set<V>,Double>> subtrees,
GraphWalk<Pair<Integer,AhujaOrlinSharmaCapacitatedMinimumSpanningTree.ImprovementGraphVertexType>,DefaultWeightedEdge> cycle)
Executes the move operations induced by the calculated cycle in the improvement graph.
void
Adds an edge between v1
and v2
to the improvement graph if
newCapacity
does not exceed the capacity constraint.
private void
AhujaOrlinSharmaCapacitatedMinimumSpanningTree.ImprovementGraph.updateOriginNodeConnections(AbstractCapacitatedMinimumSpanningTree<V,E>.CapacitatedSpanningTreeSolutionRepresentation currentSolution,
Map<V,Pair<Set<V>,Double>> subtrees,
Map<Integer,SpanningTreeAlgorithm.SpanningTree<E>> partitionSpanningTrees,
Set<Integer> labelsToUpdate,
V v1,
Pair<Integer,AhujaOrlinSharmaCapacitatedMinimumSpanningTree.ImprovementGraphVertexType> vertexOfV1Single,
Pair<Integer,AhujaOrlinSharmaCapacitatedMinimumSpanningTree.ImprovementGraphVertexType> vertexOfV1Subtree)
Updates the edges to the origin vertex.
private void
AhujaOrlinSharmaCapacitatedMinimumSpanningTree.ImprovementGraph.updateSingleNode(AbstractCapacitatedMinimumSpanningTree<V,E>.CapacitatedSpanningTreeSolutionRepresentation currentSolution,
Map<V,Pair<Set<V>,Double>> subtrees,
Set<V> tabuList,
int label,
double oldWeight,
Set<V> modifiableSet,
Pair<Integer,AhujaOrlinSharmaCapacitatedMinimumSpanningTree.ImprovementGraphVertexType> pseudoVertex,
V v1,
Pair<Integer,AhujaOrlinSharmaCapacitatedMinimumSpanningTree.ImprovementGraphVertexType> vertexOfV1Single)
Updates all edges from vertexOfV1Single
to nodes in the subset represented
by label
.
private void
AhujaOrlinSharmaCapacitatedMinimumSpanningTree.ImprovementGraph.updateSubtreeNode(AbstractCapacitatedMinimumSpanningTree<V,E>.CapacitatedSpanningTreeSolutionRepresentation currentSolution,
Map<V,Pair<Set<V>,Double>> subtrees,
Set<V> tabuList,
int label,
double oldWeight,
Set<V> modifiableSet,
Pair<Integer,AhujaOrlinSharmaCapacitatedMinimumSpanningTree.ImprovementGraphVertexType> pseudoVertex,
V v1,
Pair<Integer,AhujaOrlinSharmaCapacitatedMinimumSpanningTree.ImprovementGraphVertexType> vertexOfV1Subtree)
Updates all edges from vertexOfV1Single
to nodes in the subset represented
by label
.
private boolean
Updates all nodes that correspond to v1
and returns if the vertex
v1
.