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