# Path: pyalgs/algorithms/graphs/max_flow.py
# class FordFulkersonMaxFlow(object):
#     edgeTo = None
#     marked = None
#     s = None
#     t = None
#     value = 0.0
#     network = None
# 
#     def __init__(self, network, s, t):
#         self.s = s
#         self.t = t
#         self.network = network
#         self.value = 0.0
#         while self.has_augmenting_path():
#             x = self.t
#             bottle = float('inf')
#             while x != self.s:
#                 bottle = min(bottle, self.edgeTo[x].residual_capacity_to(x))
#                 x = self.edgeTo[x].other(x)
# 
#             x = self.t
#             while x != self.s:
#                 self.edgeTo[x].add_residual_flow_to(x, bottle)
#                 x = self.edgeTo[x].other(x)
# 
#             self.value += bottle
# 
#     def has_augmenting_path(self):
#         vertex_count = self.network.vertex_count()
#         self.edgeTo = [None] * vertex_count
#         self.marked = [False] * vertex_count
# 
#         queue = Queue.create()
# 
#         queue.enqueue(self.s)
#         self.marked[self.s] = True
# 
#         while not queue.is_empty():
#             x = queue.dequeue()
#             for e in self.network.adj(x):
#                 w = e.other(x)
#                 if e.residual_capacity_to(w) > 0:
#                     if not self.marked[w]:
#                         self.marked[w] = True
#                         self.edgeTo[w] = e
#                         queue.enqueue(w)
# 
#         return self.marked[self.t]
# 
#     def max_flow_value(self):
#         return self.value
# 
#     def min_cut(self):
#         queue = Queue.create()
#         for edge in self.network.edges():
#             if edge.residual_capacity_to(edge.end()) == 0:
#                 queue.enqueue(edge)
# 
#         return queue.iterate()
# 
# Path: tests/algorithms/graphs/util.py
# def create_flow_network():
#     g = FlowNetwork(8)
#     g.add_edge(FlowEdge(0, 1, 10))
#     g.add_edge(FlowEdge(0, 2, 5))
#     g.add_edge(FlowEdge(0, 3, 15))
#     g.add_edge(FlowEdge(1, 4, 9))
#     g.add_edge(FlowEdge(1, 5, 15))
#     g.add_edge(FlowEdge(1, 2, 4))
#     g.add_edge(FlowEdge(2, 5, 8))
#     g.add_edge(FlowEdge(2, 3, 4))
#     g.add_edge(FlowEdge(3, 6, 16))
#     g.add_edge(FlowEdge(4, 5, 15))
#     g.add_edge(FlowEdge(4, 7, 10))
#     g.add_edge(FlowEdge(5, 7, 10))
#     g.add_edge(FlowEdge(5, 6, 15))
#     g.add_edge(FlowEdge(6, 2, 6))
#     g.add_edge(FlowEdge(6, 7, 10))
# 
#     return g


import unittest
from pyalgs.algorithms.graphs.max_flow import FordFulkersonMaxFlow
from tests.algorithms.graphs.util import create_flow_network



class FordFulkersonMaxFlowUnitTest(unittest.TestCase):
    def test_max_flow(self):
        network = create_flow_network()

# Path: pyalgs/algorithms/graphs/max_flow.py
# class FordFulkersonMaxFlow(object):
#     edgeTo = None
#     marked = None
#     s = None
#     t = None
#     value = 0.0
#     network = None
# 
#     def __init__(self, network, s, t):
#         self.s = s
#         self.t = t
#         self.network = network
#         self.value = 0.0
#         while self.has_augmenting_path():
#             x = self.t
#             bottle = float('inf')
#             while x != self.s:
#                 bottle = min(bottle, self.edgeTo[x].residual_capacity_to(x))
#                 x = self.edgeTo[x].other(x)
# 
#             x = self.t
#             while x != self.s:
#                 self.edgeTo[x].add_residual_flow_to(x, bottle)
#                 x = self.edgeTo[x].other(x)
# 
#             self.value += bottle
# 
#     def has_augmenting_path(self):
#         vertex_count = self.network.vertex_count()
#         self.edgeTo = [None] * vertex_count
#         self.marked = [False] * vertex_count
# 
#         queue = Queue.create()
# 
#         queue.enqueue(self.s)
#         self.marked[self.s] = True
# 
#         while not queue.is_empty():
#             x = queue.dequeue()
#             for e in self.network.adj(x):
#                 w = e.other(x)
#                 if e.residual_capacity_to(w) > 0:
#                     if not self.marked[w]:
#                         self.marked[w] = True
#                         self.edgeTo[w] = e
#                         queue.enqueue(w)
# 
#         return self.marked[self.t]
# 
#     def max_flow_value(self):
#         return self.value
# 
#     def min_cut(self):
#         queue = Queue.create()
#         for edge in self.network.edges():
#             if edge.residual_capacity_to(edge.end()) == 0:
#                 queue.enqueue(edge)
# 
#         return queue.iterate()
# 
# Path: tests/algorithms/graphs/util.py
# def create_flow_network():
#     g = FlowNetwork(8)
#     g.add_edge(FlowEdge(0, 1, 10))
#     g.add_edge(FlowEdge(0, 2, 5))
#     g.add_edge(FlowEdge(0, 3, 15))
#     g.add_edge(FlowEdge(1, 4, 9))
#     g.add_edge(FlowEdge(1, 5, 15))
#     g.add_edge(FlowEdge(1, 2, 4))
#     g.add_edge(FlowEdge(2, 5, 8))
#     g.add_edge(FlowEdge(2, 3, 4))
#     g.add_edge(FlowEdge(3, 6, 16))
#     g.add_edge(FlowEdge(4, 5, 15))
#     g.add_edge(FlowEdge(4, 7, 10))
#     g.add_edge(FlowEdge(5, 7, 10))
#     g.add_edge(FlowEdge(5, 6, 15))
#     g.add_edge(FlowEdge(6, 2, 6))
#     g.add_edge(FlowEdge(6, 7, 10))
# 
#     return g


# Path: tests/algorithms/graphs/max_flow_unit_test.py
import unittest
from pyalgs.algorithms.graphs.max_flow import FordFulkersonMaxFlow
from tests.algorithms.graphs.util import create_flow_network




class FordFulkersonMaxFlowUnitTest(unittest.TestCase):
    def test_max_flow(self):
        network = create_flow_network()

        ff = FordFulkersonMaxFlow(network, 0, 7)