Class EsauWilliamsCapacitatedMinimumSpanningTree<V,E>
- java.lang.Object
-
- org.jgrapht.alg.spanning.AbstractCapacitatedMinimumSpanningTree<V,E>
-
- org.jgrapht.alg.spanning.EsauWilliamsCapacitatedMinimumSpanningTree<V,E>
-
- Type Parameters:
V
- the vertex typeE
- the edge type
- All Implemented Interfaces:
CapacitatedSpanningTreeAlgorithm<V,E>
public class EsauWilliamsCapacitatedMinimumSpanningTree<V,E> extends AbstractCapacitatedMinimumSpanningTree<V,E>
Implementation of a randomized version of the Esau-Williams heuristic, a greedy randomized adaptive search heuristic (GRASP) for the capacitated minimum spanning tree (CMST) problem. It calculates a suboptimal CMST. The original version can be found in L. R. Esau and K. C. Williams. 1966. On teleprocessing system design: part II a method for approximating the optimal network. IBM Syst. J. 5, 3 (September 1966), 142-147. DOI=http://dx.doi.org/10.1147/sj.53.0142 This implementation runs in polynomial time O(|V|^3).This implementation is a randomized version described in Ahuja, Ravindra K., Orlin, James B., and Sharma, Dushyant, (1998). New neighborhood search structures for the capacitated minimum spanning tree problem, No WP 4040-98. Working papers, Massachusetts Institute of Technology (MIT), Sloan School of Management.
This version runs in polynomial time dependent on the number of considered operations per iteration
numberOfOperationsParameter
(denoted by p), such that runs is in $O(|V|^3 + p|V|) = O(|V|^3)$ since $p \leq |V|$.A Capacitated Minimum Spanning Tree (CMST) is a rooted minimal cost spanning tree that satisfies the capacity constrained on all trees that are connected to the designated root. The problem is NP-hard.
- Since:
- July 12, 2018
-
-
Nested Class Summary
-
Nested classes/interfaces inherited from class org.jgrapht.alg.spanning.AbstractCapacitatedMinimumSpanningTree
AbstractCapacitatedMinimumSpanningTree.CapacitatedSpanningTreeSolutionRepresentation
-
Nested classes/interfaces inherited from interface org.jgrapht.alg.interfaces.CapacitatedSpanningTreeAlgorithm
CapacitatedSpanningTreeAlgorithm.CapacitatedSpanningTree<V,E>, CapacitatedSpanningTreeAlgorithm.CapacitatedSpanningTreeImpl<V,E>
-
-
Field Summary
Fields Modifier and Type Field Description private boolean
isAlgorithmExecuted
contains whether the algorithm was executedprivate int
numberOfOperationsParameter
the number of the most profitable operations for every iteration considered in the procedure.-
Fields inherited from class org.jgrapht.alg.spanning.AbstractCapacitatedMinimumSpanningTree
bestSolution, capacity, demands, graph, root
-
-
Method Summary
All Methods Instance Methods Concrete Methods Modifier and Type Method Description private V
calculateClosestVertex(V vertex, java.util.Map<V,java.util.Set<java.lang.Integer>> restrictionMap, java.util.Map<java.lang.Integer,V> shortestGate)
Calculates the closest vertex tovertex
such that the connection ofvertex
to the subtree of the closest vertex does not violate the capacity constraint and the savings are positive.CapacitatedSpanningTreeAlgorithm.CapacitatedSpanningTree<V,E>
getCapacitatedSpanningTree()
Computes a capacitated spanning tree.private double
getDistance(V v1, V v2)
private java.util.LinkedList<V>
getListOfBestOptions(java.util.Map<V,java.lang.Double> savings)
Returns the list of the best options as stored insavings
.protected AbstractCapacitatedMinimumSpanningTree.CapacitatedSpanningTreeSolutionRepresentation
getSolution()
Calculates a partition representation of the capacitated spanning tree.
-
-
-
Constructor Detail
-
EsauWilliamsCapacitatedMinimumSpanningTree
public EsauWilliamsCapacitatedMinimumSpanningTree(Graph<V,E> graph, V root, double capacity, java.util.Map<V,java.lang.Double> weights, int numberOfOperationsParameter)
Constructs an Esau-Williams GRASP algorithm instance.- Parameters:
graph
- the graphroot
- the root of the CMSTcapacity
- the capacity constraint of the CMSTweights
- the weights of the verticesnumberOfOperationsParameter
- the parameter how many best vertices are considered in the procedure
-
-
Method Detail
-
getCapacitatedSpanningTree
public CapacitatedSpanningTreeAlgorithm.CapacitatedSpanningTree<V,E> getCapacitatedSpanningTree()
Computes a capacitated spanning tree.Returns a capacitated spanning tree computed by the Esau-Williams algorithm.
- Specified by:
getCapacitatedSpanningTree
in interfaceCapacitatedSpanningTreeAlgorithm<V,E>
- Specified by:
getCapacitatedSpanningTree
in classAbstractCapacitatedMinimumSpanningTree<V,E>
- Returns:
- a capacitated spanning tree
-
getSolution
protected AbstractCapacitatedMinimumSpanningTree.CapacitatedSpanningTreeSolutionRepresentation getSolution()
Calculates a partition representation of the capacitated spanning tree. With that, it is possible to calculate the to the partition corresponding capacitated spanning tree in polynomial time by calculating the MSTs. The labels of the partition that are returned are non-negative.- Returns:
- a representation of the partition of the capacitated spanning tree that has non-negative labels.
-
getListOfBestOptions
private java.util.LinkedList<V> getListOfBestOptions(java.util.Map<V,java.lang.Double> savings)
Returns the list of the best options as stored insavings
.- Parameters:
savings
- the savings calculated in the algorithm (see getSolution())- Returns:
- the list of the
numberOfOperationsParameter
best options
-
calculateClosestVertex
private V calculateClosestVertex(V vertex, java.util.Map<V,java.util.Set<java.lang.Integer>> restrictionMap, java.util.Map<java.lang.Integer,V> shortestGate)
Calculates the closest vertex tovertex
such that the connection ofvertex
to the subtree of the closest vertex does not violate the capacity constraint and the savings are positive. Otherwise null is returned.- Parameters:
vertex
- the vertex to find a valid closest vertex forrestrictionMap
- the set of labels of sets of the partition, in which the capacity constraint is violated.- Returns:
- the closest valid vertex and null, if no valid vertex exists
-
-