Last active
March 6, 2017 11:09
-
-
Save mutoo/e597ceac20e6111cc458 to your computer and use it in GitHub Desktop.
a simple topological sorting program to solve course ordering.
This file contains hidden or 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
| 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; | |
| })); |
This file contains hidden or 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
| { | |
| "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": [] | |
| } |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment