Skip to content

Instantly share code, notes, and snippets.

@andrewgodwin
Created November 15, 2014 12:53
Show Gist options
  • Save andrewgodwin/5fb29282a3f582f4e437 to your computer and use it in GitHub Desktop.
Save andrewgodwin/5fb29282a3f582f4e437 to your computer and use it in GitHub Desktop.
from collections import deque
def dependency_sort(initial, dependency_func):
"""
Generic dependency sorting algorithm; supply an initial list of IDs as
"initial", and a callable that takes an ID and returns a list of IDs as
"dependencies".
The resultant list is in order from leaf nodes (no dependencies) to stems.
"""
# Turn the dependencies into a mapping of all nodes to their deps
dependencies = list(initial)
pending = deque(initial)
mapping = {}
while pending:
current = pending.popleft()
mapping[current] = [x for x in dependency_func(current) if x is not None]
for dependency in mapping[current]:
if dependency not in pending and dependency not in mapping:
pending.append(dependency)
# Build a sorted list based on that
result = []
while mapping:
len_before = len(mapping)
for node, dependencies in sorted(mapping.items()):
if not dependencies or all((dependency in result) for dependency in dependencies):
result.append(node)
del mapping[node]
if len(mapping) == len_before:
raise ValueError("Circular dependency: %s" % mapping.keys())
return result
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment