Numeric vector giving the edge capacities. If this is
NULL and the graph has a weight edge attribute, then this
attribute defines the edge capacities. For forcing unit edge capacities,
even for graphs that have a weight edge attribute, supply NA
here.

Value

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\).

Details

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.

References

JS Provan and DR Shier: A Paradigm for listing (s,t)-cuts in
graphs, Algorithmica 15, 351--372, 1996.

# NOT RUN {# A difficult graph, from the Provan-Shier paperg <- 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")
# }