1 package net.sf.fleet.test;
2
3 import java.util.Iterator;
4 import java.util.List;
5
6 import net.sf.fleet.util.CyclicGraphException;
7 import net.sf.fleet.util.DirectedAcyclicGraph;
8
9 import org.testng.annotations.Test;
10 import static org.testng.Assert.*;
11
12 public class DAGTest {
13 @Test
14 public void testEmpty() throws CyclicGraphException {
15 DirectedAcyclicGraph<Object> lGraph = new DirectedAcyclicGraph<Object>();
16 assertEquals(lGraph.topologicalSort().size(),0);
17 }
18
19 @Test
20 public void testOne() throws CyclicGraphException {
21 DirectedAcyclicGraph<Object> lGraph = new DirectedAcyclicGraph<Object>();
22 Object lObj1 = new Object();
23 lGraph.addNode(lObj1);
24
25 List<Object> lSorted = lGraph.topologicalSort();
26 assertEquals(lSorted.size(), 1);
27 assertSame(lSorted.iterator().next(), lObj1);
28 }
29
30 @Test
31 public void testSimple() throws CyclicGraphException {
32 DirectedAcyclicGraph<Object> lGraph = new DirectedAcyclicGraph<Object>();
33 Object lObj1 = new Object();
34 Object lObj2 = new Object();
35
36 lGraph.addNode(lObj1);
37 lGraph.addNode(lObj2);
38 lGraph.addEdge(lObj2, lObj1);
39
40 List<Object> lSorted = lGraph.topologicalSort();
41
42 assertEquals(lSorted.size(), 2);
43 Iterator<Object> lResults = lSorted.iterator();
44 assertSame(lResults.next(), lObj2);
45 assertSame(lResults.next(), lObj1);
46 }
47
48 @Test
49 public void testSimpleCyclic() {
50 DirectedAcyclicGraph<Object> lGraph = new DirectedAcyclicGraph<Object>();
51 Object lObj1 = new Object();
52 Object lObj2 = new Object();
53
54 lGraph.addNode(lObj1);
55 lGraph.addNode(lObj2);
56 lGraph.addEdge(lObj1, lObj2);
57 lGraph.addEdge(lObj2, lObj1);
58
59 try {
60 List<Object> lResults = lGraph.topologicalSort();
61 fail("Expected CyclicGraphException, instead received: " + lResults);
62 } catch (CyclicGraphException e) {
63
64 }
65 }
66
67 public void testComplex() throws CyclicGraphException {
68 DirectedAcyclicGraph<Object> lGraph = new DirectedAcyclicGraph<Object>();
69 Object lObj1 = new Object();
70 Object lObj2 = new Object();
71 Object lObj3 = new Object();
72 Object lObj4 = new Object();
73 Object lObj5 = new Object();
74 Object lObj6 = new Object();
75
76 lGraph.addNode(lObj1);
77 lGraph.addNode(lObj2);
78 lGraph.addNode(lObj3);
79 lGraph.addNode(lObj4);
80 lGraph.addNode(lObj5);
81 lGraph.addNode(lObj6);
82 lGraph.addEdge(lObj1, lObj3);
83 lGraph.addEdge(lObj2, lObj3);
84 lGraph.addEdge(lObj3, lObj5);
85 lGraph.addEdge(lObj4, lObj6);
86 lGraph.addEdge(lObj5, lObj6);
87 lGraph.addEdge(lObj2, lObj4);
88
89 List<Object> lSorted = lGraph.topologicalSort();
90 assertInOrder(lSorted, lObj1, lObj3);
91 assertInOrder(lSorted, lObj2, lObj3);
92 assertInOrder(lSorted, lObj3, lObj5);
93 assertInOrder(lSorted, lObj4, lObj6);
94 assertInOrder(lSorted, lObj5, lObj6);
95 assertInOrder(lSorted, lObj2, lObj4);
96
97 assertInOrder(lSorted, lObj2, lObj5);
98 }
99
100 public void testComplexCyclic() {
101 DirectedAcyclicGraph<Object> lGraph = new DirectedAcyclicGraph<Object>();
102 Object lObj1 = new Object();
103 Object lObj2 = new Object();
104 Object lObj3 = new Object();
105 Object lObj4 = new Object();
106 Object lObj5 = new Object();
107 Object lObj6 = new Object();
108
109 lGraph.addNode(lObj1);
110 lGraph.addNode(lObj2);
111 lGraph.addNode(lObj3);
112 lGraph.addNode(lObj4);
113 lGraph.addNode(lObj5);
114 lGraph.addNode(lObj6);
115 lGraph.addEdge(lObj1, lObj3);
116 lGraph.addEdge(lObj2, lObj3);
117 lGraph.addEdge(lObj3, lObj5);
118 lGraph.addEdge(lObj4, lObj6);
119 lGraph.addEdge(lObj5, lObj6);
120 lGraph.addEdge(lObj2, lObj4);
121
122
123 lGraph.addEdge(lObj6, lObj1);
124
125 try {
126 List<Object> lResults = lGraph.topologicalSort();
127 fail("Expected CyclicGraphException, recieved: " + lResults);
128 } catch (CyclicGraphException e) {
129
130 }
131 }
132
133 private void assertInOrder(List<Object> pSortedList, Object pBefore, Object pAfter) {
134 assertTrue(pSortedList.indexOf(pBefore) < pSortedList.indexOf(pAfter));
135 }
136 }