igraph (version 1.3.5)

st_cuts: List all (s,t)-cuts of a graph

Description

List all (s,t)-cuts in a directed graph.

Usage

st_cuts(graph, source, target)

Value

A list with entries:

cuts

A list of numeric vectors containing edge ids. Each vector is an \((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\).

Arguments

graph

The input graph. It must be directed.

source

The source vertex.

target

The target vertex.

Author

Gabor Csardi

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

References

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

See Also

st_min_cuts to list all minimum cuts.

Examples

# A very simple graph
g <- graph_from_literal(a -+ b -+ c -+ d -+ e)
st_cuts(g, source="a", target="e")

# A somewhat more difficult graph
g2 <- graph_from_literal(s --+ a:b, a:b --+ t,
                   a --+ 1:2:3, 1:2:3 --+ b)
st_cuts(g2, source="s", target="t")