# all\_st\_cuts for undirected graphs?

**URL:** <https://igraph.discourse.group/t/all-st-cuts-for-undirected-graphs/607>\
**Category:** Usage\
**Tags:** C, Python\
**Created:** [26 January 2021 21:32 UTC](https://igraph.discourse.group/t/all-st-cuts-for-undirected-graphs/607 "2021-01-26T21:32:44Z")\
**Posts on this page:** 1\
**Page:** 1

<div class="post-metadata">

**Author:** ![salterduke](https://avatars.discourse-cdn.com/v4/letter/s/eb9ed0/32.png) [@salterduke](https://igraph.discourse.group/u/salterduke)\
**Post date:** [26 January 2021 21:32 UTC](https://igraph.discourse.group/t/all-st-cuts-for-undirected-graphs/607/1 "2021-01-26T21:32:44Z")

</div>

Hi,

I’m trying to find all the st cuts between two vertices in an undirected graph. igraph has a function that does it for _directed_ graphs (all\_st\_cuts), and of course I can turn my undirected graph into a directed one by turning each edge into two directed ones and then run all\_st\_cuts, but that seems a highly inefficient way of doing it. And in my tests, it’s certainly not fast enough to work with a reasonably dense graph with about 1000 nodes.

Oddly, the paper that the function is based on doesn’t require that the graph be directed, so I’m curious as to why there is only a version for directed graphs in the library - does anyone know? Is there a way to modify the underlying code so that I can run the function without converting to directed?  
Citation for the paper:  
Provan, J. S., and D. R. Shier. 1996. “A Paradigm for Listing (s, T)-Cuts in Graphs.” _Algorithmica. An International Journal in Computer Science_ 15 (4): 351–72.

I’m using igraph via the python-igraph library, and while I could probably code an alternate algorithm in python that would be _theoretically_ more efficient, the running time for python would probably be too slow to be useful for reasonably sized graphs, so I’d prefer to use igraph functions that call C functions as much as possible - they’re probably better written and definitely more thoroughly tested than anything I could write.

Any thoughts on the possibility of tweaking stuff to get an undirected version of all\_st\_cuts using the C libraries? Or alternate ways of doing it that use C libraries as much as possible for speed?

Cheers in advance  
Michal