Advertisement
Guest User

Untitled

a guest
Nov 27th, 2015
73
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
text 1.52 KB | None | 0 0
  1. $ cat test.py
  2.  
  3. # http://stackoverflow.com/a/11564323
  4.  
  5. def topological_sort(source):
  6. """perform topo sort on elements.
  7.  
  8. :arg source: list of ``(name, [list of dependancies])`` pairs
  9. :returns: list of names, with dependancies listed first
  10. """
  11. pending = [(name, set(deps)) for name, deps in source] # copy deps so we can modify set in-place
  12. emitted = []
  13. while pending:
  14. next_pending = []
  15. next_emitted = []
  16. for entry in pending:
  17. name, deps = entry
  18. deps.difference_update(emitted) # remove deps we emitted last pass
  19. if deps: # still has deps? recheck during next pass
  20. next_pending.append(entry)
  21. else: # no more deps? time to emit
  22. yield name
  23. emitted.append(name) # <-- not required, but helps preserve original ordering
  24. next_emitted.append(name) # remember what we emitted for difference_update() in next pass
  25. if not next_emitted: # all entries have unmet deps, one of two things is wrong...
  26. raise ValueError("cyclic or missing dependancy detected: %r" % (next_pending,))
  27. pending = next_pending
  28. emitted = next_emitted
  29.  
  30.  
  31. # each named item can have a list of dependent items that need to start before it
  32. main = [
  33. ( "alfresco", ["skydock" ] ),
  34. ( "share", [ "alfresco" ] ),
  35. ( "solr", [ "share", "alfresco" ] ),
  36. ( "skydock", [] )
  37. ]
  38.  
  39. print main
  40.  
  41. s = topological_sort(main)
  42.  
  43. while True:
  44. print next(s)
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement