# 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 tryalgo.graph import add_reverse_arcs
    A = [0] * n               # A[v] = min residual cap. on path source->v
    augm_path = [None] * n    # None = node was not visited yet
    Q = deque()               # BFS
    Q.append(source)
    augm_path[source] = source
    A[source] = float('inf')
    while Q:
        u = Q.popleft()
        for v in graph[u]:
            cuv = capacity[u][v]
            residual = cuv - flow[u][v]
            if residual > 0 and augm_path[v] is None:
                augm_path[v] = u    # store predecessor
                A[v] = min(A[u], residual)
                if v == target:
                    break
                Q.append(v)
    return (augm_path, A[target])   # augmenting path, min residual cap.


def edmonds_karp(graph, capacity, source, target):
    """Maximum flow by Edmonds-Karp

    :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: flow matrix, flow value
    :complexity: :math:`O(|V|*|E|^2)`
    """

# 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/edmonds_karp.py
from collections import deque
from tryalgo.graph import add_reverse_arcs

    A = [0] * n               # A[v] = min residual cap. on path source->v
    augm_path = [None] * n    # None = node was not visited yet
    Q = deque()               # BFS
    Q.append(source)
    augm_path[source] = source
    A[source] = float('inf')
    while Q:
        u = Q.popleft()
        for v in graph[u]:
            cuv = capacity[u][v]
            residual = cuv - flow[u][v]
            if residual > 0 and augm_path[v] is None:
                augm_path[v] = u    # store predecessor
                A[v] = min(A[u], residual)
                if v == target:
                    break
                Q.append(v)
    return (augm_path, A[target])   # augmenting path, min residual cap.


def edmonds_karp(graph, capacity, source, target):
    """Maximum flow by Edmonds-Karp

    :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: flow matrix, flow value
    :complexity: :math:`O(|V|*|E|^2)`
    """

    add_reverse_arcs(graph, capacity)