V
 the graph vertex typeE
 the graph edge typepublic class PadbergRaoOddMinimumCutset<V,E> extends Object
The algorithm has been published in: Padberg, M. Rao, M. Odd Minimum CutSets and bMatchings. Mathematics of Operations Research, 7(1), p6780, 1982. A more concise description is published in: Letchford, A. Reinelt, G. Theis, D. Odd minimum cutsets and bmatchings revisited. SIAM Journal of Discrete Mathematics, 22(4), p14801487, 2008.
The runtime complexity of this algorithm is dominated by the runtime complexity of the algorithm used to compute A GomoryHu tree on graph G. Consequently, the runtime complexity of this class is O(V^4).
This class does not support changes to the underlying graph. The behavior of this class is undefined when the graph is modified after instantiating this class.
Constructor and Description 

PadbergRaoOddMinimumCutset(Graph<V,E> network)
Creates a new instance of the PadbergRaoOddMinimumCutset algorithm.

PadbergRaoOddMinimumCutset(Graph<V,E> network,
double epsilon)
Creates a new instance of the PadbergRaoOddMinimumCutset algorithm.

PadbergRaoOddMinimumCutset(Graph<V,E> network,
MinimumSTCutAlgorithm<V,E> minimumSTCutAlgorithm)
Creates a new instance of the PadbergRaoOddMinimumCutset algorithm.

Modifier and Type  Method and Description 

double 
calculateMinCut(Set<V> oddVertices,
boolean useTreeCompression)
Calculates the minimum odd cut.

Set<E> 
getCutEdges()
Returns the set of edges which run from the source partition to the sink partition, in the
st cut obtained after the last invocation of
calculateMinCut(Set, boolean) 
Set<V> 
getSinkPartition()
Returns partition VW of the cut obtained after the last invocation of
calculateMinCut(Set, boolean) 
Set<V> 
getSourcePartition()
Returns partition W of the cut obtained after the last invocation of
calculateMinCut(Set, boolean) 
static <V> boolean 
isOddVertexSet(Set<V> vertices,
Set<V> oddVertices)
Convenience method which test whether the given set contains an odd number of oddlabeled
nodes.

public PadbergRaoOddMinimumCutset(Graph<V,E> network)
network
 input graphpublic PadbergRaoOddMinimumCutset(Graph<V,E> network, double epsilon)
network
 input graphepsilon
 tolerancepublic PadbergRaoOddMinimumCutset(Graph<V,E> network, MinimumSTCutAlgorithm<V,E> minimumSTCutAlgorithm)
network
 input graphminimumSTCutAlgorithm
 algorithm used to calculate the GomoryHu treepublic double calculateMinCut(Set<V> oddVertices, boolean useTreeCompression)
useTreeCompression
to
true. Alternatively, experiment which setting of this parameter produces the fastest results.
Both settings are guaranteed to find the optimal cut. Experiments on random graphs showed
that setting useTreeCompression
to false was on average a bit faster.oddVertices
 Set of vertices which are labeled 'odd'. Note that the number of vertices
in this set must be even!useTreeCompression
 parameter indicating whether tree compression should be used
(recommended: false).public static <V> boolean isOddVertexSet(Set<V> vertices, Set<V> oddVertices)
V
 vertex typevertices
 input setoddVertices
 subset of vertices which are labeled oddpublic Set<V> getSourcePartition()
calculateMinCut(Set, boolean)
public Set<V> getSinkPartition()
calculateMinCut(Set, boolean)
public Set<E> getCutEdges()
calculateMinCut(Set, boolean)
Copyright © 2017. All rights reserved.