# Source code for jgrapht.algorithms.cuts

from .. import backend as _backend

from .._internals._flows import (
_JGraphTCut,
_JGraphTGomoryHuTree,
)
from .._internals._collections import _JGraphTIntegerMutableSet

from .._internals._anyhashableg import (
_is_anyhashable_graph,
_vertex_anyhashableg_to_g as _vertex_anyhashableg_to_g,
)
from .._internals._anyhashableg_flows import (
_AnyHashableGraphCut,
_AnyHashableGraphGomoryHuTree,
_AnyHashableGraphEquivalentFlowTree,
)

from .flow import push_relabel

[docs]def mincut_stoer_wagner(graph): r"""Compute a min-cut using the Stoer-Wagner algorithm. This implementation requires :math:\mathcal{O}(m n \log m) time where :math:n is the number of vertices and :math:m the number of edges of the graph. :param graph: the input graph. Must be undirected with non-negative edge weights :returns: a min cut as an instance of :py:class:.Cut. """ ( cut_weight, cut_source_partition_handle, ) = _backend.jgrapht_cut_mincut_exec_stoer_wagner(graph.handle) if _is_anyhashable_graph(graph): return _AnyHashableGraphCut(graph, cut_weight, cut_source_partition_handle) else: return _JGraphTCut(graph, cut_weight, cut_source_partition_handle)
[docs]def min_st_cut(graph, source, sink): r"""Compute a minimum s-t cut using the Push-relabel algorithm. This is a :math:\mathcal{O}(n^3) algorithm where :math: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. :param graph: The input graph. This can be either directed or undirected. Edge capacities are taken from the edge weights. :param source: The source vertex :param sink: The sink vertex. :returns: A min s-t cut. """ _, cut = push_relabel(graph, source, sink) return cut
[docs]def gomory_hu_gusfield(graph): r"""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 :math: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 :math:\mathcal{O}(n^3). The total complexity is, therefore, :math:\mathcal{O}(n^4). :param graph: an undirected network :returns: a Gomory-Hu tree as an instance of :py:class:jgrapht.types.GomoryHuTree """ handle = _backend.jgrapht_cut_gomoryhu_exec_gusfield(graph.handle) if _is_anyhashable_graph(graph): return _AnyHashableGraphGomoryHuTree(handle, graph) else: return _JGraphTGomoryHuTree(handle, graph)
[docs]def oddmincutset_padberg_rao(graph, odd_vertices, use_tree_compression=False): r"""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 :math:\mathcal{O}(n^4). :param graph: an undirected network. Must be simple and all edge weights must be positive. :param odd_vertices: set of vertices labelled "odd". It must have even cardinality. :param use_tree_compression: whether to use the tree compression technique :returns: a cut as an instance of :py:class:.Cut. """ odd_set = _JGraphTIntegerMutableSet() if _is_anyhashable_graph(graph): for x in odd_vertices: odd_set.add(_vertex_anyhashableg_to_g(graph, x)) else: for x in odd_vertices: odd_set.add(x) ( cut_weight, cut_source_partition_handle, ) = _backend.jgrapht_cut_oddmincutset_exec_padberg_rao( graph.handle, odd_set.handle, use_tree_compression ) if _is_anyhashable_graph(graph): return _AnyHashableGraphCut(graph, cut_weight, cut_source_partition_handle) else: return _JGraphTCut(graph, cut_weight, cut_source_partition_handle)