EdmondsKarp2.py

class Edge:
 def __init__(self,v0,v1,capacity):
  self.v0=v0
  self.v1=v1
  self.initialCapacity=capacity
  self.flowCapacity=capacity
  self.backFlowCapacity=0
 def __str__(self):
  s=self.v0+'->'+self.v1+' ('+str(self.flowCapacity)+'/'+str(self.initialCapacity)+') '
  s+=self.v0+'<-'+self.v1+' ('+str(self.backFlowCapacity)+'/'+str(self.initialCapacity)+')'
  return s

class Graph:
 def __init__(self,source,sink):
  self.source=source
  self.sink=sink
  self.edges=[]
 def addEdge(self,edge):
  self.edges.append(edge)
 def findVertex(self,vertex):
  edgeList=[]
  for edge in self.edges:
   if edge.v0==vertex and edge.flowCapacity>0:
    edgeList.append(edge)
   if edge.v1==vertex and edge.backFlowCapacity>0:
    edgeList.append(edge)
  return edgeList
 def calculateMaxFlow(self):
  iteration=0
  while True:
   iteration+=1
   print('Iteration: '+str(iteration))
   print(str(self))
   shortestPath=findShortestPathBFS(self)
   if shortestPath==None: break
   self.calculateResidualGraph(shortestPath)
 def calculateResidualGraph(self,shortestPath):
  current=self.source
  pf=getPossibleFlowOfPath(self,shortestPath)
  for edge in shortestPath:
   if current==edge.v0:
    edge.flowCapacity-=pf
    edge.backFlowCapacity+=pf
   else:
    edge.backFlowCapacity-=pf
    edge.flowCapacity+=pf
   current=getNextVertex(current,edge)
 def __str__(self):
  s='Graph: '
  for e in self.edges:
   s+=str(e)+' '
  return s

def getNextVertex(vertex,edge):
 return edge.v1 if vertex==edge.v0 else edge.v0

def isNotVisited(vertex,visited):
 for v in visited:
  if vertex==v[0]: return False
 return True

def getPossibleFlowOfEdge(vertex,edge):
 return edge.flowCapacity if vertex==edge.v0 else edge.backFlowCapacity

def getPossibleFlowOfPath(graph,path):
 vertex=graph.source
 possibleFlow=float('inf')
 for edge in path:
  pf=getPossibleFlowOfEdge(vertex,edge)
  if pf<possibleFlow:
   possibleFlow=pf
  vertex=getNextVertex(vertex,edge)
 return possibleFlow

def findShortestPathBFS(graph):
 current=(graph.source,[])
 fringe=[]
 visited=[]
 while True:
  neighborEdges=graph.findVertex(current[0])
  for ne in neighborEdges:
   nextVertex=getNextVertex(current[0],ne)
   if isNotVisited(nextVertex,visited):
    fringe.append((nextVertex,current[1]+[ne]))
  visited.append(current)
  if len(fringe)==0: break
  current=fringe[0]
  fringe=fringe[1:]
 shortestPaths=[v[1] for v in visited if v[0]==graph.sink]
 if len(shortestPaths)==0: return None
 shortestPath=shortestPaths[0]
 for path in shortestPaths[1:]:
  if len(path)<len(shortestPath):
   shortestPath=path
  else:
   if len(path)==len(shortestPath):
    if getPossibleFlowOfPath(graph,path)>getPossibleFlowOfPath(graph,shortestPath):
     shortestPath=path
 return shortestPath

def findMatrix(R,C,k):
 if sum(R)!=k or sum(C)!=k: return None
 nR=len(R)
 nC=len(C)
 g=Graph('source','sink')
 for iR in range(nR):
  g.addEdge(Edge('source','R'+str(iR),R[iR]))
 for iC in range(nC):
  g.addEdge(Edge('C'+str(iC),'sink',C[iC]))
 for iR in range(nR):
  for iC in range(nC):
   g.addEdge(Edge('R'+str(iR),'C'+str(iC),1))
 g.calculateMaxFlow()
 A=[[0 for iR in range(nR)] for iC in range(nC)]
 for edge in g.edges:
  if edge.v0[0]=='R' and edge.v1[0]=='C':
   iR=int(edge.v0[1:])
   iC=int(edge.v1[1:])
   A[iC][iR]=1 if edge.flowCapacity==0 else 0
 return A

A=findMatrix([1,3,2],[2,3,0,1],6)
for row in A:
 print(row)