[deliverable/tracecompass.git] / analysis / org.eclipse.tracecompass.analysis.graph.core.tests / src / org / eclipse / tracecompass / analysis / graph / core / tests / graph / TmfGraphTest.java

/*******************************************************************************
 * Copyright (c) 2015 École Polytechnique de Montréal
 *
 * All rights reserved. This program and the accompanying materials are
 * made available under the terms of the Eclipse Public License v1.0 which
 * accompanies this distribution, and is available at
 * http://www.eclipse.org/legal/epl-v10.html
 *
 * Contributors:
 *   Francis Giraldeau - Initial API and implementation
 *   Geneviève Bastien - Initial API and implementation
 *******************************************************************************/

package org.eclipse.tracecompass.analysis.graph.core.tests.graph;

import static org.junit.Assert.assertEquals;
import static org.junit.Assert.assertNotNull;
import static org.junit.Assert.assertNotSame;
import static org.junit.Assert.assertNull;

import java.util.HashSet;
import java.util.List;
import java.util.Set;

import org.eclipse.jdt.annotation.NonNull;
import org.eclipse.tracecompass.analysis.graph.core.base.CycleDetectedException;
import org.eclipse.tracecompass.analysis.graph.core.base.IGraphWorker;
import org.eclipse.tracecompass.analysis.graph.core.base.ITmfGraphVisitor;
import org.eclipse.tracecompass.analysis.graph.core.base.TmfEdge;
import org.eclipse.tracecompass.analysis.graph.core.base.TmfEdge.EdgeType;
import org.eclipse.tracecompass.analysis.graph.core.base.TmfGraph;
import org.eclipse.tracecompass.analysis.graph.core.base.TmfVertex;
import org.eclipse.tracecompass.analysis.graph.core.base.TmfVertex.EdgeDirection;
import org.eclipse.tracecompass.analysis.graph.core.tests.stubs.TestGraphWorker;
import org.eclipse.tracecompass.internal.analysis.graph.core.base.TmfGraphStatistics;
import org.eclipse.tracecompass.tmf.core.timestamp.ITmfTimestamp;
import org.eclipse.tracecompass.tmf.core.timestamp.TmfTimestamp;
import org.junit.Test;

/**
 * Test the basic functionalities of the {@link TmfGraph}, {@link TmfVertex} and
 * {@link TmfEdge} classes.
 *
 * @author Geneviève Bastien
 * @author Francis Giraldeau
 */
public class TmfGraphTest {

    private static final @NonNull IGraphWorker WORKER1 = new TestGraphWorker(1);
    private static final @NonNull IGraphWorker WORKER2 = new TestGraphWorker(2);
    private static final @NonNull IGraphWorker WORKER3 = new TestGraphWorker(3);

    private final @NonNull TmfGraph fGraph = new TmfGraph();
    private final @NonNull TmfVertex fV0 = new TmfVertex(0);
    private final @NonNull TmfVertex fV1 = new TmfVertex(1);

    /**
     * Test the graph constructor
     */
    @Test
    public void testDefaultConstructor() {
        TmfGraph g = new TmfGraph();
        assertEquals(0, g.size());
    }

    /**
     * Test the {@link TmfGraph#add(IGraphWorker, TmfVertex)} method: vertices are
     * added, but no edge between them is created
     */
    @Test
    public void testAddVertex() {
        fGraph.add(WORKER1, fV0);
        fGraph.add(WORKER1, fV1);
        List<TmfVertex> list = fGraph.getNodesOf(WORKER1);
        assertEquals(2, list.size());
        for (int i = 0; i < list.size() - 1; i++) {
            TmfVertex vertex = list.get(i);
            assertEquals(i, vertex.getTs());
            assertNull(vertex.getEdge(EdgeDirection.OUTGOING_HORIZONTAL_EDGE));
            assertNull(vertex.getEdge(EdgeDirection.INCOMING_HORIZONTAL_EDGE));
            assertNull(vertex.getEdge(EdgeDirection.OUTGOING_VERTICAL_EDGE));
            assertNull(vertex.getEdge(EdgeDirection.INCOMING_VERTICAL_EDGE));
        }
    }

