A clean algorithm for sorting a objects according to defined dependencies?

Question

Given a list of classes inheriting from this base:

class Plugin(object):
    run_after_plugins = ()
    run_before_plugins = ()

...and the following rules:

• Plugins can provide a list of plugins that they must run after.
• Plugins can provide a list of plugins that they must run before.
• The list of plugins may or may not contain all plugins that have been specified in ordering constraints.

Can anyone provide a nice clean algorithm for ordering a list of plugins? It will need to detect circular dependencies as well....

 def order_plugins(plugins):
      pass

I've come up with a few versions but nothing particuarlly neat: I'm sure some of you Art of Computer Programming types will relish the challenge :)

[note: question given in Python but it's clearly not only a Python question: pseudocode in any language would do]

Answer 1

This is called topological sorting.

The canonical application of topological sorting (topological order) is in scheduling a sequence of jobs or tasks; topological sorting algorithms were first studied in the early 1960s in the context of the PERT technique for scheduling in project management (Jarnagin 1960). The jobs are represented by vertices, and there is an edge from x to y if job x must be completed before job y can be started (for example, when washing clothes, the washing machine must finish before we put the clothes to dry). Then, a topological sort gives an order in which to perform the jobs.

Answer 2

This is called topological sorting.

Doing this involves several steps:

First build a graph of all choosen plugins as vertices and their dependencies as edges. Run before/after deps boil down to the same type of edges.

Next build a transitiv hull: Look at all plugins and add all missing dependencies. Repeat this until the set does not change any more.

Last step: Choose a vertice without incoming edges and do a DFS (or BFS) search. This algorithms can be enriched with cycle detection.

Answer 3

If you define the __lt__ and associated methods on Plugin based on whether or not they should be run before or after then it could be possible to find a sane ordering with sorted(). Cycles would still be a problem though.

Answer 4

If you want to give good diagnostics for the case that there are cycles, have a look at http://en.wikipedia.org/wiki/Strongly_connected_component. I think that if you use a version of a Strongly connected component like the one outlined in http://www.cs.sunysb.edu/~skiena/373/notes/lecture16/lecture16.html you can get it to print out the strongly connected components in topological sort order.

Answer 5

Here is Python code that does topological sorting.