igraph (version 0.6-2)

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

Description

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

Usage

stCuts(graph, source, target)

Arguments

graph
The input graph. It must be directed.
source
The source vertex.
target
The target vertex.

Value

  • A list with entries:
  • cutsA list of numeric vectors containing edge ids. Each vector is an $(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

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

stMincuts to list all minimum cuts.

Examples

Run this code
# A very simple graph
g <- graph.formula(a -+ b -+ c -+ d -+ e)
stCuts(g, source="a", target="e")

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

Run the code above in your browser using DataCamp Workspace