Skip to content

Instantly share code, notes, and snippets.

@finalclass
Created October 20, 2014 23:29
Show Gist options
  • Star 1 You must be signed in to star a gist
  • Fork 0 You must be signed in to fork a gist
  • Save finalclass/74bc545328ddf9652781 to your computer and use it in GitHub Desktop.
Save finalclass/74bc545328ddf9652781 to your computer and use it in GitHub Desktop.
dependency resolving algorithm
/**
* taken from:
* http://www.electricmonk.nl/log/2008/08/07/dependency-resolving-algorithm/
*/
class GraphNode {
public edges:GraphNode[] = [];
constructor(public name:string) {}
public addEdge(c:GraphNode):void {
this.edges.push(c);
}
}
var nodes:{[id:string]:GraphNode} = {};
nodes['a'] = new GraphNode('a');
nodes['b'] = new GraphNode('b');
nodes['c'] = new GraphNode('c');
nodes['d'] = new GraphNode('d');
nodes['e'] = new GraphNode('e');
nodes['a'].addEdge(nodes['b']); // a depends on b
nodes['a'].addEdge(nodes['d']); // a depends on d
nodes['b'].addEdge(nodes['c']); // b depends on c
nodes['b'].addEdge(nodes['e']); // b depends on e
nodes['c'].addEdge(nodes['d']); // c depends on d
nodes['c'].addEdge(nodes['e']); // c depends on e
function depResolve(c:GraphNode, resolved:GraphNode[] = [], unresolved:GraphNode[] = []):GraphNode[] {
unresolved.push(c);
c.edges.forEach((sub:GraphNode) => {
if (resolved.indexOf(sub) === -1) {
if (unresolved.indexOf(sub) !== -1) {
throw new Error('Circular reference detected: ' + c.name + ' -> ' + sub.name);
}
depResolve(sub, resolved, unresolved)
}
});
resolved.push(c);
unresolved.splice(unresolved.indexOf(c), 1);
return resolved;
}
var resolved:GraphNode[] = depResolve(nodes['a']);
console.log(resolved.map(c => c.name));
@WKleinschmit
Copy link

What if I only habe a bunch of nodes and their dependencies, not knowing that 'a' is the root?
How do I know, where to start?

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