CODEWITHSUNDEEP
pythonalgorithm
jkp
jkp

Reputation: 81316

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

Given a list of classes inheriting from this base:

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

...and the following rules:

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]

Upvotes: 5

Views: 1191

Answers (5)

tzot
tzot

Reputation: 96001

Here is Python code that does topological sorting.

Upvotes: 2

mcdowella
mcdowella

Reputation: 19611

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.

Upvotes: 0

Ignacio Vazquez-Abrams
Ignacio Vazquez-Abrams

Reputation: 799150

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.

Upvotes: 0

ebo
ebo

Reputation: 9215

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.

Upvotes: 1

Eli Bendersky
Eli Bendersky

Reputation: 273646

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.

Upvotes: 8

Related Questions