    /**
     * Test the {@link TmfGraph#append(IGraphWorker, TmfVertex)} and
     * {@link TmfGraph#append(IGraphWorker, TmfVertex, EdgeType)} methods: vertices
     * are added and links are created between them.
     */
    @Test
    public void testAppendVertex() {
        /* Append without type */
        fGraph.append(WORKER1, fV0);
        TmfEdge edge = fGraph.append(WORKER1, fV1);
        assertNotNull(edge);
        assertEquals(EdgeType.DEFAULT, edge.getType());
        assertEquals(fV1, edge.getVertexTo());
        assertEquals(fV0, edge.getVertexFrom());
        assertEquals(fV1.getTs() - fV0.getTs(), edge.getDuration());

        List<TmfVertex> list = fGraph.getNodesOf(WORKER1);
        assertEquals(2, list.size());
        checkLinkHorizontal(list);
        assertEquals(fV0, fGraph.getHead(WORKER1));
        assertEquals(fV1, fGraph.getTail(WORKER1));

        /* Append with a type */
        TmfVertex v2 = new TmfVertex(2);
        edge = fGraph.append(WORKER1, v2, EdgeType.BLOCKED);
        assertNotNull(edge);
        assertEquals(EdgeType.BLOCKED, edge.getType());
        assertEquals(v2, edge.getVertexTo());
        assertEquals(fV1, edge.getVertexFrom());
        assertEquals(v2.getTs() - fV1.getTs(), edge.getDuration());

        list = fGraph.getNodesOf(WORKER1);
        assertEquals(3, list.size());
        checkLinkHorizontal(list);
        assertEquals(fV0, fGraph.getHead(WORKER1));
        assertEquals(v2, fGraph.getTail(WORKER1));
    }

    /**
     * Test that appending vertices in non chronological order gives error
     */
    @Test(expected = IllegalArgumentException.class)
    public void testIllegalVertex() {
        fGraph.append(WORKER1, fV1);
        fGraph.append(WORKER1, fV0);
    }

    /**
     * Test the {@link TmfGraph#link(TmfVertex, TmfVertex)} and
     * {@link TmfGraph#link(TmfVertex, TmfVertex, EdgeType)} methods
     */
    @Test
    public void testLink() {
        // Start with a first node
        fGraph.add(WORKER1, fV0);

        // Link with second node not in graph
        TmfEdge edge = fGraph.link(fV0, fV1);
        assertEquals(fV1, edge.getVertexTo());
        assertEquals(fV0, edge.getVertexFrom());
        assertEquals(EdgeType.DEFAULT, edge.getType());
        assertEquals(fV1.getTs() - fV0.getTs(), edge.getDuration());

        List<TmfVertex> list = fGraph.getNodesOf(WORKER1);
        assertEquals(2, list.size());
        edge = fV1.getEdge(EdgeDirection.INCOMING_HORIZONTAL_EDGE);
        assertNotNull(edge);
        assertEquals(fV0, edge.getVertexFrom());
        edge = fV0.getEdge(EdgeDirection.OUTGOING_HORIZONTAL_EDGE);
        assertNotNull(edge);
        assertEquals(fV1, edge.getVertexTo());

        // Link with second node for the same object
        TmfVertex v2 = new TmfVertex(2);
        fGraph.add(WORKER1, v2);
        edge = fGraph.link(fV1, v2, EdgeType.NETWORK);
        assertEquals(v2, edge.getVertexTo());
        assertEquals(fV1, edge.getVertexFrom());
        assertEquals(EdgeType.NETWORK, edge.getType());

        list = fGraph.getNodesOf(WORKER1);
        assertEquals(3, list.size());
        edge = fV1.getEdge(EdgeDirection.OUTGOING_HORIZONTAL_EDGE);
        assertNotNull(edge);
        assertEquals(v2, edge.getVertexTo());
        edge = v2.getEdge(EdgeDirection.INCOMING_HORIZONTAL_EDGE);
        assertNotNull(edge);
        assertEquals(fV1, edge.getVertexFrom());

        // Link with second node for another object
        TmfVertex v3 = new TmfVertex(3);
        fGraph.add(WORKER2, v3);
        edge = fGraph.link(v2, v3, EdgeType.NETWORK);
        assertEquals(v3, edge.getVertexTo());
        assertEquals(v2, edge.getVertexFrom());
        assertEquals(EdgeType.NETWORK, edge.getType());

        list = fGraph.getNodesOf(WORKER2);
        assertEquals(1, list.size());

        list = fGraph.getNodesOf(WORKER1);
        assertEquals(3, list.size());
        edge = v3.getEdge(EdgeDirection.INCOMING_VERTICAL_EDGE);
        assertNotNull(edge);
        assertEquals(v2, edge.getVertexFrom());
        edge = v2.getEdge(EdgeDirection.OUTGOING_VERTICAL_EDGE);
        assertNotNull(edge);
        assertEquals(v3, edge.getVertexTo());

    }

