1 /*******************************************************************************
2 * Copyright (c) 2015 École Polytechnique de Montréal
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
10 * Francis Giraldeau - Initial API and implementation
11 * Geneviève Bastien - Initial API and implementation
12 *******************************************************************************/
14 package org
.eclipse
.tracecompass
.analysis
.graph
.core
.tests
.graph
;
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
;
21 import java
.util
.HashSet
;
22 import java
.util
.List
;
25 import org
.eclipse
.jdt
.annotation
.NonNull
;
26 import org
.eclipse
.tracecompass
.analysis
.graph
.core
.base
.CycleDetectedException
;
27 import org
.eclipse
.tracecompass
.analysis
.graph
.core
.base
.IGraphWorker
;
28 import org
.eclipse
.tracecompass
.analysis
.graph
.core
.base
.ITmfGraphVisitor
;
29 import org
.eclipse
.tracecompass
.analysis
.graph
.core
.base
.TmfEdge
;
30 import org
.eclipse
.tracecompass
.analysis
.graph
.core
.base
.TmfEdge
.EdgeType
;
31 import org
.eclipse
.tracecompass
.analysis
.graph
.core
.base
.TmfGraph
;
32 import org
.eclipse
.tracecompass
.analysis
.graph
.core
.base
.TmfVertex
;
33 import org
.eclipse
.tracecompass
.analysis
.graph
.core
.base
.TmfVertex
.EdgeDirection
;
34 import org
.eclipse
.tracecompass
.analysis
.graph
.core
.tests
.stubs
.TestGraphWorker
;
35 import org
.eclipse
.tracecompass
.internal
.analysis
.graph
.core
.base
.TmfGraphStatistics
;
36 import org
.eclipse
.tracecompass
.tmf
.core
.timestamp
.ITmfTimestamp
;
37 import org
.eclipse
.tracecompass
.tmf
.core
.timestamp
.TmfTimestamp
;
38 import org
.junit
.Test
;
41 * Test the basic functionalities of the {@link TmfGraph}, {@link TmfVertex} and
42 * {@link TmfEdge} classes.
44 * @author Geneviève Bastien
45 * @author Francis Giraldeau
47 public class TmfGraphTest
{
49 private static final @NonNull IGraphWorker WORKER1
= new TestGraphWorker(1);
50 private static final @NonNull IGraphWorker WORKER2
= new TestGraphWorker(2);
51 private static final @NonNull IGraphWorker WORKER3
= new TestGraphWorker(3);
53 private final @NonNull TmfGraph fGraph
= new TmfGraph();
54 private final @NonNull TmfVertex fV0
= new TmfVertex(0);
55 private final @NonNull TmfVertex fV1
= new TmfVertex(1);
58 * Test the graph constructor
61 public void testDefaultConstructor() {
62 TmfGraph g
= new TmfGraph();
63 assertEquals(0, g
.size());
67 * Test the {@link TmfGraph#add(IGraphWorker, TmfVertex)} method: vertices are
68 * added, but no edge between them is created
71 public void testAddVertex() {
72 fGraph
.add(WORKER1
, fV0
);
73 fGraph
.add(WORKER1
, fV1
);
74 List
<TmfVertex
> list
= fGraph
.getNodesOf(WORKER1
);
75 assertEquals(2, list
.size());
76 for (int i
= 0; i
< list
.size() - 1; i
++) {
77 TmfVertex vertex
= list
.get(i
);
78 assertEquals(i
, vertex
.getTs());
79 assertNull(vertex
.getEdge(EdgeDirection
.OUTGOING_HORIZONTAL_EDGE
));
80 assertNull(vertex
.getEdge(EdgeDirection
.INCOMING_HORIZONTAL_EDGE
));
81 assertNull(vertex
.getEdge(EdgeDirection
.OUTGOING_VERTICAL_EDGE
));
82 assertNull(vertex
.getEdge(EdgeDirection
.INCOMING_VERTICAL_EDGE
));
87 * Test the {@link TmfGraph#append(IGraphWorker, TmfVertex)} and
88 * {@link TmfGraph#append(IGraphWorker, TmfVertex, EdgeType)} methods: vertices
89 * are added and links are created between them.
92 public void testAppendVertex() {
93 /* Append without type */
94 fGraph
.append(WORKER1
, fV0
);
95 TmfEdge edge
= fGraph
.append(WORKER1
, fV1
);
97 assertEquals(EdgeType
.DEFAULT
, edge
.getType());
98 assertEquals(fV1
, edge
.getVertexTo());
99 assertEquals(fV0
, edge
.getVertexFrom());
100 assertEquals(fV1
.getTs() - fV0
.getTs(), edge
.getDuration());
102 List
<TmfVertex
> list
= fGraph
.getNodesOf(WORKER1
);
103 assertEquals(2, list
.size());
104 checkLinkHorizontal(list
);
105 assertEquals(fV0
, fGraph
.getHead(WORKER1
));
106 assertEquals(fV1
, fGraph
.getTail(WORKER1
));
108 /* Append with a type */
109 TmfVertex v2
= new TmfVertex(2);
110 edge
= fGraph
.append(WORKER1
, v2
, EdgeType
.BLOCKED
);
112 assertEquals(EdgeType
.BLOCKED
, edge
.getType());
113 assertEquals(v2
, edge
.getVertexTo());
114 assertEquals(fV1
, edge
.getVertexFrom());
115 assertEquals(v2
.getTs() - fV1
.getTs(), edge
.getDuration());
117 list
= fGraph
.getNodesOf(WORKER1
);
118 assertEquals(3, list
.size());
119 checkLinkHorizontal(list
);
120 assertEquals(fV0
, fGraph
.getHead(WORKER1
));
121 assertEquals(v2
, fGraph
.getTail(WORKER1
));
125 * Test that appending vertices in non chronological order gives error
127 @Test(expected
= IllegalArgumentException
.class)
128 public void testIllegalVertex() {
129 fGraph
.append(WORKER1
, fV1
);
130 fGraph
.append(WORKER1
, fV0
);
134 * Test the {@link TmfGraph#link(TmfVertex, TmfVertex)} and
135 * {@link TmfGraph#link(TmfVertex, TmfVertex, EdgeType)} methods
138 public void testLink() {
139 // Start with a first node
140 fGraph
.add(WORKER1
, fV0
);
142 // Link with second node not in graph
143 TmfEdge edge
= fGraph
.link(fV0
, fV1
);
144 assertEquals(fV1
, edge
.getVertexTo());
145 assertEquals(fV0
, edge
.getVertexFrom());
146 assertEquals(EdgeType
.DEFAULT
, edge
.getType());
147 assertEquals(fV1
.getTs() - fV0
.getTs(), edge
.getDuration());
149 List
<TmfVertex
> list
= fGraph
.getNodesOf(WORKER1
);
150 assertEquals(2, list
.size());
151 edge
= fV1
.getEdge(EdgeDirection
.INCOMING_HORIZONTAL_EDGE
);
153 assertEquals(fV0
, edge
.getVertexFrom());
154 edge
= fV0
.getEdge(EdgeDirection
.OUTGOING_HORIZONTAL_EDGE
);
156 assertEquals(fV1
, edge
.getVertexTo());
158 // Link with second node for the same object
159 TmfVertex v2
= new TmfVertex(2);
160 fGraph
.add(WORKER1
, v2
);
161 edge
= fGraph
.link(fV1
, v2
, EdgeType
.NETWORK
);
162 assertEquals(v2
, edge
.getVertexTo());
163 assertEquals(fV1
, edge
.getVertexFrom());
164 assertEquals(EdgeType
.NETWORK
, edge
.getType());
166 list
= fGraph
.getNodesOf(WORKER1
);
167 assertEquals(3, list
.size());
168 edge
= fV1
.getEdge(EdgeDirection
.OUTGOING_HORIZONTAL_EDGE
);
170 assertEquals(v2
, edge
.getVertexTo());
171 edge
= v2
.getEdge(EdgeDirection
.INCOMING_HORIZONTAL_EDGE
);
173 assertEquals(fV1
, edge
.getVertexFrom());
175 // Link with second node for another object
176 TmfVertex v3
= new TmfVertex(3);
177 fGraph
.add(WORKER2
, v3
);
178 edge
= fGraph
.link(v2
, v3
, EdgeType
.NETWORK
);
179 assertEquals(v3
, edge
.getVertexTo());
180 assertEquals(v2
, edge
.getVertexFrom());
181 assertEquals(EdgeType
.NETWORK
, edge
.getType());
183 list
= fGraph
.getNodesOf(WORKER2
);
184 assertEquals(1, list
.size());
186 list
= fGraph
.getNodesOf(WORKER1
);
187 assertEquals(3, list
.size());
188 edge
= v3
.getEdge(EdgeDirection
.INCOMING_VERTICAL_EDGE
);
190 assertEquals(v2
, edge
.getVertexFrom());
191 edge
= v2
.getEdge(EdgeDirection
.OUTGOING_VERTICAL_EDGE
);
193 assertEquals(v3
, edge
.getVertexTo());
198 * Verify that vertices in the list form a chain linked by edges and have no
201 private static void checkLinkHorizontal(List
<TmfVertex
> list
) {
202 if (list
.isEmpty()) {
205 for (int i
= 0; i
< list
.size() - 1; i
++) {
206 TmfVertex v0
= list
.get(i
);
207 TmfVertex v1
= list
.get(i
+ 1);
208 TmfEdge edge
= v0
.getEdge(EdgeDirection
.OUTGOING_HORIZONTAL_EDGE
);
210 assertEquals(v0
, edge
.getVertexFrom());
211 assertEquals(v1
, edge
.getVertexTo());
212 edge
= v1
.getEdge(EdgeDirection
.INCOMING_HORIZONTAL_EDGE
);
214 assertEquals(v0
, edge
.getVertexFrom());
215 assertEquals(v1
, edge
.getVertexTo());
216 assertNull(v1
.getEdge(EdgeDirection
.OUTGOING_VERTICAL_EDGE
));
217 assertNull(v1
.getEdge(EdgeDirection
.INCOMING_VERTICAL_EDGE
));
218 assertNull(v0
.getEdge(EdgeDirection
.OUTGOING_VERTICAL_EDGE
));
219 assertNull(v0
.getEdge(EdgeDirection
.INCOMING_VERTICAL_EDGE
));
224 * Test the {@link TmfGraph#getTail(IGraphWorker)} and
225 * {@link TmfGraph#removeTail(IGraphWorker)} methods
228 public void testTail() {
229 fGraph
.append(WORKER1
, fV0
);
230 fGraph
.append(WORKER1
, fV1
);
231 assertEquals(fV1
, fGraph
.getTail(WORKER1
));
232 assertEquals(fV1
, fGraph
.removeTail(WORKER1
));
233 assertEquals(fV0
, fGraph
.getTail(WORKER1
));
237 * Test the {@link TmfGraph#getHead()} methods
240 public void testHead() {
241 assertNull(fGraph
.getHead());
242 fGraph
.append(WORKER1
, fV0
);
243 fGraph
.append(WORKER1
, fV1
);
244 assertEquals(fV0
, fGraph
.getHead());
245 assertEquals(fV0
, fGraph
.getHead(WORKER1
));
246 assertEquals(fV0
, fGraph
.getHead(fV1
));
247 assertEquals(fV0
, fGraph
.getHead(fV0
));
251 * Test the {@link TmfGraph#getHead()} methods with 2 workers
254 public void testHead2() {
255 fGraph
.append(WORKER1
, fV1
);
256 fGraph
.append(WORKER2
, fV0
);
257 assertEquals(fV0
, fGraph
.getHead());
258 assertEquals(fV1
, fGraph
.getHead(WORKER1
));
259 assertEquals(fV0
, fGraph
.getHead(WORKER2
));
260 assertEquals(fV1
, fGraph
.getHead(fV1
));
261 assertEquals(fV0
, fGraph
.getHead(fV0
));
265 * The test {@link TmfGraph#getParentOf(TmfVertex)} method
268 public void testParent() {
269 fGraph
.append(WORKER1
, fV0
);
270 fGraph
.append(WORKER2
, fV1
);
271 assertEquals(WORKER1
, fGraph
.getParentOf(fV0
));
272 assertNotSame(WORKER1
, fGraph
.getParentOf(fV1
));
273 assertEquals(WORKER2
, fGraph
.getParentOf(fV1
));
277 * Test the {@link TmfGraph#getVertexAt(ITmfTimestamp, IGraphWorker)} method
280 public void testVertexAt() {
281 TmfVertex
[] vertices
= new TmfVertex
[5];
282 for (int i
= 0; i
< 5; i
++) {
283 TmfVertex v
= new TmfVertex((i
+ 1) * 5);
285 fGraph
.append(WORKER1
, v
);
287 assertEquals(vertices
[0], fGraph
.getVertexAt(new TmfTimestamp(5), WORKER1
));
288 assertEquals(vertices
[0], fGraph
.getVertexAt(new TmfTimestamp(0), WORKER1
));
289 assertEquals(vertices
[1], fGraph
.getVertexAt(new TmfTimestamp(6), WORKER1
));
290 assertEquals(vertices
[3], fGraph
.getVertexAt(new TmfTimestamp(19), WORKER1
));
291 assertNull(fGraph
.getVertexAt(new TmfTimestamp(19), WORKER2
));
292 assertEquals(vertices
[3], fGraph
.getVertexAt(new TmfTimestamp(20), WORKER1
));
293 assertEquals(vertices
[4], fGraph
.getVertexAt(new TmfTimestamp(21), WORKER1
));
294 assertNull(fGraph
.getVertexAt(new TmfTimestamp(26), WORKER1
));
298 * Test the {@link TmfVertex#linkHorizontal(TmfVertex)} with non
299 * chronological timestamps
301 @Test(expected
= IllegalArgumentException
.class)
302 public void testCheckHorizontal() {
303 TmfVertex n0
= new TmfVertex(10);
304 TmfVertex n1
= new TmfVertex(0);
305 n0
.linkHorizontal(n1
);
309 * Test the {@link TmfVertex#linkVertical(TmfVertex)} with non chronological
312 @Test(expected
= IllegalArgumentException
.class)
313 public void testCheckVertical() {
314 TmfVertex n0
= new TmfVertex(10);
315 TmfVertex n1
= new TmfVertex(0);
319 private class ScanCountVertex
implements ITmfGraphVisitor
{
320 public int nbVertex
= 0;
321 public int nbVLink
= 0;
322 public int nbHLink
= 0;
323 public int nbStartVertex
= 0;
326 public void visitHead(TmfVertex node
) {
331 public void visit(TmfVertex node
) {
337 public void visit(TmfEdge edge
, boolean horizontal
) {
347 * The following graph will be used
350 * ____0___1___2___3___4___5___6___7___8___9___10___11___12___13___14___15
352 * A *-------* *---*-------*---*---* *---*----*----*---------*
354 * B *---*---*-------* *-------*------------* *----------*
357 @SuppressWarnings("null")
358 private static @NonNull TmfGraph
buildFullGraph() {
359 TmfGraph graph
= new TmfGraph();
362 long[] timesA
= { 0, 2, 4, 5, 7, 8, 9, 10, 11, 12, 13, 15 };
363 long[] timesB
= { 1, 2, 3, 5, 6, 8, 11, 12, 14 };
364 vertexA
= new TmfVertex
[timesA
.length
];
365 vertexB
= new TmfVertex
[timesB
.length
];
366 for (int i
= 0; i
< timesA
.length
; i
++) {
367 vertexA
[i
] = new TmfVertex(timesA
[i
]);
369 for (int i
= 0; i
< timesB
.length
; i
++) {
370 vertexB
[i
] = new TmfVertex(timesB
[i
]);
372 graph
.append(WORKER1
, vertexA
[0]);
373 graph
.append(WORKER1
, vertexA
[1]);
374 graph
.add(WORKER1
, vertexA
[2]);
375 graph
.append(WORKER1
, vertexA
[3]);
376 graph
.append(WORKER1
, vertexA
[4]);
377 graph
.append(WORKER1
, vertexA
[5]);
378 graph
.append(WORKER1
, vertexA
[6]);
379 graph
.add(WORKER1
, vertexA
[7]);
380 graph
.append(WORKER1
, vertexA
[8]);
381 graph
.append(WORKER1
, vertexA
[9]);
382 graph
.append(WORKER1
, vertexA
[10]);
383 graph
.append(WORKER1
, vertexA
[11]);
384 graph
.append(WORKER2
, vertexB
[0]);
385 graph
.append(WORKER2
, vertexB
[1]);
386 graph
.append(WORKER2
, vertexB
[2]);
387 graph
.append(WORKER2
, vertexB
[3]);
388 graph
.add(WORKER2
, vertexB
[4]);
389 graph
.append(WORKER2
, vertexB
[5]);
390 graph
.append(WORKER2
, vertexB
[6]);
391 graph
.add(WORKER2
, vertexB
[7]);
392 graph
.append(WORKER2
, vertexB
[8]);
393 vertexA
[1].linkVertical(vertexB
[1]);
394 vertexB
[3].linkVertical(vertexA
[3]);
395 vertexA
[5].linkVertical(vertexB
[5]);
396 vertexB
[6].linkVertical(vertexA
[8]);
397 vertexA
[9].linkVertical(vertexB
[7]);
402 * Test the {@link TmfGraph#scanLineTraverse(IGraphWorker, ITmfGraphVisitor)} method
405 public void testScanCount() {
406 TmfGraph graph
= buildFullGraph();
407 ScanCountVertex visitor
= new ScanCountVertex();
408 graph
.scanLineTraverse(graph
.getHead(WORKER1
), visitor
);
409 assertEquals(21, visitor
.nbVertex
);
410 assertEquals(6, visitor
.nbStartVertex
);
411 assertEquals(5, visitor
.nbVLink
);
412 assertEquals(15, visitor
.nbHLink
);
416 * Test the {@link TmfGraphStatistics} class
419 public void testGraphStatistics() {
420 TmfGraph graph
= buildFullGraph();
421 TmfGraphStatistics stats
= new TmfGraphStatistics();
422 stats
.computeGraphStatistics(graph
, WORKER1
);
423 assertEquals(12, stats
.getSum(WORKER1
).longValue());
424 assertEquals(11, stats
.getSum(WORKER2
).longValue());
425 assertEquals(23, stats
.getSum().longValue());
429 * This visitor throws an exception if it visits twice the same vertex
431 * @author Francis Giraldeau
434 private class DuplicateDetectorVisitor
implements ITmfGraphVisitor
{
435 private final Set
<TmfVertex
> set
= new HashSet
<>();
437 public void visitHead(TmfVertex vertex
) {
440 public void visit(TmfEdge edge
, boolean horizontal
) {
443 public void visit(TmfVertex vertex
) {
444 if (set
.contains(vertex
)) {
445 throw new RuntimeException("node already visited");
452 * Test that exception is thrown if a node is linked horizontally to itself
454 @Test(expected
= IllegalArgumentException
.class)
455 public void testHorizontalSelfLink() {
456 TmfVertex n0
= new TmfVertex(0);
457 n0
.linkHorizontal(n0
);
461 * Test that exception is thrown if a node is linked vertically to itself.
463 @Test(expected
= IllegalArgumentException
.class)
464 public void testVerticalSelfLink() {
465 TmfVertex n0
= new TmfVertex(0);
470 * Test that the visitor detect a cycle in horizontal links. A cycle may
471 * exists only between vertices with equal timetstamps.
473 @Test(expected
= CycleDetectedException
.class)
474 public void testHorizontalCycle() {
475 TmfVertex n0
= new TmfVertex(0);
476 TmfVertex n1
= new TmfVertex(0);
477 n0
.linkHorizontal(n1
);
478 n1
.linkHorizontal(n0
);
479 TmfGraph graph
= new TmfGraph();
480 graph
.add(WORKER1
, n0
);
481 graph
.add(WORKER1
, n1
);
482 graph
.scanLineTraverse(n0
, new DuplicateDetectorVisitor());
486 * Test that scanLineTraverse terminates with the following graph:
499 public void testScanLineTerminates() {
500 TmfVertex n10
= new TmfVertex(0);
501 TmfVertex n20
= new TmfVertex(0);
502 TmfVertex n21
= new TmfVertex(1);
503 TmfVertex n30
= new TmfVertex(1);
504 TmfGraph graph
= new TmfGraph();
505 n10
.linkVertical(n20
);
506 n20
.linkHorizontal(n21
);
507 n21
.linkVertical(n30
);
508 graph
.add(WORKER1
, n10
);
509 graph
.add(WORKER2
, n20
);
510 graph
.add(WORKER2
, n21
);
511 graph
.add(WORKER3
, n30
);
512 graph
.scanLineTraverse(n20
, new DuplicateDetectorVisitor());
This page took 0.042933 seconds and 6 git commands to generate.