Module org.jgrapht.core
Package org.jgrapht.alg.cycle
Class AhujaOrlinSharmaCyclicExchangeLocalAugmentation<V,E>
java.lang.Object
org.jgrapht.alg.cycle.AhujaOrlinSharmaCyclicExchangeLocalAugmentation<V,E>
 Type Parameters:
V
 the vertex type the graphE
 the edge type of the graph
Implementation of an algorithm for the local augmentation problem for the cyclic exchange
neighborhood, i.e. it finds subsetdisjoint negative cycles in a graph, based on Ravindra K.
Ahuja, James B. Orlin, Dushyant Sharma, A composite very largescale neighborhood structure for
the capacitated minimum spanning tree problem, Operations Research Letters, Volume 31, Issue 3,
2003, Pages 185194, ISSN 01676377, https://doi.org/10.1016/S01676377(02)002365.
(http://www.sciencedirect.com/science/article/pii/S0167637702002365)
A subsetdisjoint cycle is a cycle such that no two vertices in the cycle are in the same subset
of a given partition of the whole vertex set.
This algorithm returns the first or the best found negative subsetdisjoint cycle. In the case of
the first found cycle, the cycle has minimum number of vertices. It may enumerate all paths up to
the length given by the parameter
lengthBound
, i.e the algorithm runs in exponential
time.
This algorithm is used to detect valid cyclic exchanges in a cyclic exchange neighborhood for the
Capacitated Minomum Spanning Tree problem
AhujaOrlinSharmaCapacitatedMinimumSpanningTree
 Since:
 June 7, 2018
 Author:
 Christoph GrĂ¼ne
 See Also:

Constructor Summary

Method Summary
Modifier and TypeMethodDescriptionCalculates a valid subsetdisjoint negative cycle.

Constructor Details

AhujaOrlinSharmaCyclicExchangeLocalAugmentation
public AhujaOrlinSharmaCyclicExchangeLocalAugmentation(Graph<V, E> graph, int lengthBound, Map<V, Integer> labelMap, boolean bestImprovement) Constructs an algorithm with given inputs Parameters:
graph
 the directed graph on which to find the negative subset disjoint cycle. The vertices of the graph are labeled according to labelMap.lengthBound
 the (inclusive) upper bound for the length of cycles to detectlabelMap
 the labelMap of the vertices encoding the subsets of verticesbestImprovement
 contains whether the best or the first improvement is returned: best if true, first if false


Method Details

getLocalAugmentationCycle
Calculates a valid subsetdisjoint negative cycle. If there is no such cycle, it returns an empty GraphWalk instance Returns:
 a valid subsetdisjoint negative cycle encoded as GraphWalk