    /**
     * Verify that vertices in the list form a chain linked by edges and have no
     * vertical edges
     */
    private static void checkLinkHorizontal(List<TmfVertex> list) {
        if (list.isEmpty()) {
            return;
        }
        for (int i = 0; i < list.size() - 1; i++) {
            TmfVertex v0 = list.get(i);
            TmfVertex v1 = list.get(i + 1);
            TmfEdge edge = v0.getEdge(EdgeDirection.OUTGOING_HORIZONTAL_EDGE);
            assertNotNull(edge);
            assertEquals(v0, edge.getVertexFrom());
            assertEquals(v1, edge.getVertexTo());
            edge = v1.getEdge(EdgeDirection.INCOMING_HORIZONTAL_EDGE);
            assertNotNull(edge);
            assertEquals(v0, edge.getVertexFrom());
            assertEquals(v1, edge.getVertexTo());
            assertNull(v1.getEdge(EdgeDirection.OUTGOING_VERTICAL_EDGE));
            assertNull(v1.getEdge(EdgeDirection.INCOMING_VERTICAL_EDGE));
            assertNull(v0.getEdge(EdgeDirection.OUTGOING_VERTICAL_EDGE));
            assertNull(v0.getEdge(EdgeDirection.INCOMING_VERTICAL_EDGE));
        }
    }

    /**
     * Test the {@link TmfGraph#getTail(IGraphWorker)} and
     * {@link TmfGraph#removeTail(IGraphWorker)} methods
     */
    @Test
    public void testTail() {
        fGraph.append(WORKER1, fV0);
        fGraph.append(WORKER1, fV1);
        assertEquals(fV1, fGraph.getTail(WORKER1));
        assertEquals(fV1, fGraph.removeTail(WORKER1));
        assertEquals(fV0, fGraph.getTail(WORKER1));
    }

    /**
     * Test the {@link TmfGraph#getHead()} methods
     */
    @Test
    public void testHead() {
        assertNull(fGraph.getHead());
        fGraph.append(WORKER1, fV0);
        fGraph.append(WORKER1, fV1);
        assertEquals(fV0, fGraph.getHead());
        assertEquals(fV0, fGraph.getHead(WORKER1));
        assertEquals(fV0, fGraph.getHead(fV1));
        assertEquals(fV0, fGraph.getHead(fV0));
    }

    /**
     * Test the {@link TmfGraph#getHead()} methods with 2 workers
     */
    @Test
    public void testHead2() {
        fGraph.append(WORKER1, fV1);
        fGraph.append(WORKER2, fV0);
        assertEquals(fV0, fGraph.getHead());
        assertEquals(fV1, fGraph.getHead(WORKER1));
        assertEquals(fV0, fGraph.getHead(WORKER2));
        assertEquals(fV1, fGraph.getHead(fV1));
        assertEquals(fV0, fGraph.getHead(fV0));
    }

    /**
     * The test {@link TmfGraph#getParentOf(TmfVertex)} method
     */
    @Test
    public void testParent() {
        fGraph.append(WORKER1, fV0);
        fGraph.append(WORKER2, fV1);
        assertEquals(WORKER1, fGraph.getParentOf(fV0));
        assertNotSame(WORKER1, fGraph.getParentOf(fV1));
        assertEquals(WORKER2, fGraph.getParentOf(fV1));
    }

