Source code for tryalgo.dinic

#!/usr/bin/env python3
# -*- coding: utf-8 -*-
"""\
Maximum flow by Dinic
jill-jênn vie et christoph dürr - 2015-2018
"""

from collections import deque
from sys import setrecursionlimit
from tryalgo.graph import add_reverse_arcs


setrecursionlimit(5010)  # necessary for big graphs


# snip{
[docs]def dinic(graph, capacity, source, target): """Maximum flow by Dinic :param graph: directed graph in listlist or listdict format :param capacity: in matrix format or same listdict graph :param int source: vertex :param int target: vertex :returns: skew symmetric flow matrix, flow value :complexity: :math:`O(|V|^2 |E|)` """ assert source != target add_reverse_arcs(graph, capacity) Q = deque() total = 0 n = len(graph) flow = [[0] * n for u in range(n)] # flow initially empty while True: # repeat while we can increase Q.appendleft(source) level = [None] * n # build levels, None = inaccessible level[source] = 0 # by BFS while Q: u = Q.pop() for v in graph[u]: if level[v] is None and capacity[u][v] > flow[u][v]: level[v] = level[u] + 1 Q.appendleft(v) if level[target] is None: # stop if sink is not reachable return flow, total up_bound = sum(capacity[source][v] for v in graph[source]) - total total += _dinic_step(graph, capacity, level, flow, source, target, up_bound)
# pylint: disable=too-many-arguments def _dinic_step(graph, capacity, level, flow, u, target, limit): """ tenter de pousser le plus de flot de u à target, sans dépasser limit """ if limit <= 0: return 0 if u == target: return limit val = 0 for v in graph[u]: residual = capacity[u][v] - flow[u][v] if level[v] == level[u] + 1 and residual > 0: z = min(limit, residual) aug = _dinic_step(graph, capacity, level, flow, v, target, z) flow[u][v] += aug flow[v][u] -= aug val += aug limit -= aug if val == 0: level[u] = None # remove unreachable node return val # snip}