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
评论列表
文章目录