    /**
     * Test the {@link TmfGraph#getVertexAt(ITmfTimestamp, IGraphWorker)} method
     */
    @Test
    public void testVertexAt() {
        TmfVertex[] vertices = new TmfVertex[5];
        for (int i = 0; i < 5; i++) {
            TmfVertex v = new TmfVertex((i + 1) * 5);
            vertices[i] = v;
            fGraph.append(WORKER1, v);
        }
        assertEquals(vertices[0], fGraph.getVertexAt(TmfTimestamp.fromSeconds(5), WORKER1));
        assertEquals(vertices[0], fGraph.getVertexAt(TmfTimestamp.fromSeconds(0), WORKER1));
        assertEquals(vertices[1], fGraph.getVertexAt(TmfTimestamp.fromSeconds(6), WORKER1));
        assertEquals(vertices[3], fGraph.getVertexAt(TmfTimestamp.fromSeconds(19), WORKER1));
        assertNull(fGraph.getVertexAt(TmfTimestamp.fromSeconds(19), WORKER2));
        assertEquals(vertices[3], fGraph.getVertexAt(TmfTimestamp.fromSeconds(20), WORKER1));
        assertEquals(vertices[4], fGraph.getVertexAt(TmfTimestamp.fromSeconds(21), WORKER1));
        assertNull(fGraph.getVertexAt(TmfTimestamp.fromSeconds(26), WORKER1));
    }

    /**
     * Test the {@link TmfVertex#linkHorizontal(TmfVertex)} with non
     * chronological timestamps
     */
    @Test(expected = IllegalArgumentException.class)
    public void testCheckHorizontal() {
        TmfVertex n0 = new TmfVertex(10);
        TmfVertex n1 = new TmfVertex(0);
        n0.linkHorizontal(n1);
    }

    /**
     * Test the {@link TmfVertex#linkVertical(TmfVertex)} with non chronological
     * timestamps
     */
    @Test(expected = IllegalArgumentException.class)
    public void testCheckVertical() {
        TmfVertex n0 = new TmfVertex(10);
        TmfVertex n1 = new TmfVertex(0);
        n0.linkVertical(n1);
    }

    private class ScanCountVertex implements ITmfGraphVisitor {
        public int nbVertex = 0;
        public int nbVLink = 0;
        public int nbHLink = 0;
        public int nbStartVertex = 0;

        @Override
        public void visitHead(TmfVertex node) {
            nbStartVertex++;
        }

        @Override
        public void visit(TmfVertex node) {
            nbVertex++;

        }

        @Override
        public void visit(TmfEdge edge, boolean horizontal) {
            if (horizontal) {
                nbHLink++;
            } else {
                nbVLink++;
            }
        }
    }

    /**
     * The following graph will be used
     *
     * <pre>
     * ____0___1___2___3___4___5___6___7___8___9___10___11___12___13___14___15
     *
     * A   *-------*       *---*-------*---*---*    *---*----*----*---------*
     *             |           |           |            |    |
     * B       *---*---*-------*   *-------*------------*    *----------*
     * </pre>
     */
    @SuppressWarnings("null")
    private static @NonNull TmfGraph buildFullGraph() {
        TmfGraph graph = new TmfGraph();
        TmfVertex[] vertexA;
        TmfVertex[] vertexB;
        long[] timesA = { 0, 2, 4, 5, 7, 8, 9, 10, 11, 12, 13, 15 };
        long[] timesB = { 1, 2, 3, 5, 6, 8, 11, 12, 14 };
        vertexA = new TmfVertex[timesA.length];
        vertexB = new TmfVertex[timesB.length];
        for (int i = 0; i < timesA.length; i++) {
            vertexA[i] = new TmfVertex(timesA[i]);
        }
        for (int i = 0; i < timesB.length; i++) {
            vertexB[i] = new TmfVertex(timesB[i]);
        }
        graph.append(WORKER1, vertexA[0]);
        graph.append(WORKER1, vertexA[1]);
        graph.add(WORKER1, vertexA[2]);
        graph.append(WORKER1, vertexA[3]);
        graph.append(WORKER1, vertexA[4]);
        graph.append(WORKER1, vertexA[5]);
        graph.append(WORKER1, vertexA[6]);
        graph.add(WORKER1, vertexA[7]);
        graph.append(WORKER1, vertexA[8]);
        graph.append(WORKER1, vertexA[9]);
        graph.append(WORKER1, vertexA[10]);
        graph.append(WORKER1, vertexA[11]);
        graph.append(WORKER2, vertexB[0]);
        graph.append(WORKER2, vertexB[1]);
        graph.append(WORKER2, vertexB[2]);
        graph.append(WORKER2, vertexB[3]);
        graph.add(WORKER2, vertexB[4]);
        graph.append(WORKER2, vertexB[5]);
        graph.append(WORKER2, vertexB[6]);
        graph.add(WORKER2, vertexB[7]);
        graph.append(WORKER2, vertexB[8]);
        vertexA[1].linkVertical(vertexB[1]);
        vertexB[3].linkVertical(vertexA[3]);
        vertexA[5].linkVertical(vertexB[5]);
        vertexB[6].linkVertical(vertexA[8]);
        vertexA[9].linkVertical(vertexB[7]);
        return graph;
    }

