229 lines
8.8 KiB
Java
229 lines
8.8 KiB
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);
|
||
|
|
}
|
||
|
|
|
||
|
|
}
|