# 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 tryalgo.graph import add_reverse_arcs
# snip{
# pylint: disable=too-many-arguments
def _augment(graph, capacity, flow, val, u, target, visit):
    """Find an augmenting path from u to target with value at most val"""
    visit[u] = True
    if u == target:
        return val
    for v in graph[u]:
        cuv = capacity[u][v]
        if not visit[v] and cuv > flow[u][v]:  # reachable arc
            res = min(val, cuv - flow[u][v])
            delta = _augment(graph, capacity, flow, res, v, target, visit)
            if delta > 0:
                flow[u][v] += delta            # augment flow
                flow[v][u] -= delta
                return delta
    return 0


def ford_fulkerson(graph, capacity, s, t):
    """Maximum flow by Ford-Fulkerson

    :param graph: directed graph in listlist or listdict format
    :param capacity: in matrix format or same listdict graph
    :param int s: source vertex
    :param int t: target vertex

    :returns: flow matrix, flow value
    :complexity: `O(|V|*|E|*max_capacity)`
    """

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

# snip{
# pylint: disable=too-many-arguments
def _augment(graph, capacity, flow, val, u, target, visit):
    """Find an augmenting path from u to target with value at most val"""
    visit[u] = True
    if u == target:
        return val
    for v in graph[u]:
        cuv = capacity[u][v]
        if not visit[v] and cuv > flow[u][v]:  # reachable arc
            res = min(val, cuv - flow[u][v])
            delta = _augment(graph, capacity, flow, res, v, target, visit)
            if delta > 0:
                flow[u][v] += delta            # augment flow
                flow[v][u] -= delta
                return delta
    return 0


def ford_fulkerson(graph, capacity, s, t):
    """Maximum flow by Ford-Fulkerson

    :param graph: directed graph in listlist or listdict format
    :param capacity: in matrix format or same listdict graph
    :param int s: source vertex
    :param int t: target vertex

    :returns: flow matrix, flow value
    :complexity: `O(|V|*|E|*max_capacity)`
    """

    add_reverse_arcs(graph, capacity)