    /**
     * Test the {@link TmfGraph#scanLineTraverse(IGraphWorker, ITmfGraphVisitor)} method
     */
    @Test
    public void testScanCount() {
        TmfGraph graph = buildFullGraph();
        ScanCountVertex visitor = new ScanCountVertex();
        graph.scanLineTraverse(graph.getHead(WORKER1), visitor);
        assertEquals(21, visitor.nbVertex);
        assertEquals(6, visitor.nbStartVertex);
        assertEquals(5, visitor.nbVLink);
        assertEquals(15, visitor.nbHLink);
    }

    /**
     * Test the {@link TmfGraphStatistics} class
     */
    @Test
    public void testGraphStatistics() {
        TmfGraph graph = buildFullGraph();
        TmfGraphStatistics stats = new TmfGraphStatistics();
        stats.computeGraphStatistics(graph, WORKER1);
        assertEquals(12, stats.getSum(WORKER1).longValue());
        assertEquals(11, stats.getSum(WORKER2).longValue());
        assertEquals(23, stats.getSum().longValue());
    }

    /**
     * This visitor throws an exception if it visits twice the same vertex
     *
     * @author Francis Giraldeau
     *
     */
    private class DuplicateDetectorVisitor implements ITmfGraphVisitor {
        private final Set<TmfVertex> set = new HashSet<>();
        @Override
        public void visitHead(TmfVertex vertex) {
        }
        @Override
        public void visit(TmfEdge edge, boolean horizontal) {
        }
        @Override
        public void visit(TmfVertex vertex) {
            if (set.contains(vertex)) {
                throw new RuntimeException("node already visited");
            }
            set.add(vertex);
        }
    }

    /**
     * Test that exception is thrown if a node is linked horizontally to itself
     */
    @Test(expected = IllegalArgumentException.class)
    public void testHorizontalSelfLink() {
        TmfVertex n0 = new TmfVertex(0);
        n0.linkHorizontal(n0);
    }

    /**
     * Test that exception is thrown if a node is linked vertically to itself.
     */
    @Test(expected = IllegalArgumentException.class)
    public void testVerticalSelfLink() {
        TmfVertex n0 = new TmfVertex(0);
        n0.linkVertical(n0);
    }

    /**
     * Test that the visitor detect a cycle in horizontal links. A cycle may
     * exists only between vertices with equal timetstamps.
     */
    @Test(expected = CycleDetectedException.class)
    public void testHorizontalCycle() {
        TmfVertex n0 = new TmfVertex(0);
        TmfVertex n1 = new TmfVertex(0);
        n0.linkHorizontal(n1);
        n1.linkHorizontal(n0);
        TmfGraph graph = new TmfGraph();
        graph.add(WORKER1, n0);
        graph.add(WORKER1, n1);
        graph.scanLineTraverse(n0, new DuplicateDetectorVisitor());
    }

