f3dae33041cfbed3c0a645add8cbdd5f8eade426
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
.List
;
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
;
38 * Test the basic functionalities of the {@link TmfGraph}, {@link TmfVertex} and
39 * {@link TmfEdge} classes.
41 * @author Geneviève Bastien
42 * @author Francis Giraldeau
44 public class TmfGraphTest
{
46 private static final @NonNull IGraphWorker WORKER1
= new TestGraphWorker(1);
47 private static final @NonNull IGraphWorker WORKER2
= new TestGraphWorker(2);
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);
54 * Test the graph constructor
57 public void testDefaultConstructor() {
58 TmfGraph g
= new TmfGraph();
59 assertEquals(0, g
.size());
63 * Test the {@link TmfGraph#add(IGraphWorker, TmfVertex)} method: vertices are
64 * added, but no edge between them is created
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
));
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.
88 public void testAppendVertex() {
89 /* Append without type */
90 fGraph
.append(WORKER1
, fV0
);
91 TmfEdge edge
= fGraph
.append(WORKER1
, fV1
);
93 assertEquals(EdgeType
.DEFAULT
, edge
.getType());
94 assertEquals(fV1
, edge
.getVertexTo());
95 assertEquals(fV0
, edge
.getVertexFrom());
96 assertEquals(fV1
.getTs() - fV0
.getTs(), edge
.getDuration());
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
));
104 /* Append with a type */
105 TmfVertex v2
= new TmfVertex(2);
106 edge
= fGraph
.append(WORKER1
, v2
, EdgeType
.BLOCKED
);
108 assertEquals(EdgeType
.BLOCKED
, edge
.getType());
109 assertEquals(v2
, edge
.getVertexTo());
110 assertEquals(fV1
, edge
.getVertexFrom());
111 assertEquals(v2
.getTs() - fV1
.getTs(), edge
.getDuration());
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
));
121 * Test that appending vertices in non chronological order gives error
123 @Test(expected
= IllegalArgumentException
.class)
124 public void testIllegalVertex() {
125 fGraph
.append(WORKER1
, fV1
);
126 fGraph
.append(WORKER1
, fV0
);
130 * Test the {@link TmfGraph#link(TmfVertex, TmfVertex)} and
131 * {@link TmfGraph#link(TmfVertex, TmfVertex, EdgeType)} methods
134 public void testLink() {
135 // Start with a first node
136 fGraph
.add(WORKER1
, fV0
);
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());
145 List
<TmfVertex
> list
= fGraph
.getNodesOf(WORKER1
);
146 assertEquals(2, list
.size());
147 edge
= fV1
.getEdge(EdgeDirection
.INCOMING_HORIZONTAL_EDGE
);
149 assertEquals(fV0
, edge
.getVertexFrom());
150 edge
= fV0
.getEdge(EdgeDirection
.OUTGOING_HORIZONTAL_EDGE
);
152 assertEquals(fV1
, edge
.getVertexTo());
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());
162 list
= fGraph
.getNodesOf(WORKER1
);
163 assertEquals(3, list
.size());
164 edge
= fV1
.getEdge(EdgeDirection
.OUTGOING_HORIZONTAL_EDGE
);
166 assertEquals(v2
, edge
.getVertexTo());
167 edge
= v2
.getEdge(EdgeDirection
.INCOMING_HORIZONTAL_EDGE
);
169 assertEquals(fV1
, edge
.getVertexFrom());
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());
179 list
= fGraph
.getNodesOf(WORKER2
);
180 assertEquals(1, list
.size());
182 list
= fGraph
.getNodesOf(WORKER1
);
183 assertEquals(3, list
.size());
184 edge
= v3
.getEdge(EdgeDirection
.INCOMING_VERTICAL_EDGE
);
186 assertEquals(v2
, edge
.getVertexFrom());
187 edge
= v2
.getEdge(EdgeDirection
.OUTGOING_VERTICAL_EDGE
);
189 assertEquals(v3
, edge
.getVertexTo());
194 * Verify that vertices in the list form a chain linked by edges and have no
197 private static void checkLinkHorizontal(List
<TmfVertex
> list
) {
198 if (list
.isEmpty()) {
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
);
206 assertEquals(v0
, edge
.getVertexFrom());
207 assertEquals(v1
, edge
.getVertexTo());
208 edge
= v1
.getEdge(EdgeDirection
.INCOMING_HORIZONTAL_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
));
220 * Test the {@link TmfGraph#getTail(IGraphWorker)} and
221 * {@link TmfGraph#removeTail(IGraphWorker)} methods
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
));
233 * Test the {@link TmfGraph#getHead()} methods
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
));
246 * The test {@link TmfGraph#getParentOf(TmfVertex)} method
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
));
258 * Test the {@link TmfGraph#getVertexAt(ITmfTimestamp, IGraphWorker)} method
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);
266 fGraph
.append(WORKER1
, v
);
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
));
279 * Test the {@link TmfVertex#linkHorizontal(TmfVertex)} with non
280 * chronological timestamps
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
);
290 * Test the {@link TmfVertex#linkVertical(TmfVertex)} with non chronological
293 @Test(expected
= IllegalArgumentException
.class)
294 public void testCheckVertical() {
295 TmfVertex n0
= new TmfVertex(10);
296 TmfVertex n1
= new TmfVertex(0);
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;
307 public void visitHead(TmfVertex node
) {
312 public void visit(TmfVertex node
) {
318 public void visit(TmfEdge edge
, boolean horizontal
) {
328 * The following graph will be used
331 * ____0___1___2___3___4___5___6___7___8___9___10___11___12___13___14___15
333 * A *-------* *---*-------*---*---* *---*----*----*---------*
335 * B *---*---*-------* *-------*------------* *----------*
338 @SuppressWarnings("null")
339 private static @NonNull TmfGraph
buildFullGraph() {
340 TmfGraph graph
= new TmfGraph();
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
]);
350 for (int i
= 0; i
< timesB
.length
; i
++) {
351 vertexB
[i
] = new TmfVertex(timesB
[i
]);
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]);
383 * Test the {@link TmfGraph#scanLineTraverse(IGraphWorker, ITmfGraphVisitor)} method
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
);
397 * Test the {@link TmfGraphStatistics} class
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());
This page took 0.040288 seconds and 4 git commands to generate.