constraints.py 文件源码

def difference_constraints_without_aux_vertex(A, b):
    row = len(A)
    col = len(A[0])
    vertices_num = col
    vertices = []
    edges = []
    weights = dict()
    for i in range(vertices_num):
        vertices.append(Vertex(i + 1))
    for i in range(0, row):
        u = A[i].index(-1)        
        v = A[i].index(1)        
        edges.append((vertices[u], vertices[v]))
        weights[(vertices[u], vertices[v])] = b[i]
    G = Graph(vertices, edges)
    if Bellman_Ford_without_aux_vertex(G, lambda x, y: weights[(x, y)]):
        return [v.d for v in vertices]
    else:
        return None