Algorithm for listing minimal directed cuts and minimal dijoins
I'd like to share an algorithm in Sage to compute minimal directed cuts and minimal dijoins of a digraph and to ask for feedback regarding its correctness and efficiency.
I firstly recall some basic definitions.
Definition. Let $G = (V(G),E(G))$ be a directed graph (abbreviated to digraph throughout).
A non-empty set of edges $C^* \subseteq E(G)$ is called a cut if there is a partition $V_0 \sqcup V_1 = V(G)$ of the vertex set such that $C^*$ is the set of edges connecting a vertex of $V_0$ and a vertex of $V_1$.
A cut $C^* $ is directed if either each edge of $C^* $ leads from $V_0$ to $V_1$, or each edge of $C^*$ leads from $V_1$ to $V_0$.
- A cut $C^* $ is minimal if there does not exist any cut properly contained in $C^* $.
- A dijoin is a subset $E$ of the edge set $E(G)$ such that $E\cap K\neq \emptyset$, for every directed cut $K$ of $G$.
- A dijoin $E$ is minimal if there does not exist any dijoin properly contained in $E$.
The code. The Sage code (with an example) can be found here:
from itertools import chain, combinations
def all_subsets(edges):
"""Returns all subsets of the set of edges."""
edges_list = list(edges)
return [set(comb) for r in range(1, len(edges_list)+1) for comb in combinations(edges_list, r)]
def directed_edge_cuts(D):
"""
Given a directed graph D, returns the list of minimal directed cuts.
Each cut is a list of directed edges that disconnect the graph into two
parts, with all edges going in one direction between them.
"""
from itertools import combinations
# Convert the directed graph to an undirected one
G = D.to_undirected()
edges = list(G.edges(labels=False))
n = len(edges)
minimal_cuts = []
for r in range(1, n + 1):
for subset in combinations(edges, r):
subset_set = set(subset)
# Skip supersets of already found cuts
if any(set(cut).issubset(subset_set) for cut in minimal_cuts):
continue
# Remove edges from a copy of the undirected graph
H = G.copy()
H.delete_edges(subset)
if not H.is_connected():
# Get components
components = H.connected_components()
if len(components) != 2:
continue # Only consider binary cuts
from_set = set(components[0])
to_set = set(components[1])
# Classify directed edges in the subset
forward_cut = []
backward_cut = []
other = []
for (u, v) in subset:
if D.has_edge(u, v) and u in from_set and v in to_set:
forward_cut.append((u, v))
elif D.has_edge(u, v) and u in to_set and v in from_set:
backward_cut.append((u, v))
else:
other.append((u, v)) # not a valid directed edge
# Keep only pure forward or pure backward cuts
if len(forward_cut) == len(subset):
minimal_cuts.append(forward_cut)
elif len(backward_cut) == len(subset):
minimal_cuts.append(backward_cut)
return minimal_cuts
def find_dijoins(D):
"""
Finds all minimal-cardinality dijoins in a digraph D.
A dijoin is a set of edges that intersects all minimal directed cuts.
"""
E = set(D.edges(labels=False))
S = all_subsets(E)
C = [set(cut) for cut in directed_edge_cuts(D)]
L = []
Visited = []
for Si in S:
# Skip supersets already visited
if any(v.issubset(Si) for v in Visited):
continue
# Check if Si intersects all cuts
test = all(len(Si & c) > 0 for c in C)
if test:
L.append(Si)
Visited.append(Si)
# Convert to list for manipulation
L = [list(subset) for subset in L]
if not L:
return []
min_size = min(len(x) for x in L)
FinalList = [x for x in L if len(x) == min_size]
return FinalList
#############################################
# Build the directed graph
D = DiGraph([
(1,4), (1,5),
(2,4), (2,5), (2,6),
(3,4), (3,5), (3,6)
])
cuts = directed_edge_cuts(D)
# Print the minimal directed cuts
for i, cut in enumerate(cuts, 1):
print(f"Directed Cut {i}: {cut}")
# Find the minimal dijoins
dijoins = find_dijoins(D)
print("Minimal dijoins:")
for i, dj in enumerate(dijoins, 1):
print(f"Dijoin {i}: {dj}")
Question. This algorithm is quite slow; for example, it took about 30 minutes to process the following graph before I stopped it:
D = DiGraph([
(1,13), (1,14),
(2,13), (2,14), (2,15),
(3,10), (3,11), (3,12), (3,13), (3,14), (3,15), (3,17), (3,19), (3,20),
(4,10), (4,11), (4,12), (4,13), (4,14), (4,15), (4,17), (4,19), (4,20),
(5,19), (5,20),
(6,13), (6,14), (6,16), (6,18),
(7,10), (7,11), (7,12),
(8,13), (8,14), (8,16), (8,18),
])
Can the current implementation be significantly optimised to improve computational efficiency and runtime?
please fix indentation errors
The problem I have is that I cannot share link because I don't have enough karma :( In that case, I would share the link of SageCell. I'm really sorry for that