1 package org.codehaus.plexus.util.dag;
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19 import java.util.ArrayList;
20 import java.util.List;
21
22 import org.junit.jupiter.api.Test;
23
24 import static org.junit.jupiter.api.Assertions.assertEquals;
25
26
27
28
29
30
31
32
33 public class TopologicalSorterTest {
34
35
36
37
38
39 @Test
40 public void testDfs() throws CycleDetectedException {
41
42
43
44 final DAG dag1 = new DAG();
45
46 dag1.addEdge("a", "b");
47
48 dag1.addEdge("b", "c");
49
50 final List<String> expected1 = new ArrayList<String>();
51
52 expected1.add("c");
53
54 expected1.add("b");
55
56 expected1.add("a");
57
58 final List<String> actual1 = TopologicalSorter.sort(dag1);
59
60 assertEquals(expected1, actual1, "Order is different then expected");
61
62
63
64
65
66 final DAG dag2 = new DAG();
67
68 dag2.addVertex("a");
69
70 dag2.addVertex("b");
71
72 dag2.addVertex("c");
73
74 dag2.addEdge("b", "a");
75
76 dag2.addEdge("c", "b");
77
78 final List<String> expected2 = new ArrayList<String>();
79
80 expected2.add("a");
81
82 expected2.add("b");
83
84 expected2.add("c");
85
86 final List<String> actual2 = TopologicalSorter.sort(dag2);
87
88 assertEquals(expected2, actual2, "Order is different then expected");
89
90
91
92
93
94
95
96 final DAG dag3 = new DAG();
97
98
99 dag3.addVertex("a");
100
101 dag3.addVertex("b");
102
103 dag3.addVertex("c");
104
105 dag3.addVertex("d");
106
107 dag3.addVertex("e");
108
109 dag3.addVertex("f");
110
111 dag3.addEdge("a", "b");
112
113 dag3.addEdge("b", "c");
114
115 dag3.addEdge("b", "d");
116
117 dag3.addEdge("c", "d");
118
119 dag3.addEdge("c", "e");
120
121 dag3.addEdge("f", "d");
122
123 dag3.addEdge("e", "f");
124
125 dag3.addEdge("f", "g");
126
127 final List<String> expected3 = new ArrayList<String>();
128
129 expected3.add("d");
130
131 expected3.add("g");
132
133 expected3.add("f");
134
135 expected3.add("e");
136
137 expected3.add("c");
138
139 expected3.add("b");
140
141 expected3.add("a");
142
143 final List<String> actual3 = TopologicalSorter.sort(dag3);
144
145 assertEquals(expected3, actual3, "Order is different then expected");
146
147
148
149
150
151
152
153 final DAG dag4 = new DAG();
154
155
156 dag4.addVertex("f");
157
158 dag4.addVertex("e");
159
160 dag4.addVertex("d");
161
162 dag4.addVertex("c");
163
164 dag4.addVertex("a");
165
166 dag4.addVertex("b");
167
168 dag4.addEdge("a", "b");
169
170 dag4.addEdge("b", "c");
171
172 dag4.addEdge("b", "d");
173
174 dag4.addEdge("c", "d");
175
176 dag4.addEdge("c", "e");
177
178 dag4.addEdge("f", "d");
179
180 dag4.addEdge("e", "f");
181
182 final List<String> expected4 = new ArrayList<String>();
183
184 expected4.add("d");
185
186 expected4.add("f");
187
188 expected4.add("e");
189
190 expected4.add("c");
191
192 expected4.add("b");
193
194 expected4.add("a");
195
196 final List<String> actual4 = TopologicalSorter.sort(dag4);
197
198 assertEquals(expected4, actual4, "Order is different then expected");
199 }
200 }