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.

class jgrapht.types.Cut[source]

A graph cut.

abstract capacity()[source]

Cut edges total capacity.

abstract edges()[source]

Edges crossing the cut.

abstract source_partition()[source]

Source partition vertex set.

abstract target_partition()[source]

Target partition vertex set.

abstract weight()[source]

Cut edges total weight.

class jgrapht.types.GomoryHuTree[source]

A Gomory-Hu Tree.

abstract as_graph()[source]

Compute the Gomory-Hu tree as a graph.

Returns

the Gomory-Hu tree as an instance of Graph

abstract min_cut()[source]

Compute the minimum cut of the graph.

Returns

a cut as an instance of Cut

abstract min_st_cut(s, t)[source]

Compute the minimum s-t cut.

Returns

a cut as an instance of Cut