    /**
     * Test that scanLineTraverse terminates with the following graph:
     *
     * <pre>
     *          ^
     *          |
     *    +----->
     *    ^
     *    |
     *    +
     *
     * </pre>
     */
    @Test
    public void testScanLineTerminates() {
        TmfVertex n10 = new TmfVertex(0);
        TmfVertex n20 = new TmfVertex(0);
        TmfVertex n21 = new TmfVertex(1);
        TmfVertex n30 = new TmfVertex(1);
        TmfGraph graph = new TmfGraph();
        n10.linkVertical(n20);
        n20.linkHorizontal(n21);
        n21.linkVertical(n30);
        graph.add(WORKER1, n10);
        graph.add(WORKER2, n20);
        graph.add(WORKER2, n21);
        graph.add(WORKER3, n30);
        graph.scanLineTraverse(n20, new DuplicateDetectorVisitor());
    }

}
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
732e0744	21	import java.util.HashSet;
1b46d94d	22	import java.util.List;
732e0744	23	import java.util.Set;
1b46d94d FG	24
1b46d94d FG	25	import org.eclipse.jdt.annotation.NonNull;
732e0744	26	import org.eclipse.tracecompass.analysis.graph.core.base.CycleDetectedException;
1b46d94d FG	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;
	39
	40	/**
	41	* Test the basic functionalities of the {@link TmfGraph}, {@link TmfVertex} and
	42	* {@link TmfEdge} classes.
	43	*
	44	* @author Geneviève Bastien
	45	* @author Francis Giraldeau
	46	*/
	47	public class TmfGraphTest {
	48
	49	private static final @NonNull IGraphWorker WORKER1 = new TestGraphWorker(1);
	50	private static final @NonNull IGraphWorker WORKER2 = new TestGraphWorker(2);
732e0744	51	private static final @NonNull IGraphWorker WORKER3 = new TestGraphWorker(3);
1b46d94d FG	52
	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);
	56
	57	/**
	58	* Test the graph constructor
	59	*/
	60	@Test
	61	public void testDefaultConstructor() {
	62	TmfGraph g = new TmfGraph();
	63	assertEquals(0, g.size());
	64	}
	65
	66	/**
	67	* Test the {@link TmfGraph#add(IGraphWorker, TmfVertex)} method: vertices are
	68	* added, but no edge between them is created
	69	*/
	70	@Test
	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));
	83	}
	84	}
	85
	86	/**
	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.
	90	*/
	91	@Test
	92	public void testAppendVertex() {
	93	/* Append without type */
	94	fGraph.append(WORKER1, fV0);
	95	TmfEdge edge = fGraph.append(WORKER1, fV1);
	96	assertNotNull(edge);
	97	assertEquals(EdgeType.DEFAULT, edge.getType());
	98	assertEquals(fV1, edge.getVertexTo());
	99	assertEquals(fV0, edge.getVertexFrom());
	100	assertEquals(fV1.getTs() - fV0.getTs(), edge.getDuration());
	101
	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));
	107
	108	/* Append with a type */
	109	TmfVertex v2 = new TmfVertex(2);
	110	edge = fGraph.append(WORKER1, v2, EdgeType.BLOCKED);
	111	assertNotNull(edge);
	112	assertEquals(EdgeType.BLOCKED, edge.getType());
	113	assertEquals(v2, edge.getVertexTo());
	114	assertEquals(fV1, edge.getVertexFrom());
	115	assertEquals(v2.getTs() - fV1.getTs(), edge.getDuration());
