List all minimum $(s,t)$-cuts of a graph
Listing all minimum $(s,t)$-cuts of a directed graph, for given $s$ and $t$.
st_min_cuts(graph, source, target, capacity = NULL)
- The input graph. It must be directed.
- The id of the source vertex.
- The id of the target vertex.
- Numeric vector giving the edge capacities. If this is
NULLand the graph has a
weightedge attribute, then this attribute defines the edge capacities. For forcing unit edge capacities, even for graphs that have a
Given a $G$ directed graph and two, different and non-ajacent vertices, $s$ and $t$, an $(s,t)$-cut is a set of edges, such that after removing these edges from $G$ there is no directed path from $s$ to $t$.
The size of an $(s,t)$-cut is defined as the sum of the capacities (or weights) in the cut. For unweighed (=equally weighted) graphs, this is simply the number of edges.
An $(s,t)$-cut is minimum if it is of the smallest possible size.
- A list with entries:
value Numeric scalar, the size of the minimum cut(s). cuts A list of numeric vectors containing edge ids. Each vector is a minimum $(s,t)$-cut. partition1s A list of numeric vectors containing vertex ids, they correspond to the edge cuts. Each vertex set is a generator of the corresponding cut, i.e. in the graph $G=(V,E)$, the vertex set $X$ and its complementer $V-X$, generates the cut that contains exactly the edges that go from $X$ to $V-X$.
JS Provan and DR Shier: A Paradigm for listing (s,t)-cuts in graphs, Algorithmica 15, 351--372, 1996.
# A difficult graph, from the Provan-Shier paper g <- graph_from_literal(s --+ a:b, a:b --+ t, a --+ 1:2:3:4:5, 1:2:3:4:5 --+ b) st_min_cuts(g, source="s", target="t")