Calculating plugin dependencies

Question

I have the need to create a plugin system that will have dependency support and I'm not sure the best way to account for dependencies. The plugins will all be subclassed from a base class, each with its own execute() method. In each plugin class, I'd planned to create a dependencies attribute as a list of all the other plugins it depends on.

When loading the plugins, I would import all of them and put them in a list and sort them based on the dependencies. Once they are all in the correct order (so anything with a dependency is in the list after its said dependencies) I'd loop through the list executing each methods execute() method.

Where I'm keep getting fuzzy is the logic behind the sorting. I can just start putting them in alphabetical order until i come across one that has a dependency- if its dependencies is not in the list yet, put it into a tmp list. at the end of the first round of imports, start at the end of the temp list ( a list with nothing but plugins that have dependencies) and check the 'run list' again. if i find its dependencies in the 'run list' make sure it has a higher index number than its highest dependency. If its dependencies are not in the list, hold off on it and move to the next plugin in the temp list. Once i get to the end of the tmp list, start back at the top and try again. Once either all the plugins are sorted, or the tmp list doesn't change size after looping over it- start executing plugins.

What would be left in the temp list are plugins that either don't have they're dependencies found, or have a circular dependency. (2 plugins in the tmp list that depend on one another)

If you're still reading AND you were able to follow my logic; is this a sound plan? Is there a simpler way? If i wanted to implement sequence numbers for execute order, is there an 'easy' way to have both sequence and dependencies? (with dependencies beating sequencing if there was a conflict) Or should a plugin use a sequence OR dependencies? (Run the plugins with sequence numbers first, than the ones with dependencies?)

TL;DR

How would you write the logic for calculating dependencies in a plugin system?

---

Edit:

Alright- I think I implemented the Topological sort from the wikipedia page; following its logic example for the DFS. It seems to work, but i've never done anything like this before.

http://en.wikipedia.org/wiki/Topological_sorting#Examples

data = {
    '10' :  ['11', '3'],
    '3'  :  [],
    '5'  :  [],
    '7'  :  [],
    '11' :  ['7', '5'],
    '9'  :  ['8', '11'],
    '2'  :  ['11'],
    '8'  :  ['7', '3']
}

L = []
visited = []

def nodeps(data):
    S = []
    for each in data.keys():
        if not len(data[each]):
            S.append(each)
    return S

def dependson(node):
    r = []
    for each in data.keys():
        for n in data[each]:
            if n == node:
                r.append(each)
    return r

def visit(node):
    if not node in visited:
        visited.append(node)
        for m in dependson(node):
            visit(m)
        L.append(node)

for node in nodeps(data):
    visit(node)

print L[::-1]

Answer 1

The algorithm you described sounds like it would work but would have a hard time detecting circular dependencies.

What you're looking for is a Topological sort of your dependencies. If you create a graph of your dependencies where an edge from A to B means A depends on B then you can do a Depth-first search to determine the correct order. You'll want to do a variation of a regular DFS that can detect cycles so you can print an error in that case.

If you use an ordered list on each vertex to store connections in the graph, you can add dependencies using their sequence numbers. An advantage of using a DFS is that the resulting sorted list should respect your sequence ordering when it isn't conflicting with dependency order. (I believe; I need to test this.)

Answer 2

A topological sort will put everything in the correct order.