sp-04/test/ch/usi/inf/sp/graph/TraversalTest.java

package ch.usi.inf.sp.graph;

import org.junit.jupiter.api.Test;

import java.util.Arrays;
import java.util.List;

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

class TraversalTest {

    //--- simple DiGraph, Node, and Edge implementations just for testing
    private static class TG extends DiGraph<TN, TE> {
        private TN root;
        public TG(TN root) { this.root = root; }
        public TN getRoot() { return root; }
        public void edge(TN from, TN to) {
            if (!getNodes().contains(from)) addNode(from);
            if (!getNodes().contains(to)) addNode(to);
            TE edge = new TE();
            addEdge(edge);
            connect(from, edge, to);
        }
    }
    private static class TN extends Node<TE> {
        private String label;
        public TN(String label) { this.label = label; }
        @Override
        public String toString() {
            return label;
        }
    }
    private static class TE extends Edge<TN> {}


    @Test
    void getNodesInPostOrderTwoNodes() {
        TN a = new TN("A");
        TN b = new TN("B");
        TG graph = new TG(a);
        graph.edge(a, b);
        //System.out.print(graph);

        List<TN> postOrderNodes = Traversal.getNodesInPostOrder(graph, graph.getRoot());
        //System.out.println("post order: "+postOrderNodes);
        assertEquals(2, postOrderNodes.size());
        assertIterableEquals(Arrays.asList(b, a), postOrderNodes);

        List<TN> reversePostOrderNodes = Traversal.getNodesInReversePostOrder(graph, graph.getRoot());
        //System.out.println("reverse post order: "+reversePostOrderNodes);
        assertEquals(2, reversePostOrderNodes.size());
        assertIterableEquals(Arrays.asList(a, b), reversePostOrderNodes);
    }

    @Test
    void getNodesInPostOrderThreeNodes() {
        TN a = new TN("A");
        TN b = new TN("B");
        TN c = new TN("C");
        TG graph = new TG(a);
        graph.edge(a, b);
        graph.edge(b, c);
        //System.out.print(graph);

        List<TN> postOrderNodes = Traversal.getNodesInPostOrder(graph, graph.getRoot());
        //System.out.println("post order: "+postOrderNodes);
        assertEquals(3, postOrderNodes.size());
        assertIterableEquals(Arrays.asList(new TN[] {c,b,a}), postOrderNodes);

        List<TN> reversePostOrderNodes = Traversal.getNodesInReversePostOrder(graph, graph.getRoot());
        //System.out.println("reverse post order: "+reversePostOrderNodes);
        assertEquals(3, reversePostOrderNodes.size());
        assertIterableEquals(Arrays.asList(new TN[] {a,b,c}), reversePostOrderNodes);
    }

    @Test
    void getNodesInPostOrderDiamond() {
        TN a = new TN("A");
        TN b = new TN("B");
        TN c = new TN("C");
        TN d = new TN("D");
        TG graph = new TG(a);
        graph.edge(a, b);
        graph.edge(a, c);
        graph.edge(b, d);
        graph.edge(c, d);
        //System.out.print(graph);

        List<TN> postOrderNodes = Traversal.getNodesInPostOrder(graph, graph.getRoot());
        //System.out.println("post order: "+postOrderNodes);
        assertEquals(4, postOrderNodes.size());
        assertSame(d, postOrderNodes.get(0));
        assertSame(a, postOrderNodes.get(3));

        List<TN> reversePostOrderNodes = Traversal.getNodesInReversePostOrder(graph, graph.getRoot());
        //System.out.println("reverse post order: "+reversePostOrderNodes);
        assertEquals(4, reversePostOrderNodes.size());
        assertSame(d, reversePostOrderNodes.get(3));
        assertSame(a, reversePostOrderNodes.get(0));
    }

    @Test
    void getNodesInPostOrderExample() {
        // example graph from
        // https://eli.thegreenplace.net/2015/directed-graph-traversal-orderings-and-applications-to-data-flow-analysis/
        TN a = new TN("A");
        TN b = new TN("B");
        TN c = new TN("C");
        TN d = new TN("D");
        TN e = new TN("E");
        TN t = new TN("T");
        TG graph = new TG(a);
        graph.edge(a, c);
        graph.edge(a, b);
        graph.edge(a, t);
        graph.edge(c, b);
        graph.edge(t, b);
        graph.edge(c, e);
        graph.edge(e, d);
        graph.edge(b, d);
        //System.out.print(graph);

        List<TN> postOrderNodes = Traversal.getNodesInPostOrder(graph, graph.getRoot());
        // this assertion is overly strict: it assumes the traversal algorithm iterates forward through the out edges
        //System.out.println("post order: "+postOrderNodes);
        assertEquals(6, postOrderNodes.size());
        assertIterableEquals(Arrays.asList(new TN[] {d,b,e,c,t,a}), postOrderNodes);

        List<TN> reversePostOrderNodes = Traversal.getNodesInReversePostOrder(graph, graph.getRoot());
        // this assertion is overly strict: it assumes the traversal algorithm iterates forward through the out edges
        //System.out.println("reverse post order: "+reversePostOrderNodes);
        assertEquals(6, reversePostOrderNodes.size());
        assertIterableEquals(Arrays.asList(new TN[] {a,t,c,e,b,d}), reversePostOrderNodes);
    }

