Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- $ cat test.py
- # http://stackoverflow.com/a/11564323
- def topological_sort(source):
- """perform topo sort on elements.
- :arg source: list of ``(name, [list of dependancies])`` pairs
- :returns: list of names, with dependancies listed first
- """
- pending = [(name, set(deps)) for name, deps in source] # copy deps so we can modify set in-place
- emitted = []
- while pending:
- next_pending = []
- next_emitted = []
- for entry in pending:
- name, deps = entry
- deps.difference_update(emitted) # remove deps we emitted last pass
- if deps: # still has deps? recheck during next pass
- next_pending.append(entry)
- else: # no more deps? time to emit
- yield name
- emitted.append(name) # <-- not required, but helps preserve original ordering
- next_emitted.append(name) # remember what we emitted for difference_update() in next pass
- if not next_emitted: # all entries have unmet deps, one of two things is wrong...
- raise ValueError("cyclic or missing dependancy detected: %r" % (next_pending,))
- pending = next_pending
- emitted = next_emitted
- # each named item can have a list of dependent items that need to start before it
- main = [
- ( "alfresco", ["skydock" ] ),
- ( "share", [ "alfresco" ] ),
- ( "solr", [ "share", "alfresco" ] ),
- ( "skydock", [] )
- ]
- print main
- s = topological_sort(main)
- while True:
- print next(s)
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement