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
public class AhujaOrlinSharmaCyclicExchangeLocalAugmentation<V,E> extends java.lang.Object
Implementation of an algorithm for the local augmentation problem for the cyclic exchange neighborhood, i.e. it finds subset-disjoint negative cycles in a graph, based on Ravindra K. Ahuja, James B. Orlin, Dushyant Sharma, A composite very large-scale neighborhood structure for the capacitated minimum spanning tree problem, Operations Research Letters, Volume 31, Issue 3, 2003, Pages 185-194, ISSN 0167-6377, https://doi.org/10.1016/S0167-6377(02)00236-5. (http://www.sciencedirect.com/science/article/pii/S0167637702002365) A subset-disjoint 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 subset-disjoint 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 parameterlengthBound
, 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 problemAhujaOrlinSharmaCapacitatedMinimumSpanningTree
- Since:
- June 7, 2018
- Author:
- Christoph GrĂ¼ne
- See Also:
AhujaOrlinSharmaCapacitatedMinimumSpanningTree
-
-
Constructor Summary
Constructors Constructor Description AhujaOrlinSharmaCyclicExchangeLocalAugmentation(Graph<V,E> graph, int lengthBound, java.util.Map<V,java.lang.Integer> labelMap, boolean bestImprovement)
Constructs an algorithm with given inputs
-
Method Summary
All Methods Instance Methods Concrete Methods Modifier and Type Method Description GraphWalk<V,E>
getLocalAugmentationCycle()
Calculates a valid subset-disjoint negative cycle.
-
-
-
Constructor Detail
-
AhujaOrlinSharmaCyclicExchangeLocalAugmentation
public AhujaOrlinSharmaCyclicExchangeLocalAugmentation(Graph<V,E> graph, int lengthBound, java.util.Map<V,java.lang.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
-
-