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.
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:
Some pseudo code for Tarjan’s algorithm
Some S.O. Q/A on the subject of detecting 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 :)
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!