Revision history [back]
 | 1 | initial version |
Consider the following method that uses integer linear programming to enumerate the minimal directed cuts.
def directed_edge_cuts_MIP(D):
r"""
Return an iterator over the directed cuts of ``D``.
This method uses mixed integer linear programming to enumerate the
minimal directed cuts of ``D``.
"""
int_to_vertex = list(D)
vertex_to_int = {u: i for i, u in enumerate(int_to_vertex)}
H = D.relabel(perm=vertex_to_int, inplace=False)
def good_edges(edges):
return [(int_to_vertex[u], int_to_vertex[v]) for u, v in edges]
def hedge(u, v):
return (u, v) if u < v else (v, u)
from sage.numerical.mip import MixedIntegerLinearProgram
p = MixedIntegerLinearProgram(constraint_generation=True, maximization=False)
x = p.new_variable(binary=True)
y = p.new_variable(binary=True)
z = p.new_variable(binary=True)
# At least one vertex must be 0 and at least one 1
p.add_constraint(p.sum(x[u] for u in H), min=1, max=H.order() - 1)
# underlying edge (u, v) is in the cut if u != v
for u, v in H.edge_iterator(labels=False):
p.add_constraint(x[v] - x[u] <= y[hedge(u, v)])
p.add_constraint(x[u] - x[v] <= y[hedge(u, v)])
# an edge of H is in the cut iff x[u] == 0 and x[v] == 1
for u, v in H.edge_iterator(labels=False):
p.add_constraint(x[v] - x[u] <= z[u, v])
p.add_constraint(z[u, v] <= x[v])
p.add_constraint(z[u, v] <= 1 - x[u])
p.add_constraint(y[hedge(u,v)] <= z[u, v])
p.set_objective(p.sum(z[u, v] for u, v in H.edge_iterator(labels=False)))
# get trivial cuts when a vertex has no incoming or outgoing edge
for u in H:
cut = []
if not H.in_degree(u):
cut = H.outgoing_edges(u, labels=False)
elif not H.out_degree(u):
cut = H.incoming_edges(u, labels=False)
if cut:
# yield the cut
yield good_edges(cut)
# and add a constraint to prevent finding it again
p.add_constraint(p.sum(z[u, v] for u, v in cut) <= len(cut) - 1)
# Now search for non trivial cuts
while True:
try:
p.solve()
except:
# no more solution
return
# Extract the cut
zz = p.get_values(z, convert=bool, tolerance=1e-3)
cut = [e for e, b in zz.items() if b]
# yield it
yield good_edges(cut)
# and add a constraint to prevent finding it again
p.add_constraint(p.sum(z[u, v] for u, v in cut) <= len(cut) - 1)
return
We can use a frontend method that exploits the digraph of the strongly connected components. Recall that we cannot find a directed cut in a strongly connected graph.
def directed_edge_cuts(D):
r"""
Return an iterator over the minimal directed edge cuts of ``D``.
"""
H = D.strongly_connected_components_digraph()
def good_cut(cut):
"""
Turn a cut in H to a cut in D
"""
return [e for u, v in cut for e in D.edge_boundary(u, v, labels=False)]
# We compute the 2 edge-connected components of the underlying graph
# Each block of order 2 corresponds to a minimal directed cut in D
for block in H.blocks_and_cut_vertices()[0]:
if len(block) == 2:
u, v = block
if not H.has_edge(u, v):
u, v = v, u
# yield the cut and remove it from H
yield good_cut([(u, v)])
H.delete_edge(u, v)
# We now search for cuts in the connected components
for g in H.connected_components_subgraphs():
if g.order() > 1:
for cut in directed_edge_cuts_MIP(g):
yield good_cut(cut)
To get the dijoins, we can also use integer linear programming.
def dijoins(D):
r"""
Return an iterator over the minimal cardinality dijoins in ``D``.
A dijoin is a set of edges that intersects all minimal directed cuts.
"""
from sage.numerical.mip import MixedIntegerLinearProgram
p = MixedIntegerLinearProgram(constraint_generation=True, maximization=False)
x = p.new_variable(binary=True)
# A dijoin contains at least one edge per cut
for cut in directed_edge_cuts(D):
p.add_constraint(p.sum(x[e] for e in cut), min=1)
p.set_objective(p.sum(x[e] for e in D.edge_iterator(labels=False)))
size = 0
while True:
try:
p.solve()
except:
return
# Extract the dijoin
xx = p.get_values(x, convert=bool, tolerance=1e-3)
dijoin = [e for e, b in xx.items() if b]
if not size:
size = len(dijoin)
elif size < len(dijoin):
# no more minimal cardinality dijoin
return
# yield it
yield dijoin
# and add a constraint to prevent finding it again
p.add_constraint(p.sum(x[e] for e in dijoin) <= len(dijoin) - 1)
return
all these methods are iterators.
sage: D = DiGraph([
....: (1,4), (1,5),
....: (2,4), (2,5), (2,6),
....: (3,4), (3,5), (3,6)
....: ])
sage: print("Minimal directed cuts:")
....: for i, cut in enumerate(directed_edge_cuts(D), 1):
....: print(f"Directed Cut {i}: {cut}")
Minimal directed cuts:
Directed Cut 1: [(3, 5), (2, 5), (1, 5)]
Directed Cut 2: [(3, 5), (3, 6), (3, 4)]
Directed Cut 3: [(3, 6), (2, 6)]
Directed Cut 4: [(2, 5), (2, 6), (2, 4)]
Directed Cut 5: [(3, 4), (2, 4), (1, 4)]
Directed Cut 6: [(1, 5), (1, 4)]
Directed Cut 7: [(3, 5), (3, 4), (2, 5), (2, 4)]
sage: print("Minimal dijoins:")
....: for i, dj in enumerate(dijoins(D), 1):
....: print(f"Dijoin {i}: {dj}")
Minimal dijoins:
Dijoin 1: [(3, 5), (2, 6), (1, 4)]
Dijoin 2: [(1, 5), (3, 4), (2, 6)]
Dijoin 3: [(2, 5), (3, 6), (1, 4)]
Dijoin 4: [(1, 5), (3, 6), (2, 4)]
This is consistent with your solutions. I let you check the next example.
sage: 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),
....: ])
sage: print("Minimal directed cuts:")
....: for i, cut in enumerate(directed_edge_cuts(D), 1):
....: print(f"Directed Cut {i}: {cut}")
....:
Minimal directed cuts:
Directed Cut 1: [(6, 13), (2, 13), (1, 13), (8, 13), (4, 13), (3, 13)]
Directed Cut 2: [(6, 13), (6, 16), (6, 18), (6, 14)]
Directed Cut 3: [(6, 16), (8, 16)]
Directed Cut 4: [(8, 13), (8, 16), (8, 18), (8, 14)]
Directed Cut 5: [(6, 18), (8, 18)]
Directed Cut 6: [(6, 14), (2, 14), (1, 14), (8, 14), (4, 14), (3, 14)]
Directed Cut 7: [(4, 13), (4, 15), (4, 14), (4, 10), (4, 11), (4, 12), (4, 17), (4, 20), (4, 19)]
Directed Cut 8: [(4, 10), (3, 10), (7, 10)]
Directed Cut 9: [(3, 13), (3, 15), (3, 14), (3, 10), (3, 11), (3, 12), (3, 17), (3, 20), (3, 19)]
Directed Cut 10: [(4, 11), (3, 11), (7, 11)]
Directed Cut 11: [(7, 10), (7, 11), (7, 12)]
Directed Cut 12: [(4, 12), (3, 12), (7, 12)]
Directed Cut 13: [(4, 17), (3, 17)]
Directed Cut 14: [(4, 20), (3, 20), (5, 20)]
Directed Cut 15: [(5, 20), (5, 19)]
Directed Cut 16: [(4, 19), (3, 19), (5, 19)]
Directed Cut 17: [(2, 15), (4, 15), (3, 15)]
Directed Cut 18: [(2, 13), (2, 15), (2, 14)]
Directed Cut 19: [(1, 13), (1, 14)]
Directed Cut 20: [(4, 20), (4, 19), (3, 20), (3, 19)]
Directed Cut 21: [(6, 13), (6, 14), (8, 13), (8, 14)]
Directed Cut 22: [(4, 13), (4, 15), (4, 14), (3, 13), (3, 15), (3, 14)]
Directed Cut 23: [(4, 13), (4, 14), (3, 13), (3, 14), (2, 13), (2, 14)]
Directed Cut 24: [(4, 10), (4, 11), (4, 12), (3, 10), (3, 11), (3, 12)]
sage: %time A = list(directed_edge_cuts(D))
CPU times: user 48.2 ms, sys: 1.88 ms, total: 50.1 ms
Wall time: 48.5 ms
sage:
sage: print("Minimal dijoins:")
....: for i, dj in enumerate(dijoins(D), 1):
....: print(f"Dijoin {i}: {dj}")
....:
Minimal dijoins:
Dijoin 1: [(1, 13), (4, 13), (6, 18), (6, 14), (8, 16), (4, 12), (4, 17), (4, 20), (3, 10), (7, 11), (5, 19), (2, 15)]
Dijoin 2: [(1, 13), (4, 13), (6, 18), (6, 14), (8, 16), (4, 12), (4, 20), (3, 10), (3, 17), (7, 11), (5, 19), (2, 15)]
Dijoin 3: [(6, 13), (4, 13), (6, 18), (8, 16), (1, 14), (4, 12), (4, 17), (4, 20), (3, 10), (7, 11), (5, 19), (2, 15)]
Dijoin 4: [(6, 13), (4, 13), (6, 16), (8, 18), (1, 14), (4, 12), (4, 17), (4, 20), (3, 10), (7, 11), (5, 19), (2, 15)]
Dijoin 5: [(6, 13), (4, 13), (6, 16), (8, 18), (1, 14), (4, 12), (4, 17), (4, 20), (7, 10), (3, 11), (5, 19), (2, 15)]
Dijoin 6: [(6, 13), (4, 13), (6, 18), (8, 16), (1, 14), (4, 12), (4, 20), (3, 10), (3, 17), (7, 11), (5, 19), (2, 15)]
Dijoin 7: [(6, 13), (4, 13), (6, 16), (8, 18), (1, 14), (4, 12), (4, 20), (3, 10), (3, 17), (7, 11), (5, 19), (2, 15)]
Dijoin 8: [(6, 13), (4, 13), (6, 16), (8, 18), (1, 14), (4, 10), (4, 12), (4, 20), (3, 17), (7, 11), (5, 19), (2, 15)]
Dijoin 9: [(6, 13), (4, 13), (6, 16), (8, 18), (1, 14), (4, 10), (4, 11), (4, 20), (3, 17), (7, 12), (5, 19), (2, 15)]
Dijoin 10: [(2, 13), (1, 13), (6, 18), (6, 14), (8, 16), (4, 15), (4, 12), (4, 17), (4, 20), (3, 10), (7, 11), (5, 19)]
.....
I don't know how many dijoins we get for this graph. It's a large number...
