rustworkx.stoer_wagner_min_cut

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 None.

Parameters:

• 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 NaN weights will be ignored, i.e it’s conidered to have zero weight. If weight_fn is not specified a default value of 1.0 will be used for all edges.

Returns:

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:

(usize, NodeIndices)

[stoer_simple_1997]

Stoer, Mechthild and Frank Wagner, “A simple min-cut algorithm”. Journal of the ACM 44 (4), 585-591, 1997.