"""All Pairs Shortest Paths
"""

import matrix as matrix

def __special_matrix_multiply(A, B, infinity):
    n, m = matrix.get_dimensions(A)
    C = matrix.make(n,m)
    for i in xrange(n):
        for j in xrange(m):
            C[i][j] = infinity
            for k in xrange(n):
                x = A[i][k] + B[k][j]
                if x < C[i][j]:
                    C[i][j] = x
    return C

def all_pairs_shortest_paths(W, infinity):
    n = matrix.get_num_rows(W)
    D = W
    m = 1
    while m < n-1:
        D = __special_matrix_multiply(D, D, infinity)
        m = 2 * m
    return D
    
def floyd_warshall(W, infinity):
    n = matrix.get_num_rows(W)
    D = matrix.clone(W)
    DD = matrix.make(n,n)
    for k in xrange(n):
        for i in xrange(n):
            for j in xrange(n):
                DD[i][j] = min(D[i][j], D[i][k] + D[k][j])
        DD, D = D, DD
    return D

######################################################################
def test():
    V = [1,2,3,4]
    WE = [(1,2,5),
          (2,3,1),
          (3,1,8), (3,4,3),
          (4,1,2)]

    print """
    Initial Data
    """
    print "V =", V
    print "WE =", WE

    print """
    Determine safe infinity.  Safe infinity equals sum of all weights
    + 1.
    """
    infinity = 1
    for (u,v,w) in WE:
        infinity = infinity + w
    print "infinity =", infinity

    n = len(V)

    print """
    Original weights.
    """
    
    W = matrix.make(n, n, infinity)
    for (u,v,w) in WE:
        W[u-1][v-1] = w
    for i in xrange(n):
        W[i][i] = 0
    matrix.print_matrix(W, infinity)

    print """
    Repeated squaring
    """
    
    D = all_pairs_shortest_paths(W, infinity)
    matrix.print_matrix(D, infinity)

    print """
    Floyd-Warshall
    """

    D = floyd_warshall(W, infinity)
    matrix.print_matrix(D, infinity)
    


######################################################################
if __name__ == '__main__':
    test()

######################################################################