# -*- coding: UTF-8 -*-
#Maximum Flow Algorithm - Push Relabel Implementation
import doctest
def MaxFlow(C, s, t):
     """Return the max for a given network - takes input from the text file 
     
     >>> MaxFlow([[0,16,13,0,0,0],[0,0,0,12,0,0],[0,4,0,0,14,0],[0,0,9,0,0,20],[0,0,0,7,0,4],[0,0,0,0,0,0]],0,5)
     23
     
     >>> MaxFlow([[0,12,14,0,0,0],[0,0,0,3,0,0],[0,4,0,7,4,0],[0,0,0,0,0,6],[0,0,0,3,0,9],[0,0,0,0,0,0]],0,5)
     10
     
     >>> MaxFlow([[0,12,0,0,0,0],[0,0,0,3,0,0],[0,0,0,7,4,0],[0,0,0,0,0,6],[0,0,0,3,0,9],[0,0,0,0,0,0]],0,5)
     3
     
     >>> MaxFlow([[0,2,4,0,6,0],[0,1,0,3,0,5],[0,4,0,7,4,2],[0,0,0,0,0,6],[0,2,0,3,0,9],[0,0,0,0,0,0]],0,5)
     12
     
     >>> MaxFlow([[1,2,14,0,0,0],[10,0,2,3,0,0],[0,4,20,7,4,0],[0,20,0,0,0,6],[0,0,0,23,0,9],[0,0,0,0,0,0]],0,5)
     10
     
     """
     n = len(C) # C is the capacity matrix
     F = [[0] * n for i in xrange(n)]
     # the residual capacity from u to v is C[u][v] - F[u][v]
     height = [0] * n # height of node
     excess = [0] * n # flow into node minus flow from node
     seen   = [0] * n # neighbours seen since last relabel
     # node "queue"
     nodelist = [i for i in xrange(n) if i != s and i != t]
     #push operation
     def push(u, v):
         #print "Push Operation"
         send = min(excess[u], C[u][v] - F[u][v])
         F[u][v] += send
         F[v][u] -= send
         excess[u] -= send
         excess[v] += send
     #relabel operation
     def relabel(u):
         #print "Relabel Operation"
         # find smallest new height making a push possible,
         # if such a push is possible at all
         min_height = float('inf')
         for v in xrange(n):
             if C[u][v] - F[u][v] > 0:
                 min_height = min(min_height, height[v])
                 height[u] = min_height + 1 
     def discharge(u):
         while excess[u] > 0:
             if seen[u] < n: # check next neighbour
                 v = seen[u]
                 if C[u][v] - F[u][v] > 0 and height[u] > height[v]:
                     push(u, v)
                 else:
                     seen[u] += 1
             else: # we have checked all neighbours. must relabel
                 relabel(u)
                 seen[u] = 0 
     height[s] = n   # longest path from source to sink is less than n long
     excess[s] = float("inf") # send as much flow as possible to neighbours of source
     for v in xrange(n):
         push(s, v)
 
     p = 0
     while p < len(nodelist):
         u = nodelist[p]
         old_height = height[u]
         discharge(u)
         if height[u] > old_height:
             nodelist.insert(0, nodelist.pop(p)) # move to front of list
             p = 0 # start from front of list
         else:
             p += 1
     return sum(F[s])                                
var = raw_input("Please enter the filename: ")
nodes = raw_input("Number of nodes in the network: ")
j = 0
graph = [[] for i in range(int(nodes))]
with open(var,"r") as fh:
             for line in fh:
                 for i in line.split(' '):
                     graph[j].append(int(i.rstrip('\n')))
                 j=j+1 
                 
source = 0  
sink = len(graph) - 1    
max_flow_value = MaxFlow(graph, source, sink)
print "==================Push-Relabeled(Preflow-push) algorithm ================== "
print "Maximum Flow for the network is: ", max_flow_value
if __name__ == "__main__":
    doctest.testmod()