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