org.jgrapht.alg.flow

• Type Parameters:
`V` - the graph vertex type
`E` - the graph edge type

```public class PadbergRaoOddMinimumCutset<V,E>
extends Object```
Implementation of the algorithm by Padberg and Rao to compute Odd Minimum Cut-Sets. Let G=(V,E) be an undirected, simple weighted graph, where all edge weights are positive. Let T ⊂ V with |T| even, be a set of vertices that are labelled odd. A cut-set (U:V-U) is called odd if |T ∩ U| is an odd number. Let c(U:V-U) be the weight of the cut, that is, the sum of weights of the edges which have exactly one endpoint in U and one endpoint in V-U. The problem of finding an odd minimum cut-set in G is stated as follows: Find W ⊆ V such that c(W:V-W)=min{c(U:V-U)|U⊆ V, |T ∩ U| is odd}.

The algorithm has been published in: Padberg, M. Rao, M. Odd Minimum Cut-Sets and b-Matchings. Mathematics of Operations Research, 7(1), p67-80, 1982. A more concise description is published in: Letchford, A. Reinelt, G. Theis, D. Odd minimum cut-sets and b-matchings revisited. SIAM Journal of Discrete Mathematics, 22(4), p1480-1487, 2008.

The runtime complexity of this algorithm is dominated by the runtime complexity of the algorithm used to compute A Gomory-Hu 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.

Author:
Joris Kinable
• ### Constructor Summary

Constructors
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.
• ### Method Summary

All Methods
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 s-t cut obtained after the last invocation of `calculateMinCut(Set, boolean)`
`Set<V>` `getSinkPartition()`
Returns partition V-W 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 odd-labeled nodes.
• ### Methods inherited from class java.lang.Object

`clone, equals, finalize, getClass, hashCode, notify, notifyAll, toString, wait, wait, wait`
• ### Constructor Detail

`public PadbergRaoOddMinimumCutset(Graph<V,E> network)`
Creates a new instance of the PadbergRaoOddMinimumCutset algorithm.
Parameters:
`network` - input graph

```public PadbergRaoOddMinimumCutset(Graph<V,E> network,
double epsilon)```
Creates a new instance of the PadbergRaoOddMinimumCutset algorithm.
Parameters:
`network` - input graph
`epsilon` - tolerance

```public PadbergRaoOddMinimumCutset(Graph<V,E> network,
MinimumSTCutAlgorithm<V,E> minimumSTCutAlgorithm)```
Creates a new instance of the PadbergRaoOddMinimumCutset algorithm.
Parameters:
`network` - input graph
`minimumSTCutAlgorithm` - algorithm used to calculate the Gomory-Hu tree
• ### Method Detail

• #### calculateMinCut

```public double calculateMinCut(Set<V> oddVertices,
boolean useTreeCompression)```
Calculates the minimum odd cut. The implementation follows Algorithm 1 in the paper Odd minimum cut sets and b-matchings revisited by Adam Letchford, Gerhard Reinelt and Dirk Theis. The original algorithm runs on a compressed Gomory-Hu tree: a cut-tree with the odd vertices as terminal vertices. This tree has |T|-1 edges as opposed to |V|-1 for a Gomory-Hu tree defined on the input graph G. This compression step can however be skipped. If you want to run the original algorithm in the paper, set the parameter `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.
Parameters:
`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).
Returns:
weight of the minimum odd cut.
• #### isOddVertexSet

```public static <V> boolean isOddVertexSet(Set<V> vertices,
Set<V> oddVertices)```
Convenience method which test whether the given set contains an odd number of odd-labeled nodes.
Type Parameters:
`V` - vertex type
Parameters:
`vertices` - input set
`oddVertices` - subset of vertices which are labeled odd
Returns:
true if the given set contains an odd number of odd-labeled nodes.
• #### getSourcePartition

`public Set<V> getSourcePartition()`
Returns partition W of the cut obtained after the last invocation of `calculateMinCut(Set, boolean)`
Returns:
partition W
• #### getSinkPartition

`public Set<V> getSinkPartition()`
Returns partition V-W of the cut obtained after the last invocation of `calculateMinCut(Set, boolean)`
Returns:
partition V-W
• #### getCutEdges

`public Set<E> getCutEdges()`
Returns the set of edges which run from the source partition to the sink partition, in the s-t cut obtained after the last invocation of `calculateMinCut(Set, boolean)`
Returns:
set of edges which have one endpoint in the source partition and one endpoint in the sink partition.