Skip to content

Instantly share code, notes, and snippets.

@SH4DY
Last active August 29, 2015 14:17
Show Gist options
  • Save SH4DY/f0876939cc0c48c18591 to your computer and use it in GitHub Desktop.
Save SH4DY/f0876939cc0c48c18591 to your computer and use it in GitHub Desktop.
Library dependencies - Graph topological sorting per DFS
//Topological sorting - Example of library dependencies
//Imagine you are given library dependencies in this form in a FILE:
// 4 libraries, 5 dependencies
// 0 -> 1
// 1 -> 2
// 2 -> 3
// 2 -> 4
// 3 ->
// 4 ->
// Meaning library 0 depends on lib 1...lib 3 depends on nothing etc
// In what order do you import the libraries, so a program depending on
// them can load?
// How do you read in this file? In what structure do you save it to?
//This is a graph problem in disguise ==> Topological sorting with DFS is a possible solution
//This code shows the DFS solution (returning the a sorted possibility, or an empty list if there are
//circular dependencies), using an ADJACENCY LIST.
//Reading in from file is not shown here.
//Adjacency List of dependencies
var v = [[1],[2],[3,4],[],[]];
//Marking nodes/libs the following format
//0...unvisited
//1...visiting
//2...visited
var sorted = sort(v);
if(sorted.length === 0){
console.log("NOT A DAG");
}
for(var i = 0; i<sorted.length; i++){
console.log("Dep.: " + sorted[i]);
}
function sort(v){
var colors = [];
var sorted = [];
console.log("Length of v: " + v.length);
for(n = 0; n < v.length; n++){
console.log("looping...n is at " + n);
if(colors[n] == undefined){
if(dfs(n, colors, sorted) == false){
console.log("dfs on node " + n + "reports a circle, return []");
return [];
}
}
}
return sorted;
}
function dfs(n, colors, sorted){
if(colors[n] === 1){
console.log("Node " + n + " CYCLE DETECTED");
return false;
}
if(colors[n] === 2){
console.log("Node " + n + " already marked VISITED, leaving");
return true;
}
colors[n] = 1;
console.log("Visiting node " + n);
for(var i = 0; i < v[n].length; i++){
if(dfs(v[n][i], colors, sorted) == false){
console.log("Node " + n + " is part of a cycle - return false");
return false;
}
}
console.log("Marking node " + n + " VISITED");
colors[n] = 2;
sorted.push(n);
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment