TopologicalSorterTest.java

package org.codehaus.plexus.util.dag;

/*
 * Copyright The Codehaus Foundation.
 *
 * Licensed under the Apache License, Version 2.0 (the "License");
 * you may not use this file except in compliance with the License.
 * You may obtain a copy of the License at
 *
 *     http://www.apache.org/licenses/LICENSE-2.0
 *
 * Unless required by applicable law or agreed to in writing, software
 * distributed under the License is distributed on an "AS IS" BASIS,
 * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
 * See the License for the specific language governing permissions and
 * limitations under the License.
 */

import java.util.ArrayList;
import java.util.List;

import org.junit.jupiter.api.Test;

import static org.junit.jupiter.api.Assertions.assertEquals;

/**
 * <p>TopologicalSorterTest class.</p>
 *
 * @author <a href="michal.maczka@dimatics.com">Michal Maczka</a>
 * @version $Id: $Id
 * @since 3.4.0
 */
class TopologicalSorterTest {
    /**
     * <p>testDfs.</p>
     *
     * @throws org.codehaus.plexus.util.dag.CycleDetectedException if any.
     */
    @Test
    void dfs() throws CycleDetectedException {
        // a --> b --->c
        //
        // result a,b,c
        final DAG dag1 = new DAG();

        dag1.addEdge("a", "b");

        dag1.addEdge("b", "c");

        final List<String> expected1 = new ArrayList<>();

        expected1.add("c");

        expected1.add("b");

        expected1.add("a");

        final List<String> actual1 = TopologicalSorter.sort(dag1);

        assertEquals(expected1, actual1, "Order is different then expected");

        //
        // a <-- b <---c
        //
        // result c, b, a
        final DAG dag2 = new DAG();

        dag2.addVertex("a");

        dag2.addVertex("b");

        dag2.addVertex("c");

        dag2.addEdge("b", "a");

        dag2.addEdge("c", "b");

        final List<String> expected2 = new ArrayList<>();

        expected2.add("a");

        expected2.add("b");

        expected2.add("c");

        final List<String> actual2 = TopologicalSorter.sort(dag2);

        assertEquals(expected2, actual2, "Order is different then expected");

        //
        // a --> b --> c --> e
        // | | |
        // | V V
        // --> d <-- f --> g
        // result d, g, f, c, b, a
        final DAG dag3 = new DAG();

        // force order of nodes in the graph
        dag3.addVertex("a");

        dag3.addVertex("b");

        dag3.addVertex("c");

        dag3.addVertex("d");

        dag3.addVertex("e");

        dag3.addVertex("f");

        dag3.addEdge("a", "b");

        dag3.addEdge("b", "c");

        dag3.addEdge("b", "d");

        dag3.addEdge("c", "d");

        dag3.addEdge("c", "e");

        dag3.addEdge("f", "d");

        dag3.addEdge("e", "f");

        dag3.addEdge("f", "g");

        final List<String> expected3 = new ArrayList<>();

        expected3.add("d");

        expected3.add("g");

        expected3.add("f");

        expected3.add("e");

        expected3.add("c");

        expected3.add("b");

        expected3.add("a");

        final List<String> actual3 = TopologicalSorter.sort(dag3);

        assertEquals(expected3, actual3, "Order is different then expected");

        //
        // a --> b --> c --> e
        // | | |
        // | V V
        // --> d <-- f
        // result d, f, e, c, b, a
        final DAG dag4 = new DAG();
        // force order of nodes in the graph

        dag4.addVertex("f");

        dag4.addVertex("e");

        dag4.addVertex("d");

        dag4.addVertex("c");

        dag4.addVertex("a");

        dag4.addVertex("b");

        dag4.addEdge("a", "b");

        dag4.addEdge("b", "c");

        dag4.addEdge("b", "d");

        dag4.addEdge("c", "d");

        dag4.addEdge("c", "e");

        dag4.addEdge("f", "d");

        dag4.addEdge("e", "f");

        final List<String> expected4 = new ArrayList<>();

        expected4.add("d");

        expected4.add("f");

        expected4.add("e");

        expected4.add("c");

        expected4.add("b");

        expected4.add("a");

        final List<String> actual4 = TopologicalSorter.sort(dag4);

        assertEquals(expected4, actual4, "Order is different then expected");
    }
}