st_cuts {igraph} | R Documentation |
List all (s,t)-cuts in a directed graph.
st_cuts(graph, source, target)
graph |
The input graph. It must be directed. |
source |
The source vertex. |
target |
The target vertex. |
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
.
A list with entries:
cuts |
A list of numeric vectors
containing edge ids. Each vector is an |
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 |
Gabor Csardi csardi.gabor@gmail.com
JS Provan and DR Shier: A Paradigm for listing (s,t)-cuts in graphs, Algorithmica 15, 351–372, 1996.
st_min_cuts()
to list all minimum cuts.
Other flow:
dominator_tree()
,
edge_connectivity()
,
is_min_separator()
,
is_separator()
,
max_flow()
,
min_cut()
,
min_separators()
,
min_st_separators()
,
st_min_cuts()
,
vertex_connectivity()
# 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")