networking_flow.push_relabel

Push-relabel (Goldberg-Tarjan) algorithm for the maximum-flow problem.

The push-relabel method takes a very different approach from the augmenting-path algorithms in this directory (ford_fulkerson.py builds up a valid flow one path at a time). Instead it works with a preflow, in which a vertex may temporarily receive more flow than it sends out. Each active vertex either pushes its excess towards a neighbour that is one level lower, or is relabeled to a higher level so that a push becomes possible. When no vertex other than the source and sink has excess, the preflow has become a maximum flow.

Using the highest-label selection rule (always discharge an active vertex whose label is largest) this implementation runs in O(V^2 * sqrt(E)) time, which beats the augmenting-path methods on dense graphs.

Reference: https://en.wikipedia.org/wiki/Push%E2%80%93relabel_maximum_flow_algorithm

Classes

PushRelabel

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

Module Contents

class networking_flow.push_relabel.PushRelabel(vertices: int)

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

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

>>> g = PushRelabel(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

It agrees with the classic four-vertex example:

>>> h = PushRelabel(4)
>>> for (u, v), cap in {(0, 1): 3, (0, 2): 2, (1, 2): 5,
...                     (1, 3): 2, (2, 3): 3}.items():
...     h.add_edge(u, v, cap)
>>> h.max_flow(0, 3)
5

Parallel edges add up, and a disconnected sink gives zero flow:

>>> p = PushRelabel(2)
>>> p.add_edge(0, 1, 3)
>>> p.add_edge(0, 1, 5)
>>> p.max_flow(0, 1)
8
>>> PushRelabel(3).max_flow(0, 2)
0

_apply_pushes(u: int, height: list[int], excess: list[int]) → None

Push as much excess as possible from u along admissible edges.

_discharge(u: int, height: list[int]) → bool

Return True if u has at least one admissible outgoing edge.

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

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

>>> g = PushRelabel(2)
>>> g.add_edge(0, 1, -1)
Traceback (most recent call last):
    ...
ValueError: capacity must be non-negative
>>> g.add_edge(2, 0, 1)
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.

>>> PushRelabel(2).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