pedWorks.py 文件源码

def ped_sort(file):
    """
        - Reorders a pedigree (dict) by the Kahn's Algorithm.

     """
    pedgraph = input_diGraph(inFile=file)
    print "\n\tApplying Kahn's Algorithm... "
    in_degree = {u: 0 for u in pedgraph}  # determine in-degree
    for u in pedgraph:  # of each node
        for v in pedgraph[u]:
            in_degree[v] += 1

    Q = deque()  # collect nodes with zero in-degree
    for u in in_degree:
        if in_degree[u] == 0:
            Q.appendleft(u)

    order_list = []  # list for order of nodes

    while Q:
        u = Q.pop()  # choose node of zero in-degree
        order_list.append(u)  # and 'remove' it from graph
        for v in pedgraph[u]:
            in_degree[v] -= 1
            if in_degree[v] == 0:
                Q.appendleft(v)

    if len(order_list) == len(pedgraph):
        return order_list
    else:  # if there is a cycle,
        print "Error: At least one cycle detected!\n"
        return []  # return an empty list