Lesson 8

The code below finds the maximum number of edge-disjoint paths from 1 to 0, and the minimum number of edges that must be removed to destroy all such paths. Internally, of course, it uses max-flow and min-cut algorithms.

import networkx as nx

g = nx.DiGraph([
    (1, 2), (2, 5), (5, 0), (2, 7), (2, 0), (1, 3),
    (3, 7), (7, 0), (1, 4), (3, 4), (1, 6), (4, 6),
    (4, 8), (6, 8), (6, 7), (8, 0)
])

print(list(nx.edge_disjoint_paths(g, 1, 0)))
print(nx.minimum_edge_cut(g, 1, 0))

[[1, 2, 0], [1, 3, 7, 0], [1, 4, 8, 0]]
{(1, 2), (8, 0), (7, 0)}