a simple topological sorting program to solve course ordering.
{
"Programming in C": [],
"Distributed Computing": ["Programming in C", "Advanced Programming in Java", "Scalable Machine Learning"],
"Database System": ["Programming in C", "Programming in Java", "Advanced Programming in Java", "Big Data with Apache Spark", "Data Structures"],
"Algorithm 1": ["Programming in C", "Programming in Perl", "Database System"],
"Algorithm 2": ["Programming in C", "Algorithm 1", "Database System", "Data Structures"],
"Programming in Java": ["Programming in C"],
"Advanced Programming in Java": ["Programming in Java"],
"Big Data with Apache Spark": ["Programming in Java", "Advanced Programming in Java", "Probability", "Data Structures"],
"Programming in Perl": ["Algorithm 2"],
"Probability": [],
"Scalable Machine Learning": ["Probability", "Big Data with Apache Spark"],
"Data Structures": []
}
var path = require("path");
var args = process.argv.slice(2);
var inputFile = args[0] || "sample.json";
var courseData = require(path.resolve(inputFile));
var Node = function(name) {
this.name = name;
this.inDegrees = 0;
this.afterEdges = [];
}
var Edge = function(from, to) {
this.from = from;
this.to = to;
}
Edge.prototype.link = function() {
this.from.afterEdges.push(this);
this.to.inDegrees++;
}
Edge.prototype.unlink = function() {
var idx = this.from.afterEdges.indexOf(this);
this.from.afterEdges.splice(idx, 1);
this.to.inDegrees--;
}
var courseDict = {};
for (var courseName in courseData) {
courseDict[courseName] = new Node(courseName);
}
for (var courseName in courseData) {
var preRequisit = courseData[courseName]
for (var i = 0; i < preRequisit.length; i++) {
var edge = new Edge(courseDict[preRequisit[i]], courseDict[courseName]);
edge.link();
}
}
var courseList = [];
for (var courseName in courseData) {
var course = courseDict[courseName];
if (course.inDegrees === 0) {
courseList.push(course);
}
}
var queue = [];
while (courseList.length !== 0) {
var course = courseList.shift();
while (course.afterEdges.length > 0) {
var edge = course.afterEdges[0];
edge.unlink();
if (edge.to.inDegrees === 0) {
courseList.push(edge.to)
}
}
queue.push(course);
}
console.log(queue.map(function(node) {
return node.name;
}));