TestDagUtils.java

package mvd.jester.model;

import static org.junit.jupiter.api.Assertions.assertTrue;
import java.util.concurrent.ThreadLocalRandom;
import org.jgrapht.Graphs;
import org.jgrapht.experimental.dag.DirectedAcyclicGraph;
import org.jgrapht.graph.DefaultEdge;
import org.junit.jupiter.api.DisplayName;
import org.junit.jupiter.api.Test;
import mvd.jester.utils.DagUtils;
import mvd.jester.model.SystemManager.DagTaskBuilder;
import mvd.jester.utils.BinaryDecompositionTree;

public class TestDagUtils {

    @Test
    @DisplayName("Test if dynamic segments are constructed correctly.")
    public void checkPathLength() {
        DirectedAcyclicGraph<Job, DefaultEdge> jobDag = createJobDag();
        long criticalPath = DagUtils.calculateCriticalPath(jobDag);

        for (Job j : jobDag) {
            assertTrue(j.getRelativeCompletionTime() <= criticalPath);
        }
        for (DefaultEdge e : jobDag.edgeSet()) {
            Job source = jobDag.getEdgeSource(e);
            Job target = jobDag.getEdgeTarget(e);
            assertTrue(source.getRelativeCompletionTime() < target.getRelativeCompletionTime());
        }

        assertTrue(criticalPath == 155);
    }


    @Test
    @DisplayName("Check if NFJ DAGs are created correctly.")
    void checkNfjDagCreation() {
        for (int i = 0; i < 100; ++i) {
            DagTaskBuilder b = new DagTaskBuilder();
            DagTask t = b.generateTask();

            DirectedAcyclicGraph<Job, DefaultEdge> nfjDag = DagUtils.createNFJGraph(t.getJobDag());

            assertTrue(DagUtils.checkNFJProperty(nfjDag));
        }

    }

    @Test
    @DisplayName("Check if Decomposition Tree is created correctly for NFJ Dag.")
    void checkDecompositionTreeCreation() {
        for (int i = 0; i < 100; ++i) {
            long numberOfProcessors = ThreadLocalRandom.current().nextLong(4, 16);
            DagTaskBuilder b = new DagTaskBuilder().setNumberOfProcessors(numberOfProcessors);
            DagTask t = b.generateTask();
            DirectedAcyclicGraph<Job, DefaultEdge> jobDag = t.getJobDag();
            DirectedAcyclicGraph<Job, DefaultEdge> nfjJobDag = DagUtils.createNFJGraph(jobDag);

            BinaryDecompositionTree<Job> tree = DagUtils.createDecompositionTree(nfjJobDag);
            DirectedAcyclicGraph<Job, DefaultEdge> jobDagFromTree =
                    DagUtils.createNFJfromDecompositionTree(tree);

            assertTrue(jobDag.vertexSet().size() == nfjJobDag.vertexSet().size());
            assertTrue(jobDag.vertexSet().size() == jobDagFromTree.vertexSet().size());
            assertTrue(jobDagFromTree.edgeSet().size() == nfjJobDag.edgeSet().size());

            for (DefaultEdge e : nfjJobDag.edgeSet()) {
                Job target = nfjJobDag.getEdgeTarget(e);
                Job source = nfjJobDag.getEdgeSource(e);

                assertTrue(jobDagFromTree.containsEdge(source, target));
            }

            for (Job j : nfjJobDag) {
                for (Job n : nfjJobDag) {
                    if (n == j) {
                        continue;
                    }
                    if (nfjJobDag.containsEdge(n, j)) {
                        assertTrue(jobDagFromTree.containsEdge(n, j));
                    }
                }
                assertTrue(nfjJobDag.inDegreeOf(j) == jobDagFromTree.inDegreeOf(j));
                assertTrue(nfjJobDag.outDegreeOf(j) == jobDagFromTree.outDegreeOf(j));

                for (Job p : Graphs.predecessorListOf(nfjJobDag, j)) {
                    assertTrue(Graphs.predecessorListOf(jobDagFromTree, j).contains(p));
                }

                for (Job s : Graphs.successorListOf(nfjJobDag, j)) {
                    assertTrue(Graphs.successorListOf(jobDagFromTree, j).contains(s));
                }

                for (Job a : nfjJobDag.getAncestors(nfjJobDag, j)) {
                    assertTrue(jobDagFromTree.getAncestors(jobDagFromTree, j).contains(a));
                }

                for (Job d : nfjJobDag.getDescendants(nfjJobDag, j)) {
                    assertTrue(jobDagFromTree.getDescendants(jobDagFromTree, j).contains(d));
                }
            }

        }

    }


