Having an file with adjacency list of a 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 to get it's topological ordering, Graph G is a Directed Acyclic Graph.
First of all I want to parse the txt file and put all in a dictionary. However I am having some issues, first when reading the file I am missing something thatI miss first element after ->:
f = open('topo.txt', 'r')
line_list = f.readlines()
G = {int(line.split('->')[0]): [int(val) for val in line.split(',')[1:] if val] for line in line_list if line}
I would 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 I am missing one element, for instance 0 would be:
[13, 16, 20, 22, 4, 5] not [16, 20, 22, 4, 5] it misses the 13
Then when using the function dfs I get error:
for v in G[s]: # for every edge (s, v) KeyError: 16
"""Performs a depth first search in graph G starting from vertex s
Input: G - the input graph in the adjacency list representation via a dictionary
s - the starting vertex
explored - a set of explored vertices
distance - a dictionary representing the topological order of the vertices
current_label - the current order of the topological order, disguised as a mutable list"""
def dfs(G, s, explored, distance, current_label):
explored.add(s)
#print G[s]
for v in G[s]: # for 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 and outputs a topological sort of graph G using dfs
Input: G - the input graph in the adjacency list representation via a dictionary
distance - a dictionary representing the topological order of the vertices"""
def topological_sort(G, distance):
explored = set()
current_label = [len(G)]
for 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) for val in line.split(',')[1:] if val] for 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:")
for _, vertex in topo:
print( vertex + " ")
print()
if __name__ == '__main__':
main()
How would correct code look like? Output should be
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 the part 16,20,22,4,5 and that's not what you want. It should be line.split('->')[1].split(','). I, personally, would write this more explicitly to avoid the double .split('->') call:
def parse_graph(lines):
G = dict()
for line in lines:
left, right = line.split('->')
G[int(left)] = [int(val) for val in right.split(',')]
return G
...
G = parse_graph(line_list)
Next, since not every vertex is in G as a key you should add the following line in dfs:
#dfs
...
if s in G: #add this
for v in G[s]: # for every edge (s, v)
if v not in explored:
dfs(G, v, explored, distance, current_label, l)
...
#
Finally, change print( vertex + " ") to print( str(vertex), end=' '). The rest seems to be ok.
Another thing you might want to consider is instead of having to keep track of two parameters current_label, distance you could just keep one list vertices, lets say, which keeps an order of the visited vertices. So instead having
distance[current_label[0]] = s
current_label[0] -= 1
you could just have
vertices.append(s)
The effect is the same. At the end, however, you should print reversed(vertices) and this would be your topological order.