-
Notifications
You must be signed in to change notification settings - Fork 0
Expand file tree
/
Copy pathtopological-sort.js
More file actions
76 lines (67 loc) · 1.78 KB
/
Copy pathtopological-sort.js
File metadata and controls
76 lines (67 loc) · 1.78 KB
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
// hard, requires graph and DFS
// Time (j + d) - because we are applying DFS - j number of jobs and d number of deps
// Space (j + d)
function topologicalSort(jobs, deps) {
const jobsGraph = createJobGraph(jobs, deps);
return getOrderedJobs(jobsGraph);
}
function createJobGraph(jobs, deps) {
const graph = new JobGraph(jobs);
for (const [prereq, job] of deps) {
graph.addPrereq(job, prereq);
}
return graph;
}
function getOrderedJobs(graph) {
const orderedJobs = [];
const { nodes } = graph;
while (nodes.length) {
const node = nodes.pop();
const containsCycle = depthFirstTraverse(node, orderedJobs);
if (containsCycle) return [];
}
return orderedJobs;
}
function depthFirstTraverse(node, orderedJobs) {
if (node.visited) return false; // means we visited this node and we don't have a cycle
if (node.visiting) return true; // means we have a cycle
node.visiting = true;
for (const prereqNode of node.prereqs) {
const containsCycle = depthFirstTraverse(prereqNode, orderedJobs);
if (containsCycle) return true;
}
node.visited = true;
node.visiting = false;
orderedJobs.push(node.job);
return false;
}
class JobGraph {
constructor(jobs) {
this.nodes = [];
this.graph = {};
for (const job of jobs) {
this.addNode(job);
}
}
addPrereq(job, prereq) {
const jobNode = this.getNode(job);
const prereqNode = this.getNode(prereq);
jobNode.prereqs.push(prereqNode);
}
getNode(job) {
if (!this.graph.hasOwnProperty(job)) this.addNode(job);
return this.graph[job];
}
addNode(job) {
this.graph[job] = new JobNode(job);
this.nodes.push(this.graph[job]);
}
}
class JobNode {
constructor(job) {
this.job = job;
this.prereqs = [];
this.visited = false;
this.visiting = false;
}
}