stMincuts: List all minimum $(s,t)$-cuts of a graph
Description
Listing all minimum $(s,t)$-cuts of a directed graph, for given
$s$ and $t$.
Usage
stMincuts(graph, source, target, capacity = NULL)
Arguments
graph
The input graph. It must be directed.
source
The id of the source vertex.
target
The id of the target vertex.
capacity
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
Value
A list with entries:
valueNumeric scalar, the size of the minimum cut(s).
cutsA list of numeric vectors containing edge ids. Each vector
is a minimum $(s,t)$-cut.
partition1sA 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$.
concept
Edge cuts
(s,t)-cuts
Minimum cuts
Minimum (s,t)-cuts
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.
# A difficult graph, from the Provan-Shier paperg <- graph.formula(s --+ a:b, a:b --+ t,
a --+ 1:2:3:4:5, 1:2:3:4:5 --+ b)
stMincuts(g, source="s", target="t")