How to sort based on dependencies?

Question

I have an class that has a list of "dependencies" pointing to other classes of the same base type.

class Foo(Base):
    dependencies = []

class Bar(Base):
    dependencies = [Foo]

class Baz(Base):
    dependencies = [Bar]

I'd like to sort the instances these classes generate based on their dependencies. In my example I'd expect instances of Foo to come first, then Bar, then Baz.

What's the best way to sort this?

Answer 1

It's called a topological sort.

def sort_deps(objs):
    queue = [objs with no dependencies]
    while queue:
        obj = queue.pop()
        yield obj
        for obj in objs:
            if dependencies are now satisfied:
                queue.append(obj)
    if not all dependencies are satisfied:
        error
    return result

Answer 2

I had a similar question just last week - wish I'd know about Stack Overflow then! I hunted around a bit until I realized that I had a DAG (Directed Acyclic Graph since my dependencies couldn't be recursive or circular). Then I found a few references for algorithms to sort them. I used a depth-first traversal to get to the leaf nodes and add them to sorted list first.

Here's a page that I found useful:

Directed Acyclic Graphs