Skip to content

Commit 6c4092a

Browse files
Jtmonumentthanhtri122002siriakanhpham197sanotaku09
authored
Add Topological Sorting Algorithm (TheAlgorithms#3060)
Co-authored-by: thanhtri122002 <thanhnt122002@122002> Co-authored-by: Andrii Siriak <siryaka@gmail.com> Co-authored-by: Anh Pham <62592224+anhpham197@users.noreply.github.com> Co-authored-by: SanOtaku <SanOtaku098@gmail.com> Co-authored-by: Raghav Taneja <97575679+RaghavTaneja@users.noreply.github.com> Co-authored-by: Andrii Siriak <siryaka@gmail.com> Co-authored-by: Hai Nguyen <88832724+ntquanghai@users.noreply.github.com> Co-authored-by: Utkarsh Yadav <Utkarshrock1510@gmail.com> Co-authored-by: Phạm Minh Hiếu <84634830+Ph1eu@users.noreply.github.com> Co-authored-by: nguyenviettrung-bi11276 <101244039+nguyenviettrung-bi11276@users.noreply.github.com> Co-authored-by: TaiNguyen2001 <102779475+TaiNguyen2001@users.noreply.github.com> Co-authored-by: de <88503943+HuyQHoang@users.noreply.github.com> Co-authored-by: thanhtri122002 <93241140+thanhtri122002@users.noreply.github.com> Co-authored-by: thanhtri122002 <thanhnt122002@122002>
1 parent ec1ab53 commit 6c4092a

File tree

2 files changed

+221
-0
lines changed

2 files changed

+221
-0
lines changed

‎src/main/java/com/thealgorithms/sorts/TopologicalSort.java

Lines changed: 160 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,160 @@
1+
package com.thealgorithms.sorts;
2+
3+
import java.util.*;
4+
5+
/**
6+
* The Topological Sorting algorithm linearly orders a DAG or Directed Acyclic Graph into
7+
* a linked list. A Directed Graph is proven to be acyclic when a DFS or Depth First Search is
8+
* performed, yielding no back-edges.
9+
*
10+
* https://en.wikipedia.org/wiki/Topological_sorting
11+
*
12+
* @author Jonathan Taylor (https://github.com/Jtmonument)
13+
* Based on Introduction to Algorithms 3rd Edition
14+
*/
15+
public class TopologicalSort {
16+
17+
/*
18+
* Enum to represent the colors for the depth first search
19+
* */
20+
private enum Color {
21+
WHITE, GRAY, BLACK
22+
}
23+
24+
/*
25+
* Class to represent vertices
26+
* */
27+
private static class Vertex {
28+
/*
29+
* Name of vertex
30+
* */
31+
public final String label;
32+
33+
/*
34+
* Weight of vertex
35+
* (more accurately defined as the time that a vertex has begun a visit in DFS)
36+
* */
37+
public int weight;
38+
39+
/*
40+
* The time that the vertex has finished a visit in DFS
41+
* */
42+
public int finished;
43+
44+
/*
45+
* π parent of the vertex
46+
* */
47+
public Vertex predecessor;
48+
49+
/*
50+
* Represents the category of visit in DFS
51+
* */
52+
public Color color = Color.WHITE;
53+
54+
/*
55+
* The array of names of descendant vertices
56+
* */
57+
public final ArrayList<String> next = new ArrayList<>();
58+
59+
public Vertex(String label) {
60+
this.label = label;
61+
}
62+
}
63+
64+
/*
65+
* Graph class uses the adjacency list representation
66+
* */
67+
static class Graph {
68+
69+
/*
70+
* Adjacency list representation
71+
* */
72+
private final HashMap<String, Vertex> adj = new LinkedHashMap<>();
73+
74+
/*
75+
* Function to add an edge to the graph
76+
* */
77+
public void addEdge(String label, String... next) {
78+
adj.put(label, new Vertex(label));
79+
if (!next[0].isEmpty())
80+
Collections.addAll(adj.get(label).next, next);
81+
}
82+
}
83+
84+
static class BackEdgeException extends RuntimeException {
85+
86+
public BackEdgeException(String backEdge) {
87+
super("This graph contains a cycle. No linear ordering is possible. " + backEdge);
88+
}
89+
90+
}
91+
92+
/*
93+
* Time variable in DFS
94+
* */
95+
private static int time;
96+
97+
/*
98+
* Depth First Search
99+
*
100+
* DFS(G)
101+
* for each vertex u ∈ G.V
102+
* u.color = WHITE
103+
* u.π = NIL
104+
* time = 0
105+
* for each vertex u ∈ G.V
106+
* if u.color == WHITE
107+
* DFS-VISIT(G, u)
108+
*
109+
* Performed in Θ(V + E) time
110+
* */
111+
public static LinkedList<String> sort(Graph graph) {
112+
LinkedList<String> list = new LinkedList<>();
113+
graph.adj.forEach((name, vertex) -> {
114+
if (vertex.color == Color.WHITE) {
115+
list.addFirst(sort(graph, vertex, list));
116+
}
117+
});
118+
return list;
119+
}
120+
121+
/*
122+
* Depth First Search Visit
123+
*
124+
* DFS-Visit(G, u)
125+
* time = time + 1
126+
* u.d = time
127+
* u.color = GRAY
128+
* for each v ∈ G.Adj[u]
129+
* if v.color == WHITE
130+
* v.π = u
131+
* DFS-Visit(G, u)
132+
* u.color = BLACK
133+
* time = time + 1
134+
* u.f = time
135+
* */
136+
private static String sort(Graph graph, Vertex u, LinkedList<String> list) {
137+
time++;
138+
u.weight = time;
139+
u.color = Color.GRAY;
140+
graph.adj.get(u.label).next.forEach(label -> {
141+
if (graph.adj.get(label).color == Color.WHITE) {
142+
graph.adj.get(label).predecessor = u;
143+
list.addFirst(sort(graph, graph.adj.get(label), list));
144+
} else if (graph.adj.get(label).color == Color.GRAY) {
145+
/*
146+
* A back edge exists if an edge (u, v) connects a vertex u to its ancestor vertex v
147+
* in a depth first tree. If v.d ≤ u.d < u.f ≤ v.f
148+
*
149+
* In many cases, we will not know u.f, but v.color denotes the type of edge
150+
* */
151+
throw new BackEdgeException("Back edge: " + u.label + " -> " + label);
152+
}
153+
});
154+
u.color = Color.BLACK;
155+
time++;
156+
u.finished = time;
157+
return u.label;
158+
}
159+
}
160+

‎src/test/java/com/thealgorithms/sorts/TopologicalSortTest.java

Lines changed: 61 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,61 @@
1+
package com.thealgorithms.sorts;
2+
3+
import org.junit.jupiter.api.Test;
4+
import static org.junit.jupiter.api.Assertions.*;
5+
import com.thealgorithms.sorts.TopologicalSort.Graph;
6+
import com.thealgorithms.sorts.TopologicalSort.BackEdgeException;
7+
8+
import java.util.LinkedList;
9+
10+
class TopologicalSortTest {
11+
@Test
12+
void successTest() {
13+
/*
14+
* Professor Bumstead example DAG. Each directed edge means that garment u must be put on
15+
* before garment v.
16+
* */
17+
Graph graph = new Graph();
18+
graph.addEdge("shirt", "tie", "belt");
19+
graph.addEdge("tie", "jacket");
20+
graph.addEdge("belt", "jacket");
21+
graph.addEdge("watch", "");
22+
graph.addEdge("undershorts", "pants", "shoes");
23+
graph.addEdge("shoes", "");
24+
graph.addEdge("socks", "shoes");
25+
graph.addEdge("jacket","");
26+
graph.addEdge("pants", "belt", "shoes");
27+
LinkedList<String> expected = new LinkedList<>();
28+
expected.add("socks");
29+
expected.add("undershorts");
30+
expected.add("pants");
31+
expected.add("shoes");
32+
expected.add("watch");
33+
expected.add("shirt");
34+
expected.add("belt");
35+
expected.add("tie");
36+
expected.add("jacket");
37+
assertIterableEquals(expected, TopologicalSort.sort(graph));
38+
}
39+
40+
@Test
41+
public void failureTest() {
42+
43+
/*
44+
* Graph example from Geeks For Geeks
45+
* https://www.geeksforgeeks.org/tree-back-edge-and-cross-edges-in-dfs-of-graph/
46+
* */
47+
Graph graph = new Graph();
48+
graph.addEdge("1", "2", "3", "8");
49+
graph.addEdge("2", "4");
50+
graph.addEdge("3", "5");
51+
graph.addEdge("4", "6");
52+
graph.addEdge("5", "4", "7", "8");
53+
graph.addEdge("6", "2");
54+
graph.addEdge("7", "");
55+
graph.addEdge("8", "");
56+
Exception exception = assertThrows(BackEdgeException.class, () -> TopologicalSort.sort(graph));
57+
String expected = "This graph contains a cycle. No linear ordering is possible. " +
58+
"Back edge: 6 -> 2";
59+
assertEquals(exception.getMessage(), expected);
60+
}
61+
}

0 commit comments

Comments
 (0)