Cuts¶
Algorithms¶

jgrapht.algorithms.cuts.
gomory_hu_gusfield
(graph)[source]¶ Computes a GomoryHu Tree using Gusfield’s algorithm.
GomoryHu Trees can be used to calculate the maximum st flow value and the minimum st cut between all pairs of vertices. It does so by performing \(n1\) max flow computations.
For more details see:
Gusfield, D, Very simple methods for all pairs network flow analysis. SIAM Journal on Computing, 19(1), p142155, 1990
This implementation uses the pushrelabel algorithm for the minimum st cut which is \(\mathcal{O}(n^3)\). The total complexity is, therefore, \(\mathcal{O}(n^4)\).
 Parameters
graph – an undirected network
 Returns
a GomoryHu tree as an instance of
jgrapht.types.GomoryHuTree

jgrapht.algorithms.cuts.
min_st_cut
(graph, source, sink)[source]¶ Compute a minimum st cut using the Pushrelabel algorithm.
This is a \(\mathcal{O}(n^3)\) algorithm where \(n\) is the number of vertices of the graph. For more details on the algorithm see:
Andrew V. Goldberg and Robert Tarjan. A new approach to the maximum flow problem. Proceedings of STOC ‘86.
The algorithm uses the graph edge weights as the network edge capacities.
 Parameters
graph – The input graph. This can be either directed or undirected. Edge capacities are taken from the edge weights.
source – The source vertex
sink – The sink vertex.
 Returns
A min st cut.

jgrapht.algorithms.cuts.
mincut_stoer_wagner
(graph)[source]¶ Compute a mincut using the StoerWagner algorithm.
This implementation requires \(\mathcal{O}(m n \log m)\) time where \(n\) is the number of vertices and \(m\) the number of edges of the graph.
 Parameters
graph – the input graph. Must be undirected with nonnegative edge weights
 Returns
a min cut as an instance of
Cut
.

jgrapht.algorithms.cuts.
oddmincutset_padberg_rao
(graph, odd_vertices, use_tree_compression=False)[source]¶ Compute Odd Minimum CutSets using the Pardberg and Rao algorithm.
See the following papers:
Padberg, M. Rao, M. Odd Minimum CutSets and bMatchings. Mathematics of Operations Research, 7(1), p6780, 1982.
Letchford, A. Reinelt, G. Theis, D. Odd minimum cutsets and bmatchings revisited. SIAM Journal of Discrete Mathematics, 22(4), p14801487, 2008.
Running time \(\mathcal{O}(n^4)\).
 Parameters
graph – an undirected network. Must be simple and all edge weights must be positive.
odd_vertices – set of vertices labelled “odd”. It must have even cardinality.
use_tree_compression – whether to use the tree compression technique
 Returns
a cut as an instance of
Cut
.
Types¶
Cuts are represented using instances of the following classes.