networking_flow.dinic

Dinic’s algorithm for the maximum-flow problem.

Dinic’s algorithm repeatedly builds a level graph with a breadth-first search (shortest augmenting paths, measured in edges) and then, in one pass, saturates a blocking flow on that level graph using depth-first search. Grouping the augmenting paths by length this way gives a much better worst case than the plain Ford-Fulkerson / Edmonds-Karp augmenting-path method:

• Dinic’s algorithm: O(V^2 * E)

• on unit-capacity networks: O(E * sqrt(V))

Unlike the adjacency-matrix implementations in ford_fulkerson.py and minimum_cut.py in this directory, this version stores the graph as an adjacency list of residual edges, so it also handles graphs with parallel edges and is efficient on sparse graphs.

Reference: https://en.wikipedia.org/wiki/Dinic%27s_algorithm

Classes

Dinic

Maximum flow in a directed graph with non-negative integer capacities.

Module Contents

class networking_flow.dinic.Dinic(vertices: int)

Maximum flow in a directed graph with non-negative integer capacities.

Add edges with add_edge(), then call max_flow().

>>> g = Dinic(6)
>>> capacities = {
...     (0, 1): 16, (0, 2): 13, (1, 2): 10, (1, 3): 12,
...     (2, 1): 4, (2, 4): 14, (3, 2): 9, (3, 5): 20,
...     (4, 3): 7, (4, 5): 4,
... }
>>> for (u, v), cap in capacities.items():
...     g.add_edge(u, v, cap)
>>> g.max_flow(0, 5)
23

A source with no outgoing edges (or a sink with no incoming edges) has zero maximum flow:

>>> Dinic(3).max_flow(0, 2)
0

Parallel edges between the same pair of vertices are supported and their capacities add up:

>>> h = Dinic(2)
>>> h.add_edge(0, 1, 3)
>>> h.add_edge(0, 1, 5)
>>> h.max_flow(0, 1)
8

_build_level_graph(source: int) → list[int]

Breadth-first search; return per-vertex levels (-1 if unreachable).

_send_flow(vertex: int, pushed: int, sink: int, level: list[int], progress: list[int]) → int

Depth-first search that pushes a blocking flow along the level graph.

add_edge(source: int, destination: int, capacity: int) → None

Add a directed edge source -> destination with the given capacity.

>>> g = Dinic(2)
>>> g.add_edge(0, 1, 5)
>>> g.add_edge(0, 1, -1)
Traceback (most recent call last):
    ...
ValueError: capacity must be non-negative
>>> g.add_edge(0, 2, 5)
Traceback (most recent call last):
    ...
ValueError: vertex out of range

max_flow(source: int, sink: int) → int

Return the maximum flow from source to sink.

>>> g = Dinic(4)
>>> for (u, v), cap in {(0, 1): 3, (0, 2): 2, (1, 2): 5,
...                     (1, 3): 2, (2, 3): 3}.items():
...     g.add_edge(u, v, cap)
>>> g.max_flow(0, 3)
5
>>> g.max_flow(0, 0)
Traceback (most recent call last):
    ...
ValueError: source and sink must be different

edges: list[list[int]] = []

graph: list[list[int]]

size