Hungarian algorithm for perfect allocation - Python

import sys

class PerfectAllocation:
    def __init__(self, table):
        self.table = table
        self.zerorows = {}
        self.zerocolumns = {}
        self.matchingrows = {}
        self.matchingcolumns = {}
        self.N = len(table)
        self.rows = []
        self.columns = []
        for x in range(self.N):
            self.zerorows[x] = []
            self.zerocolumns[x] = []
            self.columns.append([])
        for x in range(self.N):
            self.rows.append(table[x][:])
            for y in range(self.N):
                self.columns[y].append(table[x][y])
                if table[x][y] == 0:
                    self.zerorows[x].append(y)
                    self.zerocolumns[y].append(x)


    def adjustCell(self, x,y,v):
        t = self.columns[x][y] + v
        self.columns[x][y] = t
        self.rows[y][x] = t
        if t == 0:
            self.zerorows[y].append(x)
            self.zerocolumns[x].append(y)
        elif t == v:
            self.zerorows[y].remove(x)
            self.zerocolumns[x].remove(y)

    def match(self, x, y):
        self.matchingrows[x] = y
        self.matchingcolumns[y] = x

    def unmatch(self, x, y):
        if self.matchingrows[x] == y:
            del self.mathingrows[x]
        if self.matchingcolumns[y] == x:
            del self.matchingcolumns[y]

    def step0(self): #reduce
        for x in range(self.N):
            a = min(self.rows[x])
            if a > 0:
                for i in range(self.N):
                    self.adjustCell(i, x, -a)

        for x in range(self.N):
            a = min(self.columns[x])
            if a > 0:
                for i in range(self.N):
                    self.adjustCell(x, i, -a)

    def step01(self): #initial_match
        for x in range(self.N):
            if x not in self.matchingrows:
                for y in self.zerorows[x]:
                    if y not in self.matchingcolumns:
                        self.match(x,y)
                        break

    def step1(self): #check if finished
        if len(self.matchingrows) == self.N:
            S = 0
            for x in self.matchingrows:
                S = S + self.table[x][self.matchingrows[x]]
            return True
        return False

    def step2(self): #iteratively improve graph
        def NextOption(x):
            R = self.zerorows[self.matchingcolumns[x]][:]
            R.remove(x)
            return R

        path = []
        Done = sys.maxint
        for x in self.zerorows:
            if x not in self.matchingrows:
                for y in self.zerorows[x]:
                    path.append([x, y])
                    if y not in self.matchingcolumns:
                        Done = 2
        thislevelnodes = []
        thislevel = 2
        while len(path) > 0 and Done > len(path[0]):
            x = path.pop(0)
            if len(x) > thislevel:
                thislevel += 1
                thislevelnodes = []
            nextx = NextOption(x[-1])
            t = 0
            while t <  len(nextx):
                if nextx[t] in thislevelnodes or nextx[t] in x[1:]:
                    nextx.pop(t)
                    continue
                else:
                    path.append(x[:] + [nextx[t]])
                    thislevelnodes.append(nextx[t])
                    if nextx[t] not in self.matchingcolumns:
                        Done = len(path[-1])
                t += 1

        duplR = []
        duplL = []

        if len(path) == 0:
            return False

        for x in path:
            if x[-1] in self.matchingcolumns:
                continue
            if x[0] in duplL:
                continue

            duplL.append(x[0])
            for t in range(1, len(x)):
                if x[t] not in duplR:
                    duplR.append(x[t])
                else:
                    break
            else:
                if len(x) > 2:
                    for t in range(len(x) - 1, 1, -1):
                        self.match(self.matchingcolumns[x[t-1]], x[t])
                        self.unmatch(self.matchingcolumns[x[t-1]], x[t-1])
                self.match(x[0], x[1])

        return True

    def step345(self):
        L = []
        OL = range(0, self.N)
        R = []
        UL = []
        UR = []

        for x in self.zerorows:
            if x not in self.matchingrows:
                L.append(x)
                OL.remove(x)
                UL.append(x)

        while len(UL) > 0:
            for x in UL:
                for y in self.zerorows[x]:
                    if y not in R:
                        R.append(y)
                        UR.append(y)
            UL = []
            for x in UR:
                if self.matchingcolumns[x] not in L:
                    L.append(self.matchingcolumns[x])
                    OL.remove(self.matchingcolumns[x])
                    UL.append(self.matchingcolumns[x])
            UR = []

        NL = L
        L = OL

        NR = [x for x in range(self.N) if x not in R]
        m = sys.maxint
        for x in NL:
            for y in NR:
                if self.rows[x][y] < m:
                    m = self.rows[x][y]
#                m = min(m, self.rows[x][y])
#                if m == None or self.rows[x][y] < m:
#                    m = self.rows[x][y]
        for x in L:
            for y in R:
                self.adjustCell(y, x, m)

        for x in NL:
            for y in NR:
                self.adjustCell(y, x, -m)

    def step6(self):
        s = 0
        for x in self.matchingrows:
            y = self.matchingrows[x]
            s += self.table[x][y]
        return s

    def solve(self):
        self.step0()
        self.step01()
        self.step1()
        while 1:
            while self.step2():
                if len(self.matchingrows) == self.N:
                    return self.step6()
            if len(self.matchingrows) == self.N:
                return self.step6()
            self.step345()