AhujaOrlinSharmaCyclicExchangeLocalAugmentation (JGraphT : a free Java graph library)

java.lang.Object
- org.jgrapht.alg.cycle.AhujaOrlinSharmaCyclicExchangeLocalAugmentation<V,E>

Type Parameters:

V - the vertex type the graph

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

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.
- Methods inherited from class java.lang.Object
  clone, equals, finalize, getClass, hashCode, notify, notifyAll, toString, wait, wait, wait

- 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 detect
    
    labelMap - the labelMap of the vertices encoding the subsets of vertices
    
    bestImprovement - contains whether the best or the first improvement is returned: best if true, first if false
- Method Detail
  - getLocalAugmentationCycle
```
public GraphWalk<V,E> getLocalAugmentationCycle()
```
    Calculates a valid subset-disjoint negative cycle. If there is no such cycle, it returns an empty GraphWalk instance
    
    Returns:
    
    a valid subset-disjoint negative cycle encoded as GraphWalk