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
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
- See Also:
AhujaOrlinSharmaCapacitatedMinimumSpanningTree
-
-
Nested Class Summary
Nested Classes Modifier and Type Class Description private class
AhujaOrlinSharmaCyclicExchangeLocalAugmentation.LabeledPath<V>
Implementation of a labeled path.private class
AhujaOrlinSharmaCyclicExchangeLocalAugmentation.PathSetKey<V>
Implementation of a key for the path maps.
-
Field Summary
Fields Modifier and Type Field Description private boolean
bestImprovement
contains whether the best or the first improvement is returnedprivate Graph<V,E>
graph
the input graphprivate java.util.Map<V,java.lang.Integer>
labelMap
the map that maps each vertex to a subset (identified by labels) of the partitionprivate int
lengthBound
bound on how long the cycle can get
-
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 private boolean
checkDominatedPathsOfLengthK(AhujaOrlinSharmaCyclicExchangeLocalAugmentation.LabeledPath<V> path, java.util.Map<AhujaOrlinSharmaCyclicExchangeLocalAugmentation.PathSetKey<V>,AhujaOrlinSharmaCyclicExchangeLocalAugmentation.LabeledPath<V>> pathsLengthK)
Checks whetherpath
is dominated by some path in the previously calculated set of paths of length k.private boolean
checkDominatedPathsOfLengthKplus1(AhujaOrlinSharmaCyclicExchangeLocalAugmentation.LabeledPath<V> path, java.util.Map<AhujaOrlinSharmaCyclicExchangeLocalAugmentation.PathSetKey<V>,AhujaOrlinSharmaCyclicExchangeLocalAugmentation.LabeledPath<V>> pathsLengthKplus1)
Checks whetherpath
dominates the current minimal cost path with the same head, tail and label set in the set of all paths of length k + 1.GraphWalk<V,E>
getLocalAugmentationCycle()
Calculates a valid subset-disjoint negative cycle.private void
updatePathIndex(java.util.Map<AhujaOrlinSharmaCyclicExchangeLocalAugmentation.PathSetKey<V>,AhujaOrlinSharmaCyclicExchangeLocalAugmentation.LabeledPath<V>> paths, AhujaOrlinSharmaCyclicExchangeLocalAugmentation.LabeledPath<V> path)
Adds a path and removes the path, which has the same tail, head and label set, to the data structurepaths
, which contains all paths indexed by their head, tail and label set.
-
-
-
Field Detail
-
labelMap
private java.util.Map<V,java.lang.Integer> labelMap
the map that maps each vertex to a subset (identified by labels) of the partition
-
lengthBound
private int lengthBound
bound on how long the cycle can get
-
bestImprovement
private boolean bestImprovement
contains whether the best or the first improvement is returned
-
-
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
-
-
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
-
checkDominatedPathsOfLengthKplus1
private boolean checkDominatedPathsOfLengthKplus1(AhujaOrlinSharmaCyclicExchangeLocalAugmentation.LabeledPath<V> path, java.util.Map<AhujaOrlinSharmaCyclicExchangeLocalAugmentation.PathSetKey<V>,AhujaOrlinSharmaCyclicExchangeLocalAugmentation.LabeledPath<V>> pathsLengthKplus1)
Checks whetherpath
dominates the current minimal cost path with the same head, tail and label set in the set of all paths of length k + 1. Thus, dominated paths are eliminated. This is important out of efficiency reasons, otherwise many unnecessary paths may be considered in further calculations.- Parameters:
path
- the currently calculated pathpathsLengthKplus1
- all before calculated paths of length k + 1- Returns:
- whether
path
dominates the current minimal cost path with the same head, tail and label set.
-
checkDominatedPathsOfLengthK
private boolean checkDominatedPathsOfLengthK(AhujaOrlinSharmaCyclicExchangeLocalAugmentation.LabeledPath<V> path, java.util.Map<AhujaOrlinSharmaCyclicExchangeLocalAugmentation.PathSetKey<V>,AhujaOrlinSharmaCyclicExchangeLocalAugmentation.LabeledPath<V>> pathsLengthK)
Checks whetherpath
is dominated by some path in the previously calculated set of paths of length k. This is important out of efficiency reasons, otherwise many unnecessary paths may be considered in further calculations.- Parameters:
path
- the currently calculated pathpathsLengthK
- all previously calculated paths of length k- Returns:
- whether
path
is dominated by some path inpathsLengthK
-
updatePathIndex
private void updatePathIndex(java.util.Map<AhujaOrlinSharmaCyclicExchangeLocalAugmentation.PathSetKey<V>,AhujaOrlinSharmaCyclicExchangeLocalAugmentation.LabeledPath<V>> paths, AhujaOrlinSharmaCyclicExchangeLocalAugmentation.LabeledPath<V> path)
Adds a path and removes the path, which has the same tail, head and label set, to the data structurepaths
, which contains all paths indexed by their head, tail and label set.- Parameters:
paths
- the map of paths, which are indexed by head, tail and label set, to add the path topath
- the path to add
-
-