Commit | Line | Data |
---|---|---|
1b46d94d FG |
1 | /******************************************************************************* |
2 | * Copyright (c) 2015 École Polytechnique de Montréal | |
3 | * | |
4 | * All rights reserved. This program and the accompanying materials are | |
5 | * made available under the terms of the Eclipse Public License v1.0 which | |
6 | * accompanies this distribution, and is available at | |
7 | * http://www.eclipse.org/legal/epl-v10.html | |
8 | * | |
9 | * Contributors: | |
10 | * Francis Giraldeau - Initial API and implementation | |
11 | * Geneviève Bastien - Initial API and implementation | |
12 | *******************************************************************************/ | |
13 | ||
14 | package org.eclipse.tracecompass.analysis.graph.core.tests.graph; | |
15 | ||
16 | import static org.junit.Assert.assertEquals; | |
17 | import static org.junit.Assert.assertNotNull; | |
18 | import static org.junit.Assert.assertNotSame; | |
19 | import static org.junit.Assert.assertNull; | |
20 | ||
21 | import java.util.List; | |
22 | ||
23 | import org.eclipse.jdt.annotation.NonNull; | |
24 | import org.eclipse.tracecompass.analysis.graph.core.base.IGraphWorker; | |
25 | import org.eclipse.tracecompass.analysis.graph.core.base.ITmfGraphVisitor; | |
26 | import org.eclipse.tracecompass.analysis.graph.core.base.TmfEdge; | |
27 | import org.eclipse.tracecompass.analysis.graph.core.base.TmfEdge.EdgeType; | |
28 | import org.eclipse.tracecompass.analysis.graph.core.base.TmfGraph; | |
29 | import org.eclipse.tracecompass.analysis.graph.core.base.TmfVertex; | |
30 | import org.eclipse.tracecompass.analysis.graph.core.base.TmfVertex.EdgeDirection; | |
31 | import org.eclipse.tracecompass.analysis.graph.core.tests.stubs.TestGraphWorker; | |
32 | import org.eclipse.tracecompass.internal.analysis.graph.core.base.TmfGraphStatistics; | |
33 | import org.eclipse.tracecompass.tmf.core.timestamp.ITmfTimestamp; | |
34 | import org.eclipse.tracecompass.tmf.core.timestamp.TmfTimestamp; | |
35 | import org.junit.Test; | |
36 | ||
37 | /** | |
38 | * Test the basic functionalities of the {@link TmfGraph}, {@link TmfVertex} and | |
39 | * {@link TmfEdge} classes. | |
40 | * | |
41 | * @author Geneviève Bastien | |
42 | * @author Francis Giraldeau | |
43 | */ | |
44 | public class TmfGraphTest { | |
45 | ||
46 | private static final @NonNull IGraphWorker WORKER1 = new TestGraphWorker(1); | |
47 | private static final @NonNull IGraphWorker WORKER2 = new TestGraphWorker(2); | |
48 | ||
49 | private final @NonNull TmfGraph fGraph = new TmfGraph(); | |
50 | private final @NonNull TmfVertex fV0 = new TmfVertex(0); | |
51 | private final @NonNull TmfVertex fV1 = new TmfVertex(1); | |
52 | ||
53 | /** | |
54 | * Test the graph constructor | |
55 | */ | |
56 | @Test | |
57 | public void testDefaultConstructor() { | |
58 | TmfGraph g = new TmfGraph(); | |
59 | assertEquals(0, g.size()); | |
60 | } | |
61 | ||
62 | /** | |
63 | * Test the {@link TmfGraph#add(IGraphWorker, TmfVertex)} method: vertices are | |
64 | * added, but no edge between them is created | |
65 | */ | |
66 | @Test | |
67 | public void testAddVertex() { | |
68 | fGraph.add(WORKER1, fV0); | |
69 | fGraph.add(WORKER1, fV1); | |
70 | List<TmfVertex> list = fGraph.getNodesOf(WORKER1); | |
71 | assertEquals(2, list.size()); | |
72 | for (int i = 0; i < list.size() - 1; i++) { | |
73 | TmfVertex vertex = list.get(i); | |
74 | assertEquals(i, vertex.getTs()); | |
75 | assertNull(vertex.getEdge(EdgeDirection.OUTGOING_HORIZONTAL_EDGE)); | |
76 | assertNull(vertex.getEdge(EdgeDirection.INCOMING_HORIZONTAL_EDGE)); | |
77 | assertNull(vertex.getEdge(EdgeDirection.OUTGOING_VERTICAL_EDGE)); | |
78 | assertNull(vertex.getEdge(EdgeDirection.INCOMING_VERTICAL_EDGE)); | |
79 | } | |
80 | } | |
81 | ||
82 | /** | |
83 | * Test the {@link TmfGraph#append(IGraphWorker, TmfVertex)} and | |
84 | * {@link TmfGraph#append(IGraphWorker, TmfVertex, EdgeType)} methods: vertices | |
85 | * are added and links are created between them. | |
86 | */ | |
87 | @Test | |
88 | public void testAppendVertex() { | |
89 | /* Append without type */ | |
90 | fGraph.append(WORKER1, fV0); | |
91 | TmfEdge edge = fGraph.append(WORKER1, fV1); | |
92 | assertNotNull(edge); | |
93 | assertEquals(EdgeType.DEFAULT, edge.getType()); | |
94 | assertEquals(fV1, edge.getVertexTo()); | |
95 | assertEquals(fV0, edge.getVertexFrom()); | |
96 | assertEquals(fV1.getTs() - fV0.getTs(), edge.getDuration()); | |
97 | ||
98 | List<TmfVertex> list = fGraph.getNodesOf(WORKER1); | |
99 | assertEquals(2, list.size()); | |
100 | checkLinkHorizontal(list); | |
101 | assertEquals(fV0, fGraph.getHead(WORKER1)); | |
102 | assertEquals(fV1, fGraph.getTail(WORKER1)); | |
103 | ||
104 | /* Append with a type */ | |
105 | TmfVertex v2 = new TmfVertex(2); | |
106 | edge = fGraph.append(WORKER1, v2, EdgeType.BLOCKED); | |
107 | assertNotNull(edge); | |
108 | assertEquals(EdgeType.BLOCKED, edge.getType()); | |
109 | assertEquals(v2, edge.getVertexTo()); | |
110 | assertEquals(fV1, edge.getVertexFrom()); | |
111 | assertEquals(v2.getTs() - fV1.getTs(), edge.getDuration()); | |
112 | ||
113 | list = fGraph.getNodesOf(WORKER1); | |
114 | assertEquals(3, list.size()); | |
115 | checkLinkHorizontal(list); | |
116 | assertEquals(fV0, fGraph.getHead(WORKER1)); | |
117 | assertEquals(v2, fGraph.getTail(WORKER1)); | |
118 | } | |
119 | ||
120 | /** | |
121 | * Test that appending vertices in non chronological order gives error | |
122 | */ | |
123 | @Test(expected = IllegalArgumentException.class) | |
124 | public void testIllegalVertex() { | |
125 | fGraph.append(WORKER1, fV1); | |
126 | fGraph.append(WORKER1, fV0); | |
127 | } | |
128 | ||
129 | /** | |
130 | * Test the {@link TmfGraph#link(TmfVertex, TmfVertex)} and | |
131 | * {@link TmfGraph#link(TmfVertex, TmfVertex, EdgeType)} methods | |
132 | */ | |
133 | @Test | |
134 | public void testLink() { | |
135 | // Start with a first node | |
136 | fGraph.add(WORKER1, fV0); | |
137 | ||
138 | // Link with second node not in graph | |
139 | TmfEdge edge = fGraph.link(fV0, fV1); | |
140 | assertEquals(fV1, edge.getVertexTo()); | |
141 | assertEquals(fV0, edge.getVertexFrom()); | |
142 | assertEquals(EdgeType.DEFAULT, edge.getType()); | |
143 | assertEquals(fV1.getTs() - fV0.getTs(), edge.getDuration()); | |
144 | ||
145 | List<TmfVertex> list = fGraph.getNodesOf(WORKER1); | |
146 | assertEquals(2, list.size()); | |
147 | edge = fV1.getEdge(EdgeDirection.INCOMING_HORIZONTAL_EDGE); | |
148 | assertNotNull(edge); | |
149 | assertEquals(fV0, edge.getVertexFrom()); | |
150 | edge = fV0.getEdge(EdgeDirection.OUTGOING_HORIZONTAL_EDGE); | |
151 | assertNotNull(edge); | |
152 | assertEquals(fV1, edge.getVertexTo()); | |
153 | ||
154 | // Link with second node for the same object | |
155 | TmfVertex v2 = new TmfVertex(2); | |
156 | fGraph.add(WORKER1, v2); | |
157 | edge = fGraph.link(fV1, v2, EdgeType.NETWORK); | |
158 | assertEquals(v2, edge.getVertexTo()); | |
159 | assertEquals(fV1, edge.getVertexFrom()); | |
160 | assertEquals(EdgeType.NETWORK, edge.getType()); | |
161 | ||
162 | list = fGraph.getNodesOf(WORKER1); | |
163 | assertEquals(3, list.size()); | |
164 | edge = fV1.getEdge(EdgeDirection.OUTGOING_HORIZONTAL_EDGE); | |
165 | assertNotNull(edge); | |
166 | assertEquals(v2, edge.getVertexTo()); | |
167 | edge = v2.getEdge(EdgeDirection.INCOMING_HORIZONTAL_EDGE); | |
168 | assertNotNull(edge); | |
169 | assertEquals(fV1, edge.getVertexFrom()); | |
170 | ||
171 | // Link with second node for another object | |
172 | TmfVertex v3 = new TmfVertex(3); | |
173 | fGraph.add(WORKER2, v3); | |
174 | edge = fGraph.link(v2, v3, EdgeType.NETWORK); | |
175 | assertEquals(v3, edge.getVertexTo()); | |
176 | assertEquals(v2, edge.getVertexFrom()); | |
177 | assertEquals(EdgeType.NETWORK, edge.getType()); | |
178 | ||
179 | list = fGraph.getNodesOf(WORKER2); | |
180 | assertEquals(1, list.size()); | |
181 | ||
182 | list = fGraph.getNodesOf(WORKER1); | |
183 | assertEquals(3, list.size()); | |
184 | edge = v3.getEdge(EdgeDirection.INCOMING_VERTICAL_EDGE); | |
185 | assertNotNull(edge); | |
186 | assertEquals(v2, edge.getVertexFrom()); | |
187 | edge = v2.getEdge(EdgeDirection.OUTGOING_VERTICAL_EDGE); | |
188 | assertNotNull(edge); | |
189 | assertEquals(v3, edge.getVertexTo()); | |
190 | ||
191 | } | |
192 | ||
193 | /** | |
194 | * Verify that vertices in the list form a chain linked by edges and have no | |
195 | * vertical edges | |
196 | */ | |
197 | private static void checkLinkHorizontal(List<TmfVertex> list) { | |
198 | if (list.isEmpty()) { | |
199 | return; | |
200 | } | |
201 | for (int i = 0; i < list.size() - 1; i++) { | |
202 | TmfVertex v0 = list.get(i); | |
203 | TmfVertex v1 = list.get(i + 1); | |
204 | TmfEdge edge = v0.getEdge(EdgeDirection.OUTGOING_HORIZONTAL_EDGE); | |
205 | assertNotNull(edge); | |
206 | assertEquals(v0, edge.getVertexFrom()); | |
207 | assertEquals(v1, edge.getVertexTo()); | |
208 | edge = v1.getEdge(EdgeDirection.INCOMING_HORIZONTAL_EDGE); | |
209 | assertNotNull(edge); | |
210 | assertEquals(v0, edge.getVertexFrom()); | |
211 | assertEquals(v1, edge.getVertexTo()); | |
212 | assertNull(v1.getEdge(EdgeDirection.OUTGOING_VERTICAL_EDGE)); | |
213 | assertNull(v1.getEdge(EdgeDirection.INCOMING_VERTICAL_EDGE)); | |
214 | assertNull(v0.getEdge(EdgeDirection.OUTGOING_VERTICAL_EDGE)); | |
215 | assertNull(v0.getEdge(EdgeDirection.INCOMING_VERTICAL_EDGE)); | |
216 | } | |
217 | } | |
218 | ||
219 | /** | |
220 | * Test the {@link TmfGraph#getTail(IGraphWorker)} and | |
221 | * {@link TmfGraph#removeTail(IGraphWorker)} methods | |
222 | */ | |
223 | @Test | |
224 | public void testTail() { | |
225 | fGraph.append(WORKER1, fV0); | |
226 | fGraph.append(WORKER1, fV1); | |
227 | assertEquals(fV1, fGraph.getTail(WORKER1)); | |
228 | assertEquals(fV1, fGraph.removeTail(WORKER1)); | |
229 | assertEquals(fV0, fGraph.getTail(WORKER1)); | |
230 | } | |
231 | ||
232 | /** | |
233 | * Test the {@link TmfGraph#getHead()} methods | |
234 | */ | |
235 | @Test | |
236 | public void testHead() { | |
237 | fGraph.append(WORKER1, fV0); | |
238 | fGraph.append(WORKER1, fV1); | |
239 | assertEquals(fV0, fGraph.getHead()); | |
240 | assertEquals(fV0, fGraph.getHead(WORKER1)); | |
241 | assertEquals(fV0, fGraph.getHead(fV1)); | |
242 | assertEquals(fV0, fGraph.getHead(fV0)); | |
243 | } | |
244 | ||
245 | /** | |
246 | * The test {@link TmfGraph#getParentOf(TmfVertex)} method | |
247 | */ | |
248 | @Test | |
249 | public void testParent() { | |
250 | fGraph.append(WORKER1, fV0); | |
251 | fGraph.append(WORKER2, fV1); | |
252 | assertEquals(WORKER1, fGraph.getParentOf(fV0)); | |
253 | assertNotSame(WORKER1, fGraph.getParentOf(fV1)); | |
254 | assertEquals(WORKER2, fGraph.getParentOf(fV1)); | |
255 | } | |
256 | ||
257 | /** | |
258 | * Test the {@link TmfGraph#getVertexAt(ITmfTimestamp, IGraphWorker)} method | |
259 | */ | |
260 | @Test | |
261 | public void testVertexAt() { | |
262 | TmfVertex[] vertices = new TmfVertex[5]; | |
263 | for (int i = 0; i < 5; i++) { | |
264 | TmfVertex v = new TmfVertex((i + 1) * 5); | |
265 | vertices[i] = v; | |
266 | fGraph.append(WORKER1, v); | |
267 | } | |
268 | assertEquals(vertices[0], fGraph.getVertexAt(new TmfTimestamp(5), WORKER1)); | |
269 | assertEquals(vertices[0], fGraph.getVertexAt(new TmfTimestamp(0), WORKER1)); | |
270 | assertEquals(vertices[1], fGraph.getVertexAt(new TmfTimestamp(6), WORKER1)); | |
271 | assertEquals(vertices[3], fGraph.getVertexAt(new TmfTimestamp(19), WORKER1)); | |
272 | assertNull(fGraph.getVertexAt(new TmfTimestamp(19), WORKER2)); | |
273 | assertEquals(vertices[3], fGraph.getVertexAt(new TmfTimestamp(20), WORKER1)); | |
274 | assertEquals(vertices[4], fGraph.getVertexAt(new TmfTimestamp(21), WORKER1)); | |
275 | assertNull(fGraph.getVertexAt(new TmfTimestamp(26), WORKER1)); | |
276 | } | |
277 | ||
278 | /** | |
279 | * Test the {@link TmfVertex#linkHorizontal(TmfVertex)} with non | |
280 | * chronological timestamps | |
281 | */ | |
282 | @Test(expected = IllegalArgumentException.class) | |
283 | public void testCheckHorizontal() { | |
284 | TmfVertex n0 = new TmfVertex(10); | |
285 | TmfVertex n1 = new TmfVertex(0); | |
286 | n0.linkHorizontal(n1); | |
287 | } | |
288 | ||
289 | /** | |
290 | * Test the {@link TmfVertex#linkVertical(TmfVertex)} with non chronological | |
291 | * timestamps | |
292 | */ | |
293 | @Test(expected = IllegalArgumentException.class) | |
294 | public void testCheckVertical() { | |
295 | TmfVertex n0 = new TmfVertex(10); | |
296 | TmfVertex n1 = new TmfVertex(0); | |
297 | n0.linkVertical(n1); | |
298 | } | |
299 | ||
300 | private class ScanCountVertex implements ITmfGraphVisitor { | |
301 | public int nbVertex = 0; | |
302 | public int nbVLink = 0; | |
303 | public int nbHLink = 0; | |
304 | public int nbStartVertex = 0; | |
305 | ||
306 | @Override | |
307 | public void visitHead(TmfVertex node) { | |
308 | nbStartVertex++; | |
309 | } | |
310 | ||
311 | @Override | |
312 | public void visit(TmfVertex node) { | |
313 | nbVertex++; | |
314 | ||
315 | } | |
316 | ||
317 | @Override | |
318 | public void visit(TmfEdge edge, boolean horizontal) { | |
319 | if (horizontal) { | |
320 | nbHLink++; | |
321 | } else { | |
322 | nbVLink++; | |
323 | } | |
324 | } | |
325 | } | |
326 | ||
327 | /** | |
328 | * The following graph will be used | |
329 | * | |
330 | * <pre> | |
331 | * ____0___1___2___3___4___5___6___7___8___9___10___11___12___13___14___15 | |
332 | * | |
333 | * A *-------* *---*-------*---*---* *---*----*----*---------* | |
334 | * | | | | | | |
335 | * B *---*---*-------* *-------*------------* *----------* | |
336 | * </pre> | |
337 | */ | |
338 | @SuppressWarnings("null") | |
339 | private static @NonNull TmfGraph buildFullGraph() { | |
340 | TmfGraph graph = new TmfGraph(); | |
341 | TmfVertex[] vertexA; | |
342 | TmfVertex[] vertexB; | |
343 | long[] timesA = { 0, 2, 4, 5, 7, 8, 9, 10, 11, 12, 13, 15 }; | |
344 | long[] timesB = { 1, 2, 3, 5, 6, 8, 11, 12, 14 }; | |
345 | vertexA = new TmfVertex[timesA.length]; | |
346 | vertexB = new TmfVertex[timesB.length]; | |
347 | for (int i = 0; i < timesA.length; i++) { | |
348 | vertexA[i] = new TmfVertex(timesA[i]); | |
349 | } | |
350 | for (int i = 0; i < timesB.length; i++) { | |
351 | vertexB[i] = new TmfVertex(timesB[i]); | |
352 | } | |
353 | graph.append(WORKER1, vertexA[0]); | |
354 | graph.append(WORKER1, vertexA[1]); | |
355 | graph.add(WORKER1, vertexA[2]); | |
356 | graph.append(WORKER1, vertexA[3]); | |
357 | graph.append(WORKER1, vertexA[4]); | |
358 | graph.append(WORKER1, vertexA[5]); | |
359 | graph.append(WORKER1, vertexA[6]); | |
360 | graph.add(WORKER1, vertexA[7]); | |
361 | graph.append(WORKER1, vertexA[8]); | |
362 | graph.append(WORKER1, vertexA[9]); | |
363 | graph.append(WORKER1, vertexA[10]); | |
364 | graph.append(WORKER1, vertexA[11]); | |
365 | graph.append(WORKER2, vertexB[0]); | |
366 | graph.append(WORKER2, vertexB[1]); | |
367 | graph.append(WORKER2, vertexB[2]); | |
368 | graph.append(WORKER2, vertexB[3]); | |
369 | graph.add(WORKER2, vertexB[4]); | |
370 | graph.append(WORKER2, vertexB[5]); | |
371 | graph.append(WORKER2, vertexB[6]); | |
372 | graph.add(WORKER2, vertexB[7]); | |
373 | graph.append(WORKER2, vertexB[8]); | |
374 | vertexA[1].linkVertical(vertexB[1]); | |
375 | vertexB[3].linkVertical(vertexA[3]); | |
376 | vertexA[5].linkVertical(vertexB[5]); | |
377 | vertexB[6].linkVertical(vertexA[8]); | |
378 | vertexA[9].linkVertical(vertexB[7]); | |
379 | return graph; | |
380 | } | |
381 | ||
382 | /** | |
383 | * Test the {@link TmfGraph#scanLineTraverse(IGraphWorker, ITmfGraphVisitor)} method | |
384 | */ | |
385 | @Test | |
386 | public void testScanCount() { | |
387 | TmfGraph graph = buildFullGraph(); | |
388 | ScanCountVertex visitor = new ScanCountVertex(); | |
389 | graph.scanLineTraverse(graph.getHead(WORKER1), visitor); | |
390 | assertEquals(21, visitor.nbVertex); | |
391 | assertEquals(6, visitor.nbStartVertex); | |
392 | assertEquals(5, visitor.nbVLink); | |
393 | assertEquals(15, visitor.nbHLink); | |
394 | } | |
395 | ||
396 | /** | |
397 | * Test the {@link TmfGraphStatistics} class | |
398 | */ | |
399 | @Test | |
400 | public void testGraphStatistics() { | |
401 | TmfGraph graph = buildFullGraph(); | |
402 | TmfGraphStatistics stats = new TmfGraphStatistics(); | |
403 | stats.getGraphStatistics(graph, WORKER1); | |
404 | assertEquals(12, stats.getSum(WORKER1).longValue()); | |
405 | assertEquals(11, stats.getSum(WORKER2).longValue()); | |
406 | assertEquals(23, stats.getSum().longValue()); | |
407 | } | |
408 | ||
409 | } |