python - Get topological ordering of graph from Adjacency list -

having file adjacency list of graph g like:

0 -> 13,16,20,22,4,5 1 -> 12,13,16,17,19,22,23,24,25,3,4 10 -> 13,14,17,20,23,24 11 -> 12,19,20,22,23 12 -> 15,20,24 13 -> 20,21,22 15 -> 23 17 -> 25 19 -> 20,25 2 -> 16,19,3,7 20 -> 22,23 21 -> 22,23,24 22 -> 25 24 -> 25 3 -> 15,21,4 4 -> 10,12,14,15,16,17,18,19,21,23,5 5 -> 11,16,17,20,23,8,9 6 -> 12,14,18,22 7 -> 14,17,22 8 -> 21,24 9 -> 12,14 

i want it's topological ordering, graph g directed acyclic graph.

first of want parse txt file , put in dictionary. having issues, first when reading file missing thati miss first element after ->:

f = open('topo.txt', 'r')     line_list = f.readlines()     g = {int(line.split('->')[0]): [int(val) val in line.split(',')[1:] if val] line in line_list if line} 

i get:

('g:', {0: [16, 20, 22, 4, 5], 1: [13, 16, 17, 19, 22, 23, 24, 25, 3, 4], 2: [19, 3, 7], 3: [21, 4], 4: [12, 14, 15, 16, 17, 18, 19, 21, 23, 5], 5: [16, 17, 20, 23, 8, 9], 6: [14, 18, 22], 7: [17, 22], 8: [24], 9: [14], 10: [14, 17, 20, 23, 24], 11: [19, 20, 22, 23], 12: [20, 24], 13: [21, 22], 15: [], 17: [], 19: [25], 20: [23], 21: [23, 24], 22: [], 24: []}) [16, 20, 22, 4, 5] 

for each line missing 1 element, instance 0 be: [13, 16, 20, 22, 4, 5] not [16, 20, 22, 4, 5] misses 13

then when using function dfs error:

for v in g[s]: # every edge (s, v) keyerror: 16

"""performs depth first search in graph g starting vertex s     input: g - input graph in adjacency list representation via dictionary     s - starting vertex     explored - set of explored vertices     distance - dictionary representing topological order of vertices     current_label - current order of topological order, disguised mutable list""" def dfs(g, s, explored, distance, current_label):     explored.add(s)     #print g[s]     v in g[s]: # every edge (s, v)         if v not in explored:             dfs(g, v, explored, distance, current_label)     distance[current_label[0]] = s     current_label[0] -= 1  """performs , outputs topological sort of graph g using dfs     input: g - input graph in adjacency list representation via dictionary     distance - dictionary representing topological order of vertices""" def topological_sort(g, distance):     explored = set()     current_label = [len(g)]     v in g.keys():         if v not in explored:             dfs(g, v, explored, distance, current_label)  def main():     f = open('topo.txt', 'r')     line_list = f.readlines()     g = {int(line.split('->')[0]): [int(val) val in line.split(',')[1:] if val] line in line_list if line}     print("g:", g)     distance = dict()     topological_sort(g, distance)     topo = iter(sorted(distance.items()))     print("a topological order of g is:")     _, vertex in topo:         print( vertex + " ")     print()  if __name__ == '__main__':     main() 

how correct code like? output should

1, 0, 2, 6, 3, 7, 4, 5, 18, 10, 11, 16, 8, 9, 13, 17, 19, 12, 14, 21, 15, 20, 24, 23, 22, 25 

line.split(',')[1:] when run on 0 -> 13,16,20,22,4,5 takes part 16,20,22,4,5 , that's not want. should line.split('->')[1].split(','). i, personally, write more explicitly avoid double .split('->') call:

def parse_graph(lines):     g = dict()     line in lines:         left, right = line.split('->')         g[int(left)] = [int(val) val in right.split(',')]     return g ... g = parse_graph(line_list) 

next, since not every vertex in g key should add following line in dfs:

#dfs ... if s in g: #add     v in g[s]: # every edge (s, v)         if v not in explored:             dfs(g, v, explored, distance, current_label, l) ...  # 

finally, change print( vertex + " ") print( str(vertex), end=' '). rest seems ok.

another thing might want consider instead of having keep track of 2 parameters current_label, distance keep 1 list vertices, lets say, keeps order of visited vertices. instead having

distance[current_label[0]] = s current_label[0] -= 1 

you have

vertices.append(s) 

the effect same. @ end, however, should print reversed(vertices) , topological order.