mutoo
3/7/2016 - 6:33 AM

a simple topological sorting program to solve course ordering.

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;
}));