FazBrowse GitHub Viewer | Trending |
URL:
| Home
Tools: [Download Repo ZIP]   [Original HTTPS Page]

Add topological sorting. · boycgit/javascript-algorithms@e73dc2d · GitHub

/ javascript-algorithms Public
forked from trekhleb/javascript-algorithms

Commit e73dc2d

Browse files
trekhleb
committed
Add topological sorting.
1 parent fc53c7d commit e73dc2d

7 files changed

Lines changed: 225 additions & 1 deletion

File tree

‎README.md‎

Lines changed: 1 addition & 1 deletion
Original file line numberDiff line numberDiff line change
@@ -71,7 +71,7 @@
7171
* [Detect Cycle](https://github.com/trekhleb/javascript-algorithms/tree/master/src/algorithms/graph/detect-cycle) - for both directed and undirected graphs (DFS and Disjoint Set based versions)
7272
* [Prim’s Algorithm](https://github.com/trekhleb/javascript-algorithms/tree/master/src/algorithms/graph/prim) - finding Minimum Spanning Tree (MST) for weighted undirected graph
7373
* [Kruskal’s Algorithm](https://github.com/trekhleb/javascript-algorithms/tree/master/src/algorithms/graph/kruskal) - finding Minimum Spanning Tree (MST) for weighted undirected graph
74-
* Topological Sorting
74+
* [Topological Sorting](https://github.com/trekhleb/javascript-algorithms/tree/master/src/algorithms/graph/topological-sorting) - DFS method
7575
* Eulerian path, Eulerian circuit
7676
* Strongly Connected Component algorithm
7777
* Shortest Path Faster Algorithm (SPFA)

‎src/algorithms/graph/topological-sorting/README.md‎

Lines changed: 55 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,55 @@
1+
# Topological Sorting
2+
3+
In the field of computer science, a topological sort or
4+
topological ordering of a directed graph is a linear ordering
5+
of its vertices such that for every directed edge `uv` from
6+
vertex `u` to vertex `v`, `u` comes before `v` in the ordering.
7+
8+
For instance, the vertices of the graph may represent tasks to
9+
be performed, and the edges may represent constraints that one
10+
task must be performed before another; in this application, a
11+
topological ordering is just a valid sequence for the tasks.
12+
13+
A topological ordering is possible if and only if the graph has
14+
no directed cycles, that is, if it is a [directed acyclic graph](https://en.wikipedia.org/wiki/Directed_acyclic_graph)
15+
(DAG). Any DAG has at least one topological ordering, and algorithms are
16+
known for constructing a topological ordering of any DAG in linear time.
17+
18+
![Directed Acyclic Graph](https://upload.wikimedia.org/wikipedia/commons/c/c6/Topological_Ordering.svg)
19+
20+
A topological ordering of a directed acyclic graph: every edge goes from
21+
earlier in the ordering (upper left) to later in the ordering (lower right).
22+
A directed graph is acyclic if and only if it has a topological ordering.
23+
24+
## Example
25+
26+
![Topologic Sorting](https://upload.wikimedia.org/wikipedia/commons/0/03/Directed_acyclic_graph_2.svg)
27+
28+
The graph shown above has many valid topological sorts, including:
29+
30+
- `5, 7, 3, 11, 8, 2, 9, 10` (visual left-to-right, top-to-bottom)
31+
- `3, 5, 7, 8, 11, 2, 9, 10` (smallest-numbered available vertex first)
32+
- `5, 7, 3, 8, 11, 10, 9, 2` (fewest edges first)
33+
- `7, 5, 11, 3, 10, 8, 9, 2` (largest-numbered available vertex first)
34+
- `5, 7, 11, 2, 3, 8, 9, 10` (attempting top-to-bottom, left-to-right)
35+
- `3, 7, 8, 5, 11, 10, 2, 9` (arbitrary)
36+
37+
## Application
38+
39+
The canonical application of topological sorting is in
40+
**scheduling a sequence of jobs** or tasks based on their dependencies. The jobs
41+
are represented by vertices, and there is an edge from `x` to `y` if
42+
job `x` must be completed before job `y` can be started (for
43+
example, when washing clothes, the washing machine must finish
44+
before we put the clothes in the dryer). Then, a topological sort
45+
gives an order in which to perform the jobs.
46+
47+
Other application is **dependency resolution**. Each vertex is a package
48+
and each edge is a dependency of package `a` on package 'b'. Then topological
49+
sorting will provide a sequence of installing dependencies in a way that every
50+
next dependency has its dependent packages to be installed in prior.
51+
52+
## References
53+
54+
- [Wikipedia](https://en.wikipedia.org/wiki/Topological_sorting)
55+
- [Topological Sorting on YouTube by Tushar Roy](https://www.youtube.com/watch?v=ddTC4Zovtbc)

‎src/algorithms/graph/topological-sorting/__test__/topologicalSort.test.js‎

Lines changed: 53 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,53 @@
1+
import GraphVertex from '../../../../data-structures/graph/GraphVertex';
2+
import GraphEdge from '../../../../data-structures/graph/GraphEdge';
3+
import Graph from '../../../../data-structures/graph/Graph';
4+
import topologicalSort from '../topologicalSort';
5+
6+
describe('topologicalSort', () => {
7+
it('should do topological sorting on graph', () => {
8+
const vertexA = new GraphVertex('A');
9+
const vertexB = new GraphVertex('B');
10+
const vertexC = new GraphVertex('C');
11+
const vertexD = new GraphVertex('D');
12+
const vertexE = new GraphVertex('E');
13+
const vertexF = new GraphVertex('F');
14+
const vertexG = new GraphVertex('G');
15+
const vertexH = new GraphVertex('H');
16+
17+
const edgeAC = new GraphEdge(vertexA, vertexC);
18+
const edgeBC = new GraphEdge(vertexB, vertexC);
19+
const edgeBD = new GraphEdge(vertexB, vertexD);
20+
const edgeCE = new GraphEdge(vertexC, vertexE);
21+
const edgeDF = new GraphEdge(vertexD, vertexF);
22+
const edgeEF = new GraphEdge(vertexE, vertexF);
23+
const edgeEH = new GraphEdge(vertexE, vertexH);
24+
const edgeFG = new GraphEdge(vertexF, vertexG);
25+
26+
const graph = new Graph(true);
27+
28+
graph
29+
.addEdge(edgeAC)
30+
.addEdge(edgeBC)
31+
.addEdge(edgeBD)
32+
.addEdge(edgeCE)
33+
.addEdge(edgeDF)
34+
.addEdge(edgeEF)
35+
.addEdge(edgeEH)
36+
.addEdge(edgeFG);
37+
38+
const sortedVertices = topologicalSort(graph);
39+
40+
expect(sortedVertices).toBeDefined();
41+
expect(sortedVertices.length).toBe(graph.getAllVertices().length);
42+
expect(sortedVertices).toEqual([
43+
vertexB,
44+
vertexD,
45+
vertexA,
46+
vertexC,
47+
vertexE,
48+
vertexH,
49+
vertexF,
50+
vertexG,
51+
]);
52+
});
53+
});

‎src/algorithms/graph/topological-sorting/topologicalSort.js‎

Lines changed: 47 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,47 @@
1+
import Stack from '../../../data-structures/stack/Stack';
2+
import depthFirstSearch from '../depth-first-search/depthFirstSearch';
3+
4+
/**
5+
* @param {Graph} graph
6+
*/
7+
export default function topologicalSort(graph) {
8+
// Create a set of all vertices we want to visit.
9+
const unvisitedSet = {};
10+
graph.getAllVertices().forEach((vertex) => {
11+
unvisitedSet[vertex.getKey()] = vertex;
12+
});
13+
14+
// Create a set for all vertices that we've already visited.
15+
const visitedSet = {};
16+
17+
// Create a stack of already ordered vertices.
18+
const sortedStack = new Stack();
19+
20+
const dfsCallbacks = {
21+
enterVertex: ({ currentVertex }) => {
22+
// Add vertex to visited set in case if all its children has been explored.
23+
visitedSet[currentVertex.getKey()] = currentVertex;
24+
25+
// Remove this vertex from unvisited set.
26+
delete unvisitedSet[currentVertex.getKey()];
27+
},
28+
leaveVertex: ({ currentVertex }) => {
29+
// If the vertex has been totally explored then we may push it to stack.
30+
sortedStack.push(currentVertex);
31+
},
32+
allowTraversal: ({ nextVertex }) => {
33+
return !visitedSet[nextVertex.getKey()];
34+
},
35+
};
36+
37+
// Let's go and do DFS for all unvisited nodes.
38+
while (Object.keys(unvisitedSet).length) {
39+
const currentVertexKey = Object.keys(unvisitedSet)[0];
40+
const currentVertex = unvisitedSet[currentVertexKey];
41+
42+
// Do DFS for current node.
43+
depthFirstSearch(graph, currentVertex, dfsCallbacks);
44+
}
45+
46+
return sortedStack.toArray();
47+
}

‎src/data-structures/linked-list/LinkedList.js‎

Lines changed: 31 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -9,13 +9,21 @@ export default class LinkedList {
99
this.tail = null;
1010
}
1111

12+
/**
13+
* @param {*} value
14+
* @return {LinkedList}
15+
*/
1216
prepend(value) {
1317
// Make new node to be a head.
1418
this.head = new LinkedListNode(value, this.head);
1519

1620
return this;
1721
}
1822

23+
/**
24+
* @param {*} value
25+
* @return {LinkedList}
26+
*/
1927
append(value) {
2028
const newNode = new LinkedListNode(value);
2129

@@ -34,6 +42,10 @@ export default class LinkedList {
3442
return this;
3543
}
3644

45+
/**
46+
* @param {*} value
47+
* @return {LinkedListNode}
48+
*/
3749
delete(value) {
3850
if (!this.head) {
3951
return null;
@@ -67,6 +79,12 @@ export default class LinkedList {
6779
return deletedNode;
6880
}
6981

82+
/**
83+
* @param {Object} findParams
84+
* @param {*} findParams.value
85+
* @param {function} [findParams.callback]
86+
* @return {LinkedListNode}
87+
*/
7088
find({ value = undefined, callback = undefined }) {
7189
if (!this.head) {
7290
return null;
@@ -91,6 +109,9 @@ export default class LinkedList {
91109
return null;
92110
}
93111

112+
/**
113+
* @return {LinkedListNode}
114+
*/
94115
deleteTail() {
95116
if (this.head === this.tail) {
96117
const deletedTail = this.tail;
@@ -116,6 +137,9 @@ export default class LinkedList {
116137
return deletedTail;
117138
}
118139

140+
/**
141+
* @return {LinkedListNode}
142+
*/
119143
deleteHead() {
120144
if (!this.head) {
121145
return null;
@@ -133,6 +157,9 @@ export default class LinkedList {
133157
return deletedHead;
134158
}
135159

160+
/**
161+
* @return {LinkedListNode[]}
162+
*/
136163
toArray() {
137164
const nodes = [];
138165

@@ -145,6 +172,10 @@ export default class LinkedList {
145172
return nodes;
146173
}
147174

175+
/**
176+
* @param {function} [callback]
177+
* @return {string}
178+
*/
148179
toString(callback) {
149180
return this.toArray().map(node => node.toString(callback)).toString();
150181
}

‎src/data-structures/stack/Stack.js‎

Lines changed: 26 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -5,10 +5,16 @@ export default class Stack {
55
this.linkedList = new LinkedList();
66
}
77

8+
/**
9+
* @return {boolean}
10+
*/
811
isEmpty() {
912
return !this.linkedList.tail;
1013
}
1114

15+
/**
16+
* @return {LinkedListNode}
17+
*/
1218
peek() {
1319
if (!this.linkedList.tail) {
1420
return null;
@@ -17,15 +23,35 @@ export default class Stack {
1723
return this.linkedList.tail.value;
1824
}
1925

26+
/**
27+
* @param {*} value
28+
*/
2029
push(value) {
2130
this.linkedList.append(value);
2231
}
2332

33+
/**
34+
* @return {LinkedListNode}
35+
*/
2436
pop() {
2537
const removedTail = this.linkedList.deleteTail();
2638
return removedTail ? removedTail.value : null;
2739
}
2840

41+
/**
42+
* @return {*[]}
43+
*/
44+
toArray() {
45+
return this.linkedList
46+
.toArray()
47+
.map(linkedListNode => linkedListNode.value)
48+
.reverse();
49+
}
50+
51+
/**
52+
* @param {function} [callback]
53+
* @return {string}
54+
*/
2955
toString(callback) {
3056
return this.linkedList.toString(callback);
3157
}

‎src/data-structures/stack/__test__/Stack.test.js‎

Lines changed: 12 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -62,4 +62,16 @@ describe('Stack', () => {
6262
expect(stack.pop().value).toBe('test2');
6363
expect(stack.pop().value).toBe('test1');
6464
});
65+
66+
it('should be possible to convert stack to array', () => {
67+
const stack = new Stack();
68+
69+
expect(stack.peek()).toBeNull();
70+
71+
stack.push(1);
72+
stack.push(2);
73+
stack.push(3);
74+
75+
expect(stack.toArray()).toEqual([3, 2, 1]);
76+
});
6577
});

0 commit comments

Comments
 (0)
Back | FazBrowse Home | New Git URL