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$$.

## References

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

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]]
#> + 1/4 edge from 9b5c772 (vertex names):
#> [1] a->b
#>
#> $cuts[[2]] #> + 1/4 edge from 9b5c772 (vertex names): #> [1] b->c #> #>$cuts[[3]]
#> + 1/4 edge from 9b5c772 (vertex names):
#> [1] c->d
#>
#> $cuts[[4]] #> + 1/4 edge from 9b5c772 (vertex names): #> [1] d->e #> #> #>$partition1s
#> $partition1s[[1]] #> + 1/5 vertex, named, from 9b5c772: #> [1] a #> #>$partition1s[[2]]
#> + 2/5 vertices, named, from 9b5c772:
#> [1] a b
#>
#> $partition1s[[3]] #> + 3/5 vertices, named, from 9b5c772: #> [1] a b c #> #>$partition1s[[4]]
#> + 4/5 vertices, named, from 9b5c772:
#> [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]]
#> + 2/10 edges from 7db354c (vertex names):
#> [1] s->a s->b
#>
#> $cuts[[2]] #> + 2/10 edges from 7db354c (vertex names): #> [1] s->a b->t #> #>$cuts[[3]]
#> + 5/10 edges from 7db354c (vertex names):
#> [1] s->b a->t a->1 a->2 a->3
#>
#> $cuts[[4]] #> + 5/10 edges from 7db354c (vertex names): #> [1] s->b a->t a->1 a->2 3->b #> #>$cuts[[5]]
#> + 5/10 edges from 7db354c (vertex names):
#> [1] s->b a->t a->1 a->3 2->b
#>
#> $cuts[[6]] #> + 5/10 edges from 7db354c (vertex names): #> [1] s->b a->t a->1 2->b 3->b #> #>$cuts[[7]]
#> + 5/10 edges from 7db354c (vertex names):
#> [1] s->b a->t a->2 a->3 1->b
#>
#> $cuts[[8]] #> + 5/10 edges from 7db354c (vertex names): #> [1] s->b a->t a->2 1->b 3->b #> #>$cuts[[9]]
#> + 5/10 edges from 7db354c (vertex names):
#> [1] s->b a->t a->3 1->b 2->b
#>
#> $cuts[[10]] #> + 5/10 edges from 7db354c (vertex names): #> [1] s->b a->t 1->b 2->b 3->b #> #>$cuts[[11]]
#> + 2/10 edges from 7db354c (vertex names):
#> [1] a->t b->t
#>
#>
#> $partition1s #>$partition1s[[1]]
#> + 1/7 vertex, named, from 7db354c:
#> [1] s
#>
#> $partition1s[[2]] #> + 2/7 vertices, named, from 7db354c: #> [1] s b #> #>$partition1s[[3]]
#> + 2/7 vertices, named, from 7db354c:
#> [1] s a
#>
#> $partition1s[[4]] #> + 3/7 vertices, named, from 7db354c: #> [1] s a 3 #> #>$partition1s[[5]]
#> + 3/7 vertices, named, from 7db354c:
#> [1] s a 2
#>
#> $partition1s[[6]] #> + 4/7 vertices, named, from 7db354c: #> [1] s a 2 3 #> #>$partition1s[[7]]
#> + 3/7 vertices, named, from 7db354c:
#> [1] s a 1
#>
#> $partition1s[[8]] #> + 4/7 vertices, named, from 7db354c: #> [1] s a 1 3 #> #>$partition1s[[9]]
#> + 4/7 vertices, named, from 7db354c:
#> [1] s a 1 2
#>
#> $partition1s[[10]] #> + 5/7 vertices, named, from 7db354c: #> [1] s a 1 2 3 #> #>$partition1s[[11]]
#> + 6/7 vertices, named, from 7db354c:
#> [1] s a 1 2 3 b
#>
#>