116
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));
122	}
123
124	/**
125	* Test that appending vertices in non chronological order gives error
126	*/
127	@Test(expected = IllegalArgumentException.class)
128	public void testIllegalVertex() {
129	fGraph.append(WORKER1, fV1);
130	fGraph.append(WORKER1, fV0);
131	}
132
133	/**
134	* Test the {@link TmfGraph#link(TmfVertex, TmfVertex)} and
135	* {@link TmfGraph#link(TmfVertex, TmfVertex, EdgeType)} methods
136	*/
137	@Test
138	public void testLink() {
139	// Start with a first node
140	fGraph.add(WORKER1, fV0);
141
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());
148
149	List<TmfVertex> list = fGraph.getNodesOf(WORKER1);
150	assertEquals(2, list.size());
151	edge = fV1.getEdge(EdgeDirection.INCOMING_HORIZONTAL_EDGE);
152	assertNotNull(edge);
153	assertEquals(fV0, edge.getVertexFrom());
154	edge = fV0.getEdge(EdgeDirection.OUTGOING_HORIZONTAL_EDGE);
155	assertNotNull(edge);
156	assertEquals(fV1, edge.getVertexTo());
157
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());
165
166	list = fGraph.getNodesOf(WORKER1);
167	assertEquals(3, list.size());
168	edge = fV1.getEdge(EdgeDirection.OUTGOING_HORIZONTAL_EDGE);
169	assertNotNull(edge);
170	assertEquals(v2, edge.getVertexTo());
171	edge = v2.getEdge(EdgeDirection.INCOMING_HORIZONTAL_EDGE);
172	assertNotNull(edge);
173	assertEquals(fV1, edge.getVertexFrom());
174
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());
182
183	list = fGraph.getNodesOf(WORKER2);
184	assertEquals(1, list.size());
185
186	list = fGraph.getNodesOf(WORKER1);
187	assertEquals(3, list.size());
188	edge = v3.getEdge(EdgeDirection.INCOMING_VERTICAL_EDGE);
189	assertNotNull(edge);
190	assertEquals(v2, edge.getVertexFrom());
191	edge = v2.getEdge(EdgeDirection.OUTGOING_VERTICAL_EDGE);
192	assertNotNull(edge);
193	assertEquals(v3, edge.getVertexTo());
194
195	}
196
197	/**
198	* Verify that vertices in the list form a chain linked by edges and have no
199	* vertical edges
200	*/
201	private static void checkLinkHorizontal(List<TmfVertex> list) {
202	if (list.isEmpty()) {
203	return;
204	}
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);
209	assertNotNull(edge);
210	assertEquals(v0, edge.getVertexFrom());
211	assertEquals(v1, edge.getVertexTo());
212	edge = v1.getEdge(EdgeDirection.INCOMING_HORIZONTAL_EDGE);
213	assertNotNull(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));
220	}
221	}
222
223	/**
224	* Test the {@link TmfGraph#getTail(IGraphWorker)} and
225	* {@link TmfGraph#removeTail(IGraphWorker)} methods
226	*/
227	@Test
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));
234	}
235
236	/**
237	* Test the {@link TmfGraph#getHead()} methods
238	*/
239	@Test
240	public void testHead() {
ce81d501	241	assertNull(fGraph.getHead());
1b46d94d FG	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));
	248	}
	249
ce81d501 GB	250	/**
	251	* Test the {@link TmfGraph#getHead()} methods with 2 workers
	252	*/
	253	@Test
	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));
	262	}
	263
1b46d94d FG	264	/**
	265	* The test {@link TmfGraph#getParentOf(TmfVertex)} method
	266	*/
	267	@Test
	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));
	274	}
	275
	276	/**
	277	* Test the {@link TmfGraph#getVertexAt(ITmfTimestamp, IGraphWorker)} method
	278	*/
	279	@Test
	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);
	284	vertices[i] = v;
	285	fGraph.append(WORKER1, v);
	286	}
b2c971ec MK	287	assertEquals(vertices[0], fGraph.getVertexAt(TmfTimestamp.fromSeconds(5), WORKER1));
	288	assertEquals(vertices[0], fGraph.getVertexAt(TmfTimestamp.fromSeconds(0), WORKER1));
	289	assertEquals(vertices[1], fGraph.getVertexAt(TmfTimestamp.fromSeconds(6), WORKER1));
	290	assertEquals(vertices[3], fGraph.getVertexAt(TmfTimestamp.fromSeconds(19), WORKER1));
	291	assertNull(fGraph.getVertexAt(TmfTimestamp.fromSeconds(19), WORKER2));
	292	assertEquals(vertices[3], fGraph.getVertexAt(TmfTimestamp.fromSeconds(20), WORKER1));
	293	assertEquals(vertices[4], fGraph.getVertexAt(TmfTimestamp.fromSeconds(21), WORKER1));
	294	assertNull(fGraph.getVertexAt(TmfTimestamp.fromSeconds(26), WORKER1));
