This is the documentation for the current state of the development branch of rustworkx. The documentation or APIs here can change prior to being released.
- stoer_wagner_min_cut(graph, /, weight_fn=None)#
Compute a weighted minimum cut using the Stoer-Wagner algorithm.
Determine the minimum cut of a graph using the Stoer-Wagner algorithm [stoer_simple_1997]. All weights must be nonnegative. If the input graph is disconnected, a cut with zero value will be returned. For graphs with less than two nodes, this function returns
PyGraph – The graph to be used
weight_fn (Callable) – An optional callable object (function, lambda, etc) which will be passed the edge object and expected to return a
float. Edges with
NaNweights will be ignored, i.e it’s conidered to have zero weight. If
weight_fnis not specified a default value of
1.0will be used for all edges.
A tuple with the minimum cut value and a list of all the node indexes contained in one part of the partition that defines a minimum cut.
- Return type:
Stoer, Mechthild and Frank Wagner, “A simple min-cut algorithm”. Journal of the ACM 44 (4), 585-591, 1997.