# 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

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
Q = deque()
total = 0
n = len(graph)
flow = [ * 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}