# top_sort.py

a guest
Nov 19th, 2010
131
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
1. #!/usr/bin/env python2.6
2. """
3. top_sort.py
4.
5. We implement a topological sort of a directed acyclic graph (DAG) G, implemented
6. as a dictionary of edge lists. We first check if G is acyclic, then sort it if
7. so. I got some help from Wikipedia
8. (http://en.wikipedia.org/wiki/Topological_sorting), CLRS3e, and the original
9. blog post.
10.
11. http://programmingpraxis.com/2010/11/19/topological-sort/
12.
13. GRE, 11/19/10
14. """
15.
16. from copy import deepcopy
17.
18. def predless_nodes(G):
19. # Nodes without a predecessor
20.     S = G.keys()
21.     for n in G:
22.         for m in G[n]:
23.             if m in S: S.remove(m)
24.     return S
25.
26. def leaves(G):
27. # Nodes with no sucessor
28.     return [n for n in G if G[n] == []]
29.
30. def is_cyclic(G):
31. # Uses the algorithm described in the blog post for determining if G is cyclic
32.     L = leaves(G)
33.     if len(G) == 0:
34.         return False
35.     elif len(L) == 0:
36.         return True
37.     else:
38.         for l in L:
39.             for n in G.iterkeys():
40.                 if l in G[n]:
41.                     G[n].remove(l)
42.             G.pop(l)
43.         return is_cyclic(G)
44.
45. def topological_sort(G):
46. # Uses depth-first search from CLRS3e and Wikipedia
47.     if is_cyclic(deepcopy(G)):      # deepcopy or else we lose G
48.         return "Error! G was cyclic."
49.     v = dict.fromkeys(G)
50.     T = []
51.     S = predless_nodes(G)
52. # Define depth-first search
53.     def visit(n):
54.         if not v[n]:
55.             v[n] = True
56.             for m in G[n]:
57.                 visit(m)
58.             T.insert(0,n)
59.         return
60. # Execute depth-first search
61.     for n in S:
62.         visit(n)
63.     return T
64.
65.
66. if __name__ == '__main__':
67.     def tester(G):
68.         print "Graph:\n%s" % G
69.         print "A topological sort of this graph:\n%s" % topological_sort(G)
70.         return
71.
72.     G1 = {2:[], 3:[8, 10], 5:[11], 7:[8,11], 8:[9], 9:[], 10:[], 11:[2, 9, 10]}
73.     tester(G1)
74.     G2 = {2:[], 3:[8, 10], 5:[11], 7:[8,11], 8:[9], 9:[], 10:[5], 11:[2, 9, 10]}
75.     tester(G2)