    @Test
    void getNodesInPostOrderExample2() {
        // example graph from
        // Christensen's MS thesis, Figure 2.2
        TN a = new TN("A");
        TN b = new TN("B");
        TN c = new TN("C");
        TN d = new TN("D");
        TN e = new TN("E");
        TN f = new TN("F");
        TG graph = new TG(a);
        graph.edge(a, b);
        graph.edge(a, d);
        graph.edge(b, c);
        graph.edge(d, e);
        graph.edge(d, f);
        graph.edge(e, b);
        graph.edge(f, e);
        //System.out.print(graph);

        List<TN> postOrderNodes = Traversal.getNodesInPostOrder(graph, graph.getRoot());
        // this assertion is overly strict: it assumes the traversal algorithm iterates forward through the out edges
        //System.out.println("post order: "+postOrderNodes);
        assertIterableEquals(Arrays.asList(new TN[] {c,b,e,f,d,a}), postOrderNodes);

        List<TN> reversePostOrderNodes = Traversal.getNodesInReversePostOrder(graph, graph.getRoot());
        // this assertion is overly strict: it assumes the traversal algorithm iterates forward through the out edges
        //System.out.println("reverse post order: "+reversePostOrderNodes);
        assertIterableEquals(Arrays.asList(new TN[] {a,d,f,e,b,c}), reversePostOrderNodes);
    }

    @Test
    void getNodesInPostOrderExample3() {
        // example graph from
        // Cooper et al., Figure 2
        TN n1 = new TN("1");
        TN n2 = new TN("2");
        TN n3 = new TN("3");
        TN n4 = new TN("4");
        TN n5 = new TN("5");
        TG graph = new TG(n5);
        graph.edge(n5, n3);
        graph.edge(n5, n4);
        graph.edge(n3, n2);
        graph.edge(n2, n1);
        graph.edge(n1, n2);
        graph.edge(n4, n1);
        //System.out.print(graph);

        List<TN> postOrderNodes = Traversal.getNodesInPostOrder(graph, graph.getRoot());
        // this assertion is overly strict: it assumes the traversal algorithm iterates forward through the out edges
        //System.out.println("post order: "+postOrderNodes);
        assertIterableEquals(Arrays.asList(new TN[] {n1,n2,n3,n4,n5}), postOrderNodes);

        List<TN> reversePostOrderNodes = Traversal.getNodesInReversePostOrder(graph, graph.getRoot());
        // this assertion is overly strict: it assumes the traversal algorithm iterates forward through the out edges
        //System.out.println("reverse post order: "+reversePostOrderNodes);
        assertIterableEquals(Arrays.asList(new TN[] {n5,n4,n3,n2,n1}), reversePostOrderNodes);
    }

    @Test
    void getNodesInPostOrderExample4() {
        // example graph from
        // Cooper et al., Figure 4
        TN n1 = new TN("1");
        TN n2 = new TN("2");
        TN n3 = new TN("3");
        TN n4 = new TN("4");
        TN n5 = new TN("5");
        TN n6 = new TN("6");
        TG graph = new TG(n6);
        graph.edge(n6, n4);
        graph.edge(n6, n5);
        graph.edge(n4, n3);
        graph.edge(n4, n2);
        graph.edge(n2, n1);
        graph.edge(n2, n3);
        graph.edge(n3, n2);
        graph.edge(n5, n1);
        graph.edge(n1, n2);
        //System.out.print(graph);

        List<TN> postOrderNodes = Traversal.getNodesInPostOrder(graph, graph.getRoot());
        // this assertion is overly strict: it assumes the traversal algorithm iterates forward through the out edges
        //System.out.println("post order: "+postOrderNodes);
        assertIterableEquals(Arrays.asList(new TN[] {n1,n2,n3,n4,n5,n6}), postOrderNodes);

        List<TN> reversePostOrderNodes = Traversal.getNodesInReversePostOrder(graph, graph.getRoot());
        // this assertion is overly strict: it assumes the traversal algorithm iterates forward through the out edges
        //System.out.println("reverse post order: "+reversePostOrderNodes);
        assertIterableEquals(Arrays.asList(new TN[] {n6,n5,n4,n3,n2,n1}), reversePostOrderNodes);
    }

}