- java.lang.Object
-
- org.jgrapht.alg.flow.PadbergRaoOddMinimumCutset<V,E>
-
- Type Parameters:
V
- the graph vertex typeE
- the graph edge type
public class PadbergRaoOddMinimumCutset<V,E> extends java.lang.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 \subset V$ with $|T|$ even, be a set of vertices that are labelled odd. A cut-set $(U:V-U)$ is called odd if $|T \cap 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 \subseteq V$ such that $c(W:V-W)=min(c(U:V-U)|U \subseteq V, |T \cap 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.
-
-
Field Summary
Fields Modifier and Type Field Description private SimpleWeightedGraph<V,DefaultWeightedEdge>
gomoryHuTree
private GusfieldGomoryHuCutTree<V,E>
gusfieldGomoryHuCutTreeAlgorithm
private double
minimumCutWeight
private Graph<V,E>
network
private java.util.Set<V>
oddVertices
private java.util.Set<V>
sourcePartitionMinimumCut
-
Constructor Summary
Constructors Constructor 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 Static Methods Instance Methods Concrete Methods Modifier and Type Method Description double
calculateMinCut(java.util.Set<V> oddVertices, boolean useTreeCompression)
Calculates the minimum odd cut.private double
calculateMinCutWithoutTreeCompression()
Modified implementation of the algorithm proposed in Odd Minimum Cut-sets and b-matchings by Padberg and Rao.private double
calculateMinCutWithTreeCompression()
Implementation of the algorithm proposed in Odd Minimum Cut-sets and b-matchings by Padberg and Rao.java.util.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 ofcalculateMinCut(Set, boolean)
java.util.Set<V>
getSinkPartition()
Returns partition $V-W$ of the cut obtained after the last invocation ofcalculateMinCut(Set, boolean)
java.util.Set<V>
getSourcePartition()
Returns partition $W$ of the cut obtained after the last invocation ofcalculateMinCut(Set, boolean)
private java.util.Set<V>
intersection(java.util.Set<V> set1, java.util.Set<V> set2)
Efficient way to compute the intersection between two setsstatic <V> boolean
isOddVertexSet(java.util.Set<V> vertices, java.util.Set<V> oddVertices)
Convenience method which test whether the given set contains an odd number of odd-labeled nodes.private void
splitCluster(java.util.Set<V> cluster, java.util.Queue<java.util.Set<V>> queue)
Takes a set of odd vertices with cardinality $2$ or more, and splits them into $2$ new non-empty sets.
-
-
-
Field Detail
-
oddVertices
private java.util.Set<V> oddVertices
-
gusfieldGomoryHuCutTreeAlgorithm
private final GusfieldGomoryHuCutTree<V,E> gusfieldGomoryHuCutTreeAlgorithm
-
gomoryHuTree
private SimpleWeightedGraph<V,DefaultWeightedEdge> gomoryHuTree
-
minimumCutWeight
private double minimumCutWeight
-
sourcePartitionMinimumCut
private java.util.Set<V> sourcePartitionMinimumCut
-
-
Constructor Detail
-
PadbergRaoOddMinimumCutset
public PadbergRaoOddMinimumCutset(Graph<V,E> network)
Creates a new instance of the PadbergRaoOddMinimumCutset algorithm.- Parameters:
network
- input graph
-
PadbergRaoOddMinimumCutset
public PadbergRaoOddMinimumCutset(Graph<V,E> network, double epsilon)
Creates a new instance of the PadbergRaoOddMinimumCutset algorithm.- Parameters:
network
- input graphepsilon
- tolerance
-
PadbergRaoOddMinimumCutset
public PadbergRaoOddMinimumCutset(Graph<V,E> network, MinimumSTCutAlgorithm<V,E> minimumSTCutAlgorithm)
Creates a new instance of the PadbergRaoOddMinimumCutset algorithm.- Parameters:
network
- input graphminimumSTCutAlgorithm
- algorithm used to calculate the Gomory-Hu tree
-
-
Method Detail
-
calculateMinCut
public double calculateMinCut(java.util.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 parameteruseTreeCompression
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 settinguseTreeCompression
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.
-
calculateMinCutWithoutTreeCompression
private double calculateMinCutWithoutTreeCompression()
Modified implementation of the algorithm proposed in Odd Minimum Cut-sets and b-matchings by Padberg and Rao. The optimal cut is directly computed on the Gomory-Hu tree computed for graph $G$. This approach iterates efficiently over all possible cuts of the graph (there are $|V|$ such cuts).- Returns:
- weight of the minimum odd cut.
-
calculateMinCutWithTreeCompression
private double calculateMinCutWithTreeCompression()
Implementation of the algorithm proposed in Odd Minimum Cut-sets and b-matchings by Padberg and Rao. The algorithm evaluates at most $|T|$ cuts in the Gomory-Hu tree.- Returns:
- weight of the minimum odd cut.
-
splitCluster
private void splitCluster(java.util.Set<V> cluster, java.util.Queue<java.util.Set<V>> queue)
Takes a set of odd vertices with cardinality $2$ or more, and splits them into $2$ new non-empty sets.- Parameters:
cluster
- group of odd verticesqueue
- clusters with cardinality $2$ or more
-
intersection
private java.util.Set<V> intersection(java.util.Set<V> set1, java.util.Set<V> set2)
Efficient way to compute the intersection between two sets- Parameters:
set1
- set $1$set2
- set $2$- Returns:
- intersection of set $1$ and $2$
-
isOddVertexSet
public static <V> boolean isOddVertexSet(java.util.Set<V> vertices, java.util.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 setoddVertices
- subset of vertices which are labeled odd- Returns:
- true if the given set contains an odd number of odd-labeled nodes.
-
getSourcePartition
public java.util.Set<V> getSourcePartition()
Returns partition $W$ of the cut obtained after the last invocation ofcalculateMinCut(Set, boolean)
- Returns:
- partition $W$
-
getSinkPartition
public java.util.Set<V> getSinkPartition()
Returns partition $V-W$ of the cut obtained after the last invocation ofcalculateMinCut(Set, boolean)
- Returns:
- partition $V-W$
-
getCutEdges
public java.util.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 ofcalculateMinCut(Set, boolean)
- Returns:
- set of edges which have one endpoint in the source partition and one endpoint in the sink partition.
-
-