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 <script> tags are rendered to include jQuery, jQuery.UI, jQuery.Validate, ScriptY and then ScriptX (in that order – though jQuery.UI and jQuery.Validate can be in either order).

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<string>]  property. 

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!

Related Articles:

Post Footer automatically generated by Add Post Footer Plugin for wordpress.

About Chad Myers

Chad Myers is the Director of Development for Dovetail Software, in Austin, TX, where he leads a premiere software team building complex enterprise software products. Chad is a .NET software developer specializing in enterprise software designs and architectures. He has over 12 years of software development experience and a proven track record of Agile, test-driven project leadership using both Microsoft and open source tools. He is a community leader who speaks at the Austin .NET User's Group, the ADNUG Code Camp, and participates in various development communities and open source projects.
This entry was posted in .NET, cool-stuff-in-fubu, fubucore, FubuMVC. Bookmark the permalink. Follow any comments here with the RSS feed for this post.
  • Anonymous

    Tarjan’s is interesting, but do you really need something that complicated for dependency graph resolution?  Tarjan’s is really about learning about communities in a graph.  But that kind of profile of the graph might not be the task at hand.  If you just kept a simple set of visited nodes, wouldn’t a straight-forward depth-first search suffice (using the visited node set to guard against cycles)?  That’s the exact algorithm I used when I hand-rolled more or less the same thing, and it worked perfectly fine.  As for computational complexity, DFS is also O(E+V), same as Tarjan’s.  If I’m reading your final interface correctly for your DependencyGraph class, I think Tarjan’s is somewhat overkill.  I think you could have solved your problem with a lot less research and lines of code.

  • Pingback: The Morning Brew - Chris Alcock » The Morning Brew #865

  • http://twitter.com/PhatBoyG Chris Patterson

    Tarjan was only used to find loops in the graph, a regular Topological Sort is used to actually order the dependencies. Not that I would know anything about how it was implemented… ;)