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

In igraph: Network Analysis and Visualization

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

Description

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

Usage

st_cuts(graph, source, target)

Arguments

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

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.

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.

Related documentation in the C library

igraph_all_st_cuts().

Author(s)

Gabor Csardi [e-mail]

References

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

See Also

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()

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")

igraph documentation built on Oct. 20, 2024, 1:06 a.m.