/
TopologicalSortTest.java
62 lines (57 loc) · 2.16 KB
/
TopologicalSortTest.java
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
package com.thealgorithms.sorts;
import static org.junit.jupiter.api.Assertions.assertEquals;
import static org.junit.jupiter.api.Assertions.assertIterableEquals;
import static org.junit.jupiter.api.Assertions.assertThrows;
import com.thealgorithms.sorts.TopologicalSort.Graph;
import java.util.LinkedList;
import org.junit.jupiter.api.Test;
class TopologicalSortTest {
@Test
void successTest() {
/*
* Professor Bumstead example DAG. Each directed edge means that garment u must be put on
* before garment v.
* */
Graph graph = new Graph();
graph.addEdge("shirt", "tie", "belt");
graph.addEdge("tie", "jacket");
graph.addEdge("belt", "jacket");
graph.addEdge("watch", "");
graph.addEdge("undershorts", "pants", "shoes");
graph.addEdge("shoes", "");
graph.addEdge("socks", "shoes");
graph.addEdge("jacket", "");
graph.addEdge("pants", "belt", "shoes");
LinkedList<String> expected = new LinkedList<>();
expected.add("socks");
expected.add("undershorts");
expected.add("pants");
expected.add("shoes");
expected.add("watch");
expected.add("shirt");
expected.add("belt");
expected.add("tie");
expected.add("jacket");
assertIterableEquals(expected, TopologicalSort.sort(graph));
}
@Test
public void failureTest() {
/*
* Graph example from Geeks For Geeks
* https://www.geeksforgeeks.org/tree-back-edge-and-cross-edges-in-dfs-of-graph/
* */
Graph graph = new Graph();
graph.addEdge("1", "2", "3", "8");
graph.addEdge("2", "4");
graph.addEdge("3", "5");
graph.addEdge("4", "6");
graph.addEdge("5", "4", "7", "8");
graph.addEdge("6", "2");
graph.addEdge("7", "");
graph.addEdge("8", "");
Exception exception = assertThrows(RuntimeException.class, () -> TopologicalSort.sort(graph));
String expected = "This graph contains a cycle. No linear ordering is possible. "
+ "Back edge: 6 -> 2";
assertEquals(exception.getMessage(), expected);
}
}