1b46d94d FG	295	}
	296
	297	/**
	298	* Test the {@link TmfVertex#linkHorizontal(TmfVertex)} with non
	299	* chronological timestamps
	300	*/
	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);
	306	}
	307
	308	/**
	309	* Test the {@link TmfVertex#linkVertical(TmfVertex)} with non chronological
	310	* timestamps
	311	*/
	312	@Test(expected = IllegalArgumentException.class)
	313	public void testCheckVertical() {
	314	TmfVertex n0 = new TmfVertex(10);
	315	TmfVertex n1 = new TmfVertex(0);
	316	n0.linkVertical(n1);
	317	}
	318
	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;
	324
	325	@Override
	326	public void visitHead(TmfVertex node) {
	327	nbStartVertex++;
	328	}
	329
	330	@Override
	331	public void visit(TmfVertex node) {
	332	nbVertex++;
	333
	334	}
	335
	336	@Override
	337	public void visit(TmfEdge edge, boolean horizontal) {
	338	if (horizontal) {
	339	nbHLink++;
	340	} else {
	341	nbVLink++;
	342	}
	343	}
	344	}
	345
	346	/**
	347	* The following graph will be used
	348	*
	349	* <pre>
	350	* ____0___1___2___3___4___5___6___7___8___9___10___11___12___13___14___15
	351	*
	352	* A ------- ----------------* --------------------*
	353	* \| \| \| \| \|
	354	* B ------------- -------------------* ----------
	355	* </pre>
	356	*/
	357	@SuppressWarnings("null")
	358	private static @NonNull TmfGraph buildFullGraph() {
359	TmfGraph graph = new TmfGraph();
360	TmfVertex[] vertexA;
361	TmfVertex[] vertexB;
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]);
368	}
369	for (int i = 0; i < timesB.length; i++) {
370	vertexB[i] = new TmfVertex(timesB[i]);
371	}
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]);
398	return graph;
399	}
400
401	/**
402	* Test the {@link TmfGraph#scanLineTraverse(IGraphWorker, ITmfGraphVisitor)} method
403	*/
404	@Test
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);
413	}
414
415	/**
416	* Test the {@link TmfGraphStatistics} class
417	*/
418	@Test
419	public void testGraphStatistics() {
420	TmfGraph graph = buildFullGraph();
421	TmfGraphStatistics stats = new TmfGraphStatistics();
49a4b360	422	stats.computeGraphStatistics(graph, WORKER1);
1b46d94d FG	423	assertEquals(12, stats.getSum(WORKER1).longValue());
	424	assertEquals(11, stats.getSum(WORKER2).longValue());
	425	assertEquals(23, stats.getSum().longValue());
	426	}
	427
732e0744 FG	428	/**
	429	* This visitor throws an exception if it visits twice the same vertex
	430	*
	431	* @author Francis Giraldeau
	432	*
	433	*/
	434	private class DuplicateDetectorVisitor implements ITmfGraphVisitor {
	435	private final Set<TmfVertex> set = new HashSet<>();
	436	@Override
	437	public void visitHead(TmfVertex vertex) {
	438	}
	439	@Override
	440	public void visit(TmfEdge edge, boolean horizontal) {
	441	}
	442	@Override
	443	public void visit(TmfVertex vertex) {
	444	if (set.contains(vertex)) {
	445	throw new RuntimeException("node already visited");
	446	}
	447	set.add(vertex);
	448	}
	449	}
	450
	451	/**
	452	* Test that exception is thrown if a node is linked horizontally to itself
	453	*/
	454	@Test(expected = IllegalArgumentException.class)
	455	public void testHorizontalSelfLink() {
	456	TmfVertex n0 = new TmfVertex(0);
	457	n0.linkHorizontal(n0);
	458	}
	459
	460	/**
	461	* Test that exception is thrown if a node is linked vertically to itself.
	462	*/
	463	@Test(expected = IllegalArgumentException.class)
	464	public void testVerticalSelfLink() {
	465	TmfVertex n0 = new TmfVertex(0);
	466	n0.linkVertical(n0);
	467	}
	468
	469	/**
	470	* Test that the visitor detect a cycle in horizontal links. A cycle may
	471	* exists only between vertices with equal timetstamps.
	472	*/
	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());
	483	}
	484
	485	/**
	486	* Test that scanLineTraverse terminates with the following graph:
	487	*
	488	* <pre>
	489	* ^
	490	* \|
	491	* +----->
492	* ^
493	* \|
494	* +
495	*
496	* </pre>
497	*/
498	@Test
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());
513	}
514
1b46d94d	515	}