Last active
August 29, 2015 14:17
-
-
Save SH4DY/f0876939cc0c48c18591 to your computer and use it in GitHub Desktop.
Library dependencies - Graph topological sorting per DFS
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
//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