Skip to content

Instantly share code, notes, and snippets.

@six8
Created February 3, 2012 21:20
Show Gist options
  • Save six8/1732686 to your computer and use it in GitHub Desktop.
Save six8/1732686 to your computer and use it in GitHub Desktop.
Javascript dependency graph resolution
// Dependency resolution, adapted from https://gist.github.com/1232505/f16308bc14966c8d003c2686b1c258ec41303c1f
function resolve(graph) {
var sorted = [], // sorted list of IDs ( returned value )
visited = {}; // hash: id of already visited node => true
// 2. topological sort
Object.keys(graph).forEach(function visit(name, ancestors) {
if (!Array.isArray(ancestors)) ancestors = [];
ancestors.push(name);
visited[name] = true;
graph[name].forEach(function(dep) {
if (ancestors.indexOf(dep) >= 0) // if already in ancestors, a closed chain exists.
throw new Error('Circular dependency "' + dep + '" is required by "' + name + '": ' + ancestors.join(' -> '));
// if already exists, do nothing
if (visited[name]) return;
visit(dep, ancestors.slice(0)); // recursive call
});
sorted.push(name);
});
return sorted;
}
var subscribers = {
html: ['foo'],
value: ['options', 'html'],
foo: ['options'],
bar: ['options', 'html'],
options: [],
css: ['value'],
elements: ['css', 'html', 'options']
};
/*
Expected:
options
foo
html
value
bar
css
elements
*/
var execution_order = resolve(subscribers);
// var execution_order = resolve(subscribers);
execution_order.forEach(function(name) {
console.log(name);
});
@RubyTuesdayDONO
Copy link

very helpful - thank you so much!

i think there may be a logic error or two based after comparing actual and expected output. i'm not quite smart enough to completely understand the algorithm, but with a little tinkering i was able to pass the test case:
https://gist.github.com/RubyTuesdayDONO/5006455

@jreeme
Copy link

jreeme commented May 12, 2015

Thanks! Exactly what I was looking for. RubyTuesday may have been on to something though. It worked a lot better for me when I moved line 17 to line 7.5.

@Amitkad
Copy link

Amitkad commented May 22, 2016

yep.. there is a problem with it.
@RubyTuesdayDONO fix works fine

thanks you bros

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment