LatinRectangle.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 getPossibleNumbersForColumn(numbers,A,columnIndex):
 nRows=len(A)
 n=len(numbers)
 column=[A[row][columnIndex] for row in range(nRows)]
 possible=[n for n in numbers if not n in column]
 print('columnIndex: ',columnIndex,' column: ',column,' possible: ',possible)
 return possible

def isNewRowPerfectMatching(newRow,numbers):
 newRowSorted=sorted(newRow)
 return newRowSorted==numbers

def findNextRow(A,n):
 numbers=[i+1 for i in range(n)]
 L=['L'+str(i) for i in numbers]
 R=['R'+str(i) for i in numbers]
 source='SOURCE'
 sink='SINK'
 g=Graph(source,sink)
 for i in numbers:
  g.addEdge(Edge(source,L[i-1],1))
  g.addEdge(Edge(R[i-1],sink,1))
 for columnIndex in range(n):
  possibleNumbersForColumn=getPossibleNumbersForColumn(numbers,A,columnIndex)
  for p in possibleNumbersForColumn:
   g.addEdge(Edge(L[columnIndex],R[p-1],1))
 g.calculateMaxFlow()
 newRow=[0 for i in numbers]
 for edge in g.edges:
  if edge.v0[0]=='L' and edge.v1[0]=='R':
   iL=int(edge.v0[1:])
   iR=int(edge.v1[1:])
   if(edge.flowCapacity==0): newRow[iL-1]=numbers[iR-1]
 if not isNewRowPerfectMatching(newRow,numbers): return None
 return newRow

def printMatrix(A):
 for row in A:
  print(row)

def growMatrix(A,n):
 while True:
  print('Matrix:')
  printMatrix(A)
  newRow=findNextRow(A,n)
  if newRow==None: break
  print('New row: ',newRow)
  A.append(newRow)
 print('New row cannot be found.')

A=[[1,2,3,4,5],[2,3,4,5,1],[3,4,5,1,2]]
growMatrix(A,5)