1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19 package org.apache.maven.project;
20
21 import java.util.ArrayList;
22 import java.util.Arrays;
23 import java.util.List;
24 import java.util.Set;
25 import java.util.stream.Collectors;
26
27 import org.apache.maven.project.Graph.Vertex;
28 import org.junit.jupiter.api.Test;
29
30 import static org.junit.jupiter.api.Assertions.assertEquals;
31 import static org.junit.jupiter.api.Assertions.assertFalse;
32 import static org.junit.jupiter.api.Assertions.assertNotNull;
33 import static org.junit.jupiter.api.Assertions.assertThrows;
34 import static org.junit.jupiter.api.Assertions.assertTrue;
35
36 public class GraphTest {
37
38 @Test
39 public void testGraph() throws CycleDetectedException {
40 Graph graph = new Graph();
41 graph.addVertex("a");
42 assertEquals(1, graph.getVertices().size());
43 assertEquals("a", graph.getVertex("a").getLabel());
44 graph.addVertex("a");
45 assertEquals(1, graph.getVertices().size());
46 assertEquals("a", graph.getVertex("a").getLabel());
47
48 graph.addVertex("b");
49 assertEquals(2, graph.getVertices().size());
50 assertFalse(hasEdge(graph, "a", "b"));
51 assertFalse(hasEdge(graph, "b", "a"));
52
53 Vertex a = graph.getVertex("a");
54 Vertex b = graph.getVertex("b");
55 assertEquals("a", a.getLabel());
56 assertEquals("b", b.getLabel());
57
58 addEdge(graph, "a", "b");
59 assertTrue(a.getChildren().contains(b));
60 assertTrue(b.getParents().contains(a));
61 assertTrue(hasEdge(graph, "a", "b"));
62 assertFalse(hasEdge(graph, "b", "a"));
63
64 addEdge(graph, "c", "d");
65 assertEquals(4, graph.getVertices().size());
66
67 Vertex c = graph.getVertex("c");
68 Vertex d = graph.getVertex("d");
69 assertEquals("a", a.getLabel());
70 assertEquals("b", b.getLabel());
71 assertEquals("c", c.getLabel());
72 assertEquals("d", d.getLabel());
73 assertFalse(hasEdge(graph, "b", "a"));
74 assertFalse(hasEdge(graph, "a", "c"));
75 assertFalse(hasEdge(graph, "a", "d"));
76 assertTrue(hasEdge(graph, "c", "d"));
77 assertFalse(hasEdge(graph, "d", "c"));
78
79 Set<String> labels = graph.getVertices().stream().map(Vertex::getLabel).collect(Collectors.toSet());
80 assertEquals(4, labels.size());
81 assertTrue(labels.contains("a"));
82 assertTrue(labels.contains("b"));
83 assertTrue(labels.contains("c"));
84 assertTrue(labels.contains("d"));
85
86 addEdge(graph, "a", "d");
87 assertEquals(2, a.getChildren().size());
88 assertTrue(a.getChildren().contains(b));
89 assertTrue(a.getChildren().contains(d));
90 assertEquals(2, d.getParents().size());
91 assertTrue(d.getParents().contains(a));
92 assertTrue(d.getParents().contains(c));
93 }
94
95 @Test
96 public void testCycleDetection() throws Exception {
97 Graph graph1 = new Graph();
98 addEdge(graph1, "a", "b");
99 addEdge(graph1, "b", "c");
100
101 Graph graph2 = new Graph();
102 addEdge(graph2, "a", "b");
103 addEdge(graph2, "b", "c");
104 CycleDetectedException cde = assertThrows(CycleDetectedException.class, () -> addEdge(graph2, "c", "a"));
105 List<String> cycle = cde.getCycle();
106 assertNotNull(cycle, "Cycle should be not null");
107 assertTrue(cycle.contains("a"), "Cycle contains 'a'");
108 assertTrue(cycle.contains("b"), "Cycle contains 'b'");
109 assertTrue(cycle.contains("c"), "Cycle contains 'c'");
110
111 Graph graph3 = new Graph();
112 addEdge(graph3, "a", "b");
113 addEdge(graph3, "b", "c");
114 addEdge(graph3, "b", "d");
115 addEdge(graph3, "a", "d");
116
117 Graph graph4 = new Graph();
118 addEdge(graph4, "a", "b");
119 addEdge(graph4, "b", "c");
120 addEdge(graph4, "b", "d");
121 addEdge(graph4, "a", "d");
122 cde = assertThrows(CycleDetectedException.class, () -> addEdge(graph4, "c", "a"));
123 assertEquals(Arrays.asList("a", "b", "c", "a"), cde.getCycle());
124
125 Graph graph5 = new Graph();
126 addEdge(graph5, "a", "b");
127 addEdge(graph5, "b", "c");
128 addEdge(graph5, "b", "f");
129 addEdge(graph5, "f", "g");
130 addEdge(graph5, "g", "h");
131 addEdge(graph5, "c", "d");
132 addEdge(graph5, "d", "e");
133 cde = assertThrows(CycleDetectedException.class, () -> addEdge(graph5, "e", "b"));
134 assertEquals(Arrays.asList("b", "c", "d", "e", "b"), cde.getCycle());
135 assertTrue(hasEdge(graph5, "a", "b"));
136 assertTrue(hasEdge(graph5, "b", "c"));
137 assertTrue(hasEdge(graph5, "b", "f"));
138 assertTrue(hasEdge(graph5, "f", "g"));
139 assertTrue(hasEdge(graph5, "g", "h"));
140 assertTrue(hasEdge(graph5, "c", "d"));
141 assertTrue(hasEdge(graph5, "d", "e"));
142 assertFalse(hasEdge(graph5, "e", "b"));
143 }
144
145 @Test
146 public void testDfs() throws CycleDetectedException {
147 Graph graph1 = new Graph();
148 addEdge(graph1, "a", "b");
149 addEdge(graph1, "b", "c");
150 List<String> expected1 = new ArrayList<>();
151 expected1.add("c");
152 expected1.add("b");
153 expected1.add("a");
154 List<String> actual1 = graph1.visitAll();
155 assertEquals(expected1, actual1);
156
157 Graph graph2 = new Graph();
158 graph2.addVertex("a");
159 graph2.addVertex("b");
160 graph2.addVertex("c");
161 addEdge(graph2, "b", "a");
162 addEdge(graph2, "c", "b");
163 List<String> expected2 = new ArrayList<>();
164 expected2.add("a");
165 expected2.add("b");
166 expected2.add("c");
167 List<String> actual2 = graph2.visitAll();
168 assertEquals(expected2, actual2);
169
170 Graph graph3 = new Graph();
171 graph3.addVertex("a");
172 graph3.addVertex("b");
173 graph3.addVertex("c");
174 graph3.addVertex("d");
175 graph3.addVertex("e");
176 graph3.addVertex("f");
177 addEdge(graph3, "a", "b");
178 addEdge(graph3, "b", "c");
179 addEdge(graph3, "b", "d");
180 addEdge(graph3, "c", "d");
181 addEdge(graph3, "c", "e");
182 addEdge(graph3, "f", "d");
183 addEdge(graph3, "e", "f");
184 addEdge(graph3, "f", "g");
185 List<String> expected3 = new ArrayList<>();
186 expected3.add("d");
187 expected3.add("g");
188 expected3.add("f");
189 expected3.add("e");
190 expected3.add("c");
191 expected3.add("b");
192 expected3.add("a");
193 List<String> actual3 = graph3.visitAll();
194 assertEquals(expected3, actual3);
195
196 Graph graph4 = new Graph();
197 graph4.addVertex("f");
198 graph4.addVertex("e");
199 graph4.addVertex("d");
200 graph4.addVertex("c");
201 graph4.addVertex("a");
202 graph4.addVertex("b");
203 addEdge(graph4, "a", "b");
204 addEdge(graph4, "b", "c");
205 addEdge(graph4, "b", "d");
206 addEdge(graph4, "c", "d");
207 addEdge(graph4, "c", "e");
208 addEdge(graph4, "f", "d");
209 addEdge(graph4, "e", "f");
210
211 List<String> expected4 = new ArrayList<>();
212 expected4.add("d");
213 expected4.add("f");
214 expected4.add("e");
215 expected4.add("c");
216 expected4.add("b");
217 expected4.add("a");
218 List<String> actual4 = graph4.visitAll();
219 assertEquals(expected4, actual4);
220 }
221
222 static void addEdge(Graph graph, String v1, String v2) throws CycleDetectedException {
223 Vertex vx1 = graph.addVertex(v1);
224 Vertex vx2 = graph.addVertex(v2);
225 graph.addEdge(vx1, vx2);
226 }
227
228 static boolean hasEdge(Graph graph, String v1, String v2) {
229 Vertex vx1 = graph.getVertex(v1);
230 Vertex vx2 = graph.getVertex(v2);
231 return vx1 != null && vx2 != null && vx1.children.contains(vx2);
232 }
233 }