How to get all the possible set of edges of graph that disconnects the graph ( satisfying minimum cut )

Question

Imagine I have the graph below.

Minimum cut of this graph is 2 which means it takes at least removing 2 edges to make this graph disconnected. I want to get all the possible set of edges that satisfy this number and removing them makes graph disconnected. in this example [(4,8),(3,5)] and [(5,6),(6,7)]

with the help of internet I find the code below:

import networkx as nx

# creating test graph
test_graph =  nx.Graph()
test_graph.add_edge(0, 1)
test_graph.add_edge(0, 2)
test_graph.add_edge(0, 4)
test_graph.add_edge(1, 2)
test_graph.add_edge(1, 3)
test_graph.add_edge(2, 3)
test_graph.add_edge(2, 4)
test_graph.add_edge(3, 4)
test_graph.add_edge(3, 5)
test_graph.add_edge(4, 8)
test_graph.add_edge(5, 6)
test_graph.add_edge(5, 7)
test_graph.add_edge(5, 8)
test_graph.add_edge(6, 7)
test_graph.add_edge(7, 9)
test_graph.add_edge(8, 9)
test_graph.add_edge(8, 10)
test_graph.add_edge(8, 11)
test_graph.add_edge(9, 10)
test_graph.add_edge(9, 11)
test_graph.add_edge(10, 11)

print(nx.minimum_edge_cut(test_graph))

but it only returns the first edges it finds (in this case [(5,6),(6,7)] but I want all the candidates. can any body help me pls?

Answer 1

from networkx.algorithms.connectivity import minimum_st_edge_cut

all_cuts = []

for n in test_graph.nodes:
    for k in test_graph.nodes:
        
        if n==k:
            continue
            
        all_cuts.append(minimum_st_edge_cut(test_graph, n, k, flow_func=None, auxiliary=None, residual=None))

all_cuts_with_min_len = [frozenset(cut) for cut in all_cuts if len(cut) == len(min(all_cuts, key=len))]
all_min_cuts = [frozenset([tuple(sorted(i)) for i in j]) for j in all_cuts_with_min_len]
all_min_cuts = [set(s) for s in set(all_min_cuts)]
print(all_min_cuts)

This calculates all the possible cuts, identifies the shortest ones, cleans the different permutations. The result is: [{(3, 5), (4, 8)}, {(5, 6), (6, 7)}].

Please be aware that this is surely not the most efficient nor the most elegant solution.