Skip to content

Instantly share code, notes, and snippets.

@Beraliv
Forked from six8/gist:1732686
Created January 11, 2023 12:01
Show Gist options
  • Save Beraliv/63547289544bfec59d8ce7eeba189fb7 to your computer and use it in GitHub Desktop.
Save Beraliv/63547289544bfec59d8ce7eeba189fb7 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);
});
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment