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

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.

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

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

Related documentation in the C library

all_st_cuts(), vcount(), edges(), get_eids(), ecount()

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

Author

Gabor Csardi csardi.gabor@gmail.com

Examples

# A very simple graph
g <- graph_from_literal(a -+ b -+ c -+ d -+ e)
st_cuts(g, source = "a", target = "e")
#> $cuts
#> $cuts[[1]]
#> ── <edge sequence> 1/4 · vertex names · from d8263ea ───────────────────────────
#> [1] a → b 
#> 
#> $cuts[[2]]
#> ── <edge sequence> 1/4 · vertex names · from d8263ea ───────────────────────────
#> [1] b → c 
#> 
#> $cuts[[3]]
#> ── <edge sequence> 1/4 · vertex names · from d8263ea ───────────────────────────
#> [1] c → d 
#> 
#> $cuts[[4]]
#> ── <edge sequence> 1/4 · vertex names · from d8263ea ───────────────────────────
#> [1] d → e 
#> 
#> 
#> $partition1s
#> $partition1s[[1]]
#> ── <vertex sequence> 1/5 · named · from d8263ea ────────────────────────────────
#> [1] a
#> 
#> $partition1s[[2]]
#> ── <vertex sequence> 2/5 · named · from d8263ea ────────────────────────────────
#> [1] a b
#> 
#> $partition1s[[3]]
#> ── <vertex sequence> 3/5 · named · from d8263ea ────────────────────────────────
#> [1] a b c
#> 
#> $partition1s[[4]]
#> ── <vertex sequence> 4/5 · named · from d8263ea ────────────────────────────────
#> [1] a b c d
#> 
#> 

# 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")
#> $cuts
#> $cuts[[1]]
#> ── <edge sequence> 2/10 · vertex names · from 82ba3e2 ──────────────────────────
#> [1] s → a  s → b 
#> 
#> $cuts[[2]]
#> ── <edge sequence> 2/10 · vertex names · from 82ba3e2 ──────────────────────────
#> [1] s → a  b → t 
#> 
#> $cuts[[3]]
#> ── <edge sequence> 5/10 · vertex names · from 82ba3e2 ──────────────────────────
#> [1] s → b  a → t  a → 1  a → 2  a → 3 
#> 
#> $cuts[[4]]
#> ── <edge sequence> 5/10 · vertex names · from 82ba3e2 ──────────────────────────
#> [1] s → b  a → t  a → 1  a → 2  3 → b 
#> 
#> $cuts[[5]]
#> ── <edge sequence> 5/10 · vertex names · from 82ba3e2 ──────────────────────────
#> [1] s → b  a → t  a → 1  a → 3  2 → b 
#> 
#> $cuts[[6]]
#> ── <edge sequence> 5/10 · vertex names · from 82ba3e2 ──────────────────────────
#> [1] s → b  a → t  a → 1  2 → b  3 → b 
#> 
#> $cuts[[7]]
#> ── <edge sequence> 5/10 · vertex names · from 82ba3e2 ──────────────────────────
#> [1] s → b  a → t  a → 2  a → 3  1 → b 
#> 
#> $cuts[[8]]
#> ── <edge sequence> 5/10 · vertex names · from 82ba3e2 ──────────────────────────
#> [1] s → b  a → t  a → 2  1 → b  3 → b 
#> 
#> $cuts[[9]]
#> ── <edge sequence> 5/10 · vertex names · from 82ba3e2 ──────────────────────────
#> [1] s → b  a → t  a → 3  1 → b  2 → b 
#> 
#> $cuts[[10]]
#> ── <edge sequence> 5/10 · vertex names · from 82ba3e2 ──────────────────────────
#> [1] s → b  a → t  1 → b  2 → b  3 → b 
#> 
#> $cuts[[11]]
#> ── <edge sequence> 2/10 · vertex names · from 82ba3e2 ──────────────────────────
#> [1] a → t  b → t 
#> 
#> 
#> $partition1s
#> $partition1s[[1]]
#> ── <vertex sequence> 1/7 · named · from 82ba3e2 ────────────────────────────────
#> [1] s
#> 
#> $partition1s[[2]]
#> ── <vertex sequence> 2/7 · named · from 82ba3e2 ────────────────────────────────
#> [1] s b
#> 
#> $partition1s[[3]]
#> ── <vertex sequence> 2/7 · named · from 82ba3e2 ────────────────────────────────
#> [1] s a
#> 
#> $partition1s[[4]]
#> ── <vertex sequence> 3/7 · named · from 82ba3e2 ────────────────────────────────
#> [1] s a 3
#> 
#> $partition1s[[5]]
#> ── <vertex sequence> 3/7 · named · from 82ba3e2 ────────────────────────────────
#> [1] s a 2
#> 
#> $partition1s[[6]]
#> ── <vertex sequence> 4/7 · named · from 82ba3e2 ────────────────────────────────
#> [1] s a 2 3
#> 
#> $partition1s[[7]]
#> ── <vertex sequence> 3/7 · named · from 82ba3e2 ────────────────────────────────
#> [1] s a 1
#> 
#> $partition1s[[8]]
#> ── <vertex sequence> 4/7 · named · from 82ba3e2 ────────────────────────────────
#> [1] s a 1 3
#> 
#> $partition1s[[9]]
#> ── <vertex sequence> 4/7 · named · from 82ba3e2 ────────────────────────────────
#> [1] s a 1 2
#> 
#> $partition1s[[10]]
#> ── <vertex sequence> 5/7 · named · from 82ba3e2 ────────────────────────────────
#> [1] s a 1 2 3
#> 
#> $partition1s[[11]]
#> ── <vertex sequence> 6/7 · named · from 82ba3e2 ────────────────────────────────
#> [1] s a 1 2 3 b
#> 
#>