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.List;
20
21 import org.junit.jupiter.api.Test;
22
23 import static org.junit.jupiter.api.Assertions.assertEquals;
24 import static org.junit.jupiter.api.Assertions.assertFalse;
25 import static org.junit.jupiter.api.Assertions.assertNotNull;
26 import static org.junit.jupiter.api.Assertions.assertTrue;
27 import static org.junit.jupiter.api.Assertions.fail;
28
29
30
31
32
33
34
35
36 public class CycleDetectorTest {
37
38
39
40
41 @Test
42 public void testCycyleDetection() {
43
44
45
46
47 try {
48 final DAG dag1 = new DAG();
49
50 dag1.addEdge("a", "b");
51
52 dag1.addEdge("b", "c");
53
54 } catch (CycleDetectedException e) {
55
56 fail("Cycle should not be detected");
57 }
58
59
60
61
62
63
64
65 try {
66 final DAG dag2 = new DAG();
67
68 dag2.addEdge("a", "b");
69
70 dag2.addEdge("b", "c");
71
72 dag2.addEdge("c", "a");
73
74 fail("Cycle should be detected");
75
76 } catch (CycleDetectedException e) {
77
78 final List<String> cycle = e.getCycle();
79
80 assertNotNull(cycle, "Cycle should be not null");
81
82 assertTrue(cycle.contains("a"), "Cycle contains 'a'");
83
84 assertTrue(cycle.contains("b"), "Cycle contains 'b'");
85
86 assertTrue(cycle.contains("c"), "Cycle contains 'c'");
87 }
88
89
90
91
92
93 try {
94 final DAG dag3 = new DAG();
95
96 dag3.addEdge("a", "b");
97
98 dag3.addEdge("b", "c");
99
100 dag3.addEdge("b", "d");
101
102 dag3.addEdge("a", "d");
103
104 } catch (CycleDetectedException e) {
105 fail("Cycle should not be detected");
106 }
107
108
109
110
111
112
113
114 try {
115 final DAG dag4 = new DAG();
116
117 dag4.addEdge("a", "b");
118
119 dag4.addEdge("b", "c");
120
121 dag4.addEdge("b", "d");
122
123 dag4.addEdge("a", "d");
124
125 dag4.addEdge("c", "a");
126
127 fail("Cycle should be detected");
128
129 } catch (CycleDetectedException e) {
130 final List<String> cycle = e.getCycle();
131
132 assertNotNull(cycle, "Cycle should be not null");
133
134 assertEquals("a", (String) cycle.get(0), "Cycle contains 'a'");
135
136 assertEquals("b", cycle.get(1), "Cycle contains 'b'");
137
138 assertEquals("c", cycle.get(2), "Cycle contains 'c'");
139
140 assertEquals("a", (String) cycle.get(3), "Cycle contains 'a'");
141 }
142
143
144
145
146
147
148
149
150
151 final DAG dag5 = new DAG();
152
153 try {
154
155 dag5.addEdge("a", "b");
156
157 dag5.addEdge("b", "c");
158
159 dag5.addEdge("b", "f");
160
161 dag5.addEdge("f", "g");
162
163 dag5.addEdge("g", "h");
164
165 dag5.addEdge("c", "d");
166
167 dag5.addEdge("d", "e");
168
169 dag5.addEdge("e", "b");
170
171 fail("Cycle should be detected");
172
173 } catch (CycleDetectedException e) {
174 final List<String> cycle = e.getCycle();
175
176 assertNotNull(cycle, "Cycle should be not null");
177
178 assertEquals(5, cycle.size(), "Cycle contains 5 elements");
179
180 assertEquals("b", (String) cycle.get(0), "Cycle contains 'b'");
181
182 assertEquals("c", cycle.get(1), "Cycle contains 'c'");
183
184 assertEquals("d", cycle.get(2), "Cycle contains 'd'");
185
186 assertEquals("e", (String) cycle.get(3), "Cycle contains 'e'");
187
188 assertEquals("b", (String) cycle.get(4), "Cycle contains 'b'");
189
190 assertTrue(dag5.hasEdge("a", "b"), "Edge exists");
191
192 assertTrue(dag5.hasEdge("b", "c"), "Edge exists");
193
194 assertTrue(dag5.hasEdge("b", "f"), "Edge exists");
195
196 assertTrue(dag5.hasEdge("f", "g"), "Edge exists");
197
198 assertTrue(dag5.hasEdge("g", "h"), "Edge exists");
199
200 assertTrue(dag5.hasEdge("c", "d"), "Edge exists");
201
202 assertTrue(dag5.hasEdge("d", "e"), "Edge exists");
203
204 assertFalse(dag5.hasEdge("e", "b"));
205 }
206 }
207 }