# Path: tryalgo/graph.py
# def add_reverse_arcs(graph, capac=None):
#     """Utility function for flow algorithms that need for every arc (u,v),
#     the existence of an (v,u) arc, by default with zero capacity.
#     graph can be in adjacency list, possibly with capacity matrix capac.
#     or graph can be in adjacency dictionary, then capac parameter is ignored.
# 
#     :param capac: arc capacity matrix
#     :param graph: in listlist representation, or in listdict representation,
#     in this case capac is ignored
#     :complexity: linear
#     :returns: nothing, but graph is modified
#     """
#     for u, _ in enumerate(graph):
#         for v in graph[u]:
#             if u not in graph[v]:
#                 if type(graph[v]) is list:
#                     graph[v].append(u)
#                     if capac:
#                         capac[v][u] = 0
#                 else:
#                     assert type(graph[v]) is dict
#                     graph[v][u] = 0


from collections import deque
from sys import setrecursionlimit
from tryalgo.graph import add_reverse_arcs
#!/usr/bin/env python3
# -*- coding: utf-8 -*-
"""\
Maximum flow by Dinic
jill-jênn vie et christoph dürr - 2015-2018
"""



setrecursionlimit(5010)  # necessary for big graphs


# snip{
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

# Path: tryalgo/graph.py
# def add_reverse_arcs(graph, capac=None):
#     """Utility function for flow algorithms that need for every arc (u,v),
#     the existence of an (v,u) arc, by default with zero capacity.
#     graph can be in adjacency list, possibly with capacity matrix capac.
#     or graph can be in adjacency dictionary, then capac parameter is ignored.
# 
#     :param capac: arc capacity matrix
#     :param graph: in listlist representation, or in listdict representation,
#     in this case capac is ignored
#     :complexity: linear
#     :returns: nothing, but graph is modified
#     """
#     for u, _ in enumerate(graph):
#         for v in graph[u]:
#             if u not in graph[v]:
#                 if type(graph[v]) is list:
#                     graph[v].append(u)
#                     if capac:
#                         capac[v][u] = 0
#                 else:
#                     assert type(graph[v]) is dict
#                     graph[v][u] = 0


# Path: tryalgo/dinic.py
from collections import deque
from sys import setrecursionlimit
from tryalgo.graph import add_reverse_arcs

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



setrecursionlimit(5010)  # necessary for big graphs


# snip{
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)