Is there any way to find all cutsets of a graph using IGraphM?

Usage
1

Is there any way to find all cutsets of a graph using IGraphM?

g = Graph[{DirectedEdge[0, 3, 1], DirectedEdge[2, 1, 2], 
    DirectedEdge[2, 0, 3], DirectedEdge[0, 2, 4], 
    DirectedEdge[3, 1, 5], DirectedEdge[3, 1, 6], 
    DirectedEdge[0, 4, 1], DirectedEdge[4, 5, 1], 
    DirectedEdge[0, 5, 1]}, VertexLabels -> "Name"];

IncidenceMatrix from Mathematica is helpful, but it doesn’t include all possible cutsets.

2

Have a look at IGFindMinimalCuts and IGFindMinimumCuts. These finds minimal or minimum edge cuts between two specific vertices.

3

Thanks for the info. I tried, but it doesn’t seem to work — or did I misunderstand something?

image
image1617×836 53.1 KB

4

What is the result that you are expecting? There is only one minimal edge cut between 0 and 3, and it is returning that.

5

I’m sorry—I probably misunderstood the concept of connectedness in a directed graph.
I converted it to an undirected graph, and now it seems to work fine.

image
image2118×862 76.2 KB

However, for directed multigraphs, how can I get all the cutsets in a format similar to Kirchhoff’s current law equations in electrical circuits (similar to IncidenceMatrix)?
The conversion to an undirected graph allows me to find the cutsets, but they are just sets of edges without any reference direction.

6

Do you mean that you want the result to be set of directed edges, but you want to compute cuts while ignoring edge directions?

I think it would be a useful feature to have a DirectedEdges option that allows ignoring edge directions in directed graphs. Can you open an issue to suggest this feature, so I wouldn’t forget?

7

Sorry, that’s not exactly what I meant. But if you think it would be helpful, I will open a feature request.

What I actually want is something like this:

image
image850×440 54.8 KB

(a random image I found from google search)

Assume that for a cutset in a directed graph, you can write an equation like
e1 + e4 - e5 - e6 = 0
where e1 and e4 go in one direction across the cut, and e5 and e6 go in the opposite direction.

So instead of just a list of edge cut like {e1, e4, e5, e6}, I want something that also captures the direction of each edge relative to the cut, such as:
e1 + e4 - e5 - e6 = 0, or {e1, e4, -e5, -e6}, or {-e1, -e4, e5, e6}, etc.