Breaking Code

March 11, 2013

An example dependency resolution algorithm in Python

Filed under: Programming — Tags: , , — Mario Vilas @ 2:36 pm

I’ve been toying with dependency resolution a bit today, since it’s one of the features we plan to add to GoLismero 2.0 plugins with @ggdaniel (cr0hn). So I came up with this short example that’s reasonably fast and doesn’t use recursion at all, unlike many of the examples that I found on the net.

The basic idea is this: given a set of tasks (nodes) and the tasks that need to be performed before them, build a dependency graph and find the sets of tasks that can be run concurrently while satisfying the dependencies. For example, suppose we have tasks A, B, C and D. Task A can be run directly, it has no dependencies. Tasks B and C must be run only after A has completed, so we say B and C depend on A. Then task D depends on B and C, which in turn depend on A.

Dependency graph example

Dependency graph example

What the algorithm does, instead of traversing the graph recursively, is iteratively finding and removing from the graph all nodes that have no dependencies – that is, no arrows coming out of them. In our example, the first iteration removes node A, the second iteration removes nodes B and C, and the last iteration removes node D. And these are precisely the three batches of tasks that can run concurrently – first task A runs, on completion tasks B and C can run in parallel, and once both are finished task D can be started.

If at some point there are still nodes in the graph but we can’t find any nodes without dependencies, that means we have a circular dependency.

Circular dependency graph example

Circular dependency graph example

(more…)

The Silver is the New Black Theme. Create a free website or blog at WordPress.com.

Follow

Get every new post delivered to your Inbox.

Join 2,480 other followers