Pastebin is 300% more awesome when you are logged in. Sign Up, it's FREE!
Guest

top_sort.py

By: a guest on Nov 19th, 2010  |  syntax: Python  |  size: 1.95 KB  |  hits: 88  |  expires: Never
download  |  raw  |  embed  |  report abuse  |  print
Text below is selected. Please press Ctrl+C to copy to your clipboard. (⌘+C on Mac)
  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)