Cool stuff in FubuCore No. 4: Dependency Analysis with Directed Graph

This is the fourth post of the FubuCore series mentioned in the Introduction post.

There are several places in the Fubu-related projects (FubuMVC, Bottles packaging/deployment, etc) that we need to work out a dependency tree.  This means, for a given node, we need to find out all the dependencies that node has and if there are any cycles in the dependency graph.  I’m being vague. Let me be more concrete.

FubuMVC has script management functionality. Actually, it has resource management because it can handle more than just scripts (like CSS), but the main problem has to do with script dependencies.  We do a *lot* of stuff with JavaScript and jQuery. We use a lot of jQuery plugins and we have a lot of internal plugins we’ve written for our app.  The dependency graph gets kinda complicated: ScriptX depends on ScriptY which depends on jQuery.Validate and jQuery.UI and all these four scripts depend on jQuery proper.  So if a view requests that ScriptX be added to the HTML output, our script manager has to also ensure that

Later, if another view requests, say, ScriptY, the script manager knows that ScriptY and all its dependencies have already been rendered, so it does nothing.  So the script manager ensures once-and-only-once and dependency graph resolution (among other things).

We ran into a similar situation in our deployment story when figuring out what dependencies application X has when being deployed.  Rather than re-writing dependency graph resolution logic again, Dru and Jeremy decided to figure out if there was common algorithm for doing this sort of thing.  They found some and then implemented them in FubuCore.  We’re currently using it for Bottles Deployment and will soon retro-fit it back into Script Manager. 

First, the math!

Here’s where they started:

Directed Graph

Tarjan’s strongly connected components algorithm 

Some pseudo code for Tarjan’s algorithm

Some S.O. Q/A on the subject of detecting cycles in a graph:

Best algorithm for detecting cycles in a directed graph

Finding all cycles in a graph

Second, the implementation

They wrote the implementation to be use-case agnostic. They made it generic to apply to any dependency-resolution situation so that we could reuse it for numerous things like deployment and script management.

It all starts with DependencyGraph.  You tell DependencyGraph about your main graph model object (think ‘script’ for the script manager or ‘component’ for deployment).  Another good example is a build tool (say, rake).  Rake, like every other build tool, has targets (i.e. ‘compile’ or ‘test’). Targets have dependencies (‘test’ may require ‘compile’ and ‘deploy_config’).  A rakefile (like a makefile or NAnt build file or MSBuild file) has a flat list of all the targets.  You would feed this list to DependencyGraph and then tell it how to find the dependencies for each task.

For this post, let’s talk about Bottles (since that’s what DependencyGraph was originally written for and is currently the best example of its use). In Bottles, a deployable unit (or component) is called a “Recipe.” The Recipe object has a [Name : string] property and a [Dependencies : IEnumerable]  property.  </p>

In Bottles, we need to feed a flattened list of all the recipes and their dependencies (which we get from a config file) and want DependencyGraph to tell us the order of how all the recipes need to be installed. Consider this code snippet:

// Teach D.G. how get a unique key/name and list of deps for each recipe
var graph = new DependencyGraph<Recipe>(r => r.Name, r => r.Dependencies);

// Register each recipe with the graph
recipes.Each(graph.RegisterItem);

// Ask the graph to give us the final, properly-ordered list
return graph.Ordered();

Our script management works similarly (the list of scripts and their dependencies are in a config file).  We have a model object that represents a configured script and its related dependencies.  We’d be able to reuse that DependencyGraph code above fairly easily to take advantage of the algorithm implementations and remove a bunch of code from FubuMVC’s script management. We just haven’t done it yet 🙂

Summary

If you’re working with a list of things that have dependencies and you need to know the order that those things should be processed to honor the dependency chain, consider using the DependencyGraph in FubuCore!