Cuts¶
Algorithms¶
-
jgrapht.algorithms.cuts.
gomory_hu_gusfield
(graph)[source]¶ Computes a Gomory-Hu Tree using Gusfield’s algorithm.
Gomory-Hu Trees can be used to calculate the maximum s-t flow value and the minimum s-t cut between all pairs of vertices. It does so by performing \(n-1\) max flow computations.
For more details see:
Gusfield, D, Very simple methods for all pairs network flow analysis. SIAM Journal on Computing, 19(1), p142-155, 1990
This implementation uses the push-relabel algorithm for the minimum s-t cut which is \(\mathcal{O}(n^3)\). The total complexity is, therefore, \(\mathcal{O}(n^4)\).
- Parameters
graph – an undirected network
- Returns
a Gomory-Hu tree as an instance of
jgrapht.types.GomoryHuTree
-
jgrapht.algorithms.cuts.
min_st_cut
(graph, source, sink)[source]¶ Compute a minimum s-t cut using the Push-relabel 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 s-t cut.
-
jgrapht.algorithms.cuts.
mincut_stoer_wagner
(graph)[source]¶ Compute a min-cut using the Stoer-Wagner 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 non-negative 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 Cut-Sets using the Pardberg and Rao algorithm.
See the following papers:
Padberg, M. Rao, M. Odd Minimum Cut-Sets and b-Matchings. Mathematics of Operations Research, 7(1), p67-80, 1982.
Letchford, A. Reinelt, G. Theis, D. Odd minimum cut-sets and b-matchings revisited. SIAM Journal of Discrete Mathematics, 22(4), p1480-1487, 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.