org.jgrapht.alg.spanning

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 type

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

Author:

Christoph Grüne

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 inherited from class org.jgrapht.alg.spanning.AbstractCapacitatedMinimumSpanningTree

bestSolution, capacity, demands, graph, root

Constructor Summary

Constructors

Constructor and Description
EsauWilliamsCapacitatedMinimumSpanningTree(Graph<V,E> graph, V root, double capacity, Map<V,Double> weights, int numberOfOperationsParameter) Constructs an Esau-Williams GRASP algorithm instance.

Method Summary

Modifier and Type	Method and Description
CapacitatedSpanningTreeAlgorithm.CapacitatedSpanningTree<V,E>	getCapacitatedSpanningTree() Computes a capacitated spanning tree.
protected AbstractCapacitatedMinimumSpanningTree.CapacitatedSpanningTreeSolutionRepresentation	getSolution() Calculates a partition representation of the capacitated spanning tree.

Methods inherited from class java.lang.Object

clone, equals, finalize, getClass, hashCode, notify, notifyAll, toString, wait, wait, wait

Constructor Detail

EsauWilliamsCapacitatedMinimumSpanningTree

public EsauWilliamsCapacitatedMinimumSpanningTree(Graph<V,E> graph,
                                                  V root,
                                                  double capacity,
                                                  Map<V,Double> weights,
                                                  int numberOfOperationsParameter)

Constructs an Esau-Williams GRASP algorithm instance.

Parameters:

graph - the graph

root - the root of the CMST

capacity - the capacity constraint of the CMST

weights - the weights of the vertices

numberOfOperationsParameter - 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 interface CapacitatedSpanningTreeAlgorithm<V,E>

Specified by:

getCapacitatedSpanningTree in class AbstractCapacitatedMinimumSpanningTree<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.