One of the projects I am working on at work presented an interesting problem. Â I had a list of items with dependencies on one another and I needed to figure out the order in which to use those items, based on their dependencies.
For the sake of the example, think of a list of database tables, which reference each other. Â I need a way to export those tables in such a way, that when imported back in, tables that have dependencies will be imported after all those tables on which they depend. Â (It’s not the real task I’m working on, but close enough.)
Consider the following list as an example of input data:
// List of items with dependencies. Order is not important
$tables = [
'articles_meta' => ['articles'],
'articles' => ['users', 'categories', 'tags'],
'categories' => [],
'comments' => ['users', 'articles'],
'options' => [],
'tags' => [],
'users' => [],
'users_meta' => ['users'],
];
The result of the dependency resolution should give me the list like this (there are variations in order, of course, as long as the dependencies are satisfied):
categories
options
tags
users
users_meta
articles
articles_meta
comments
There are several ways to solve this problem. Â My first attempt took about 50 lines of code and worked fine, but it lacked elegance. Â It had too many nested loops and tricky conditions and was difficult to read. Â My second attempt was slightly better, with a bit of a recursion, but still looked somewhat off. Â It felt like there is a better way to do it, and that I’ve done something similar before, but I could put my finger on it.
I thought I’d take a look at something that solves a similar problem.  Composer, PHP package and dependency manager, surely had something to offer.  A brief check of the GitHub repository, and that idea is out of my hand.  Composer deals with much more complex issues, so its Dependency Resolver code is not something I can grasp in a few minutes.
It was time for some Googling. Â Moments later, my deja vu feeling of “I’ve seen this before” was easily explained. Â This problem fits into the graph theory, which I probably used last back in my college years. Â Of course, I could have grabbed the book off the shelf and refresh my knowledge, practicing the sacred art of the Real Programming. Â But time was an issue, so I cheated.
I found this “Dependency resolving algorithm” blog post by Ferry Boender over at Electric Monk (thanks man!).  He had exactly what I needed – simple and straight forward recursive algorithm for walking the graph, circular dependency detection, and even some performance optimization.
The only problem was that his code is all in Python. Â But that’s not really a problem. Â So I’ve rewritten his code in PHP and got exactly what I needed. Â Here it is:
// List of items with dependencies. Order is not important
$tables = [
'articles_meta' => ['articles'],
'articles' => ['users', 'categories', 'tags'],
'categories' => [],
'comments' => ['users', 'articles'],
'options' => [],
'tags' => [],
'users' => [],
'users_meta' => ['users'],
];
$resolved = [];
$unresolved = [];
// Resolve dependencies for each table
foreach (array_keys($tables) as $table) {
try {
list ($resolved, $unresolved) = dep_resolve($table, $tables, $resolved, $unresolved);
} catch (\Exception $e) {
die("Oops! " . $e->getMessage());
}
}
// Print out result
foreach ($resolved as $table) {
$deps = empty($tables[$table]) ? 'none' : join(',', $tables[$table]);
print "$table (deps: $deps)\n";
}
/**
* Recursive dependency resolution
*
* @param string $item Item to resolve dependencies for
* @param array $items List of all items with dependencies
* @param array $resolved List of resolved items
* @param array $unresolved List of unresolved items
* @return array
*/
function dep_resolve($item, array $items, array $resolved, array $unresolved) {
array_push($unresolved, $item);
foreach ($items[$item] as $dep) {
if (!in_array($dep, $resolved)) {
if (!in_array($dep, $unresolved)) {
array_push($unresolved, $dep);
list($resolved, $unresolved) = dep_resolve($dep, $items, $resolved, $unresolved);
} else {
throw new \RuntimeException("Circular dependency: $item -> $dep");
}
}
}
// Add $item to $resolved if it's not already there
if (!in_array($item, $resolved)) {
array_push($resolved, $item);
}
// Remove all occurrences of $item in $unresolved
while (($index = array_search($item, $unresolved)) !== false) {
unset($unresolved[$index]);
}
return [$resolved, $unresolved];
}
Running the above code produces the following result:
$ php dependecy.php
users (deps: none)
categories (deps: none)
tags (deps: none)
articles (deps: users,categories,tags)
articles_meta (deps: articles)
comments (deps: users,articles)
options (deps: none)
users_meta (deps: users)
Which is exactly what I was looking for. Â And now that I have it here, I’ll probably be needing it again and again. Â It’s an elegant hammer to a lot of my nails.