    private DirectedAcyclicGraph<Job, DefaultEdge> createJobDag() {
        DirectedAcyclicGraph<Job, DefaultEdge> jobDag =
                new DirectedAcyclicGraph<>(DefaultEdge.class);

        Job source = new Job(20);
        Job pathA = new Job(10);
        Job pathB = new Job(30);
        Job pathC = new Job(40);

        Job child1OfA = new Job(5);
        Job child2OfA = new Job(15);
        Job child3OfA = new Job(5);

        Job childsOfAJoin = new Job(10);

        Job child1OfC = new Job(5);
        Job child2OfC = new Job(10);
        Job child3OfC = new Job(15);
        Job child4OfC = new Job(20);

        Job firstJoin = new Job(20);

        Job intermediateFork = new Job(10);

        Job forkChild1 = new Job(5);
        Job forkChild2 = new Job(10);
        Job forkChild3 = new Job(15);

        Job sink = new Job(30);
        try {
            jobDag.addVertex(source);
            jobDag.addVertex(pathA);
            jobDag.addVertex(pathB);
            jobDag.addVertex(pathC);
            jobDag.addVertex(child1OfA);
            jobDag.addVertex(child2OfA);
            jobDag.addVertex(child3OfA);
            jobDag.addVertex(childsOfAJoin);
            jobDag.addVertex(child1OfC);
            jobDag.addVertex(child2OfC);
            jobDag.addVertex(child3OfC);
            jobDag.addVertex(child4OfC);
            jobDag.addVertex(firstJoin);
            jobDag.addVertex(intermediateFork);
            jobDag.addVertex(forkChild1);
            jobDag.addVertex(forkChild2);
            jobDag.addVertex(forkChild3);
            jobDag.addVertex(sink);
            jobDag.addDagEdge(source, pathA);
            jobDag.addDagEdge(pathA, child1OfA);
            jobDag.addDagEdge(pathA, child2OfA);
            jobDag.addDagEdge(pathA, child3OfA);
            jobDag.addDagEdge(child1OfA, childsOfAJoin);
            jobDag.addDagEdge(child2OfA, childsOfAJoin);
            jobDag.addDagEdge(child3OfA, childsOfAJoin);
            jobDag.addDagEdge(childsOfAJoin, firstJoin);
            jobDag.addDagEdge(source, pathB);
            jobDag.addDagEdge(pathB, firstJoin);
            jobDag.addDagEdge(source, pathC);
            jobDag.addDagEdge(pathC, child1OfC);
            jobDag.addDagEdge(pathC, child2OfC);
            jobDag.addDagEdge(pathC, child3OfC);
            jobDag.addDagEdge(pathC, child4OfC);
            jobDag.addDagEdge(child1OfC, firstJoin);
            jobDag.addDagEdge(child2OfC, firstJoin);
            jobDag.addDagEdge(child3OfC, firstJoin);
            jobDag.addDagEdge(child4OfC, firstJoin);
            jobDag.addDagEdge(firstJoin, intermediateFork);
            jobDag.addDagEdge(intermediateFork, forkChild1);
            jobDag.addDagEdge(intermediateFork, forkChild2);
            jobDag.addDagEdge(intermediateFork, forkChild3);
            jobDag.addDagEdge(forkChild1, sink);
            jobDag.addDagEdge(forkChild2, sink);
            jobDag.addDagEdge(forkChild3, sink);
        } catch (Exception e) {
        }
        return jobDag;
    }
}