Hasse Matrix with Path Recovery

hasse.py

# coding=utf-8

def hedetniemi(A, B):
    return [[min(A[i][k] + B[k][j] for k in range(len(A))) for j in range(len(A))] for i in range(len(A))]

def hasse(D, k):
    return reduce(hedetniemi, [D]*(k - 1), D)

def hasse_recovery(D, k):
    if k == 1:
        return [range(len(D)) for row in D]
    D_prev = hasse(D, k - 1)
    D_next = hedetniemi(D_prev, D)
    R_prev = hasse_recovery(D, k - 1)
    R_next = [[min((D_prev[i][k] + D[k][j], k) for k in range(len(D)))[1] if D_prev[i][j] != D_next[i][j] else R_prev[i][j] for j in range(len(D))] for i in range(len(D))]
    return R_next

# Example program below
if __name__ == "__main__":
    
    inf = 0xDEADBEEF

    def print_matrix(M, offset=0, spacing=3):
        for row in M:
            for col in row:
                # print col, 
                print (" "*(spacing - 1) + "∞") if col == inf else ("%" + str(spacing) + "d") % (col + offset),
            print ""
        print ""

    D = [[0, 5, 3, inf, inf, inf, inf],
         [5, 0, 1, 5, 2, inf, inf],
         [3, 1, 0, 7, inf, inf, 12],
         [inf, 5, 7, 0, 3, inf, 3],
         [inf, 2, inf, 3, 0, 1, inf],
         [inf, inf, inf, 1, 1, 0, inf],
         [inf, inf, 12, 3, inf, 4, 0]]

    for k in range(1, len(D)):
        print "D(%d)" % k
        print_matrix(hasse(D, k))

        print "R(%d)" % k
        print_matrix(hasse_recovery(D, k), offset=1)