1 package test; 2 3 import org.testng.Assert; 4 import org.testng.TestNGException; 5 import org.testng.annotations.Test; 6 import org.testng.internal.Graph; 7 import org.testng.internal.Tarjan; 8 9 import java.util.List; 10 11 12 /** 13 * This class 14 * 15 * @author cbeust 16 */ 17 public class GraphTest { 18 19 @Test sort()20 public void sort() { 21 Graph<String> g = new Graph<>(); 22 g.addNode("3"); 23 g.addNode("1"); 24 g.addNode("2.2"); 25 g.addNode("independent"); 26 g.addNode("2.1"); 27 g.addNode("2"); 28 29 g.addPredecessor("3", "2"); 30 g.addPredecessor("3", "2.1"); 31 g.addPredecessor("3", "2.2"); 32 g.addPredecessor("2", "1"); 33 g.addPredecessor("2.1", "1"); 34 g.addPredecessor("2.2", "1"); 35 36 g.topologicalSort(); 37 List<String> l = g.getStrictlySortedNodes(); 38 int i = 0; 39 Assert.assertTrue("1".equals(l.get(i))); 40 i++; 41 Assert.assertTrue("2".equals(l.get(i)) || "2.1".equals(l.get(i)) || "2.2".equals(l.get(i))); 42 i++; 43 Assert.assertTrue("2".equals(l.get(i)) || "2.1".equals(l.get(i)) || "2.2".equals(l.get(i))); 44 i++; 45 Assert.assertTrue("2".equals(l.get(i)) || "2.1".equals(l.get(i)) || "2.2".equals(l.get(i))); 46 i++; 47 Assert.assertTrue("3".equals(l.get(i))); 48 49 Assert.assertTrue(1 == g.getIndependentNodes().size()); 50 } 51 52 @Test(expectedExceptions = org.testng.TestNGException.class) cycleShouldFail()53 public void cycleShouldFail() { 54 Graph<String> g = createCyclicGraph(); 55 g.topologicalSort(); 56 } 57 58 @Test cycleShouldBeCorrect()59 public void cycleShouldBeCorrect() { 60 Graph<String> g = null; 61 try { 62 g = createCyclicGraph(); 63 g.topologicalSort(); 64 } 65 catch(TestNGException ex) { 66 Tarjan<String> t = new Tarjan<>(g, "1"); 67 Assert.assertEquals(t.getCycle().size(), 3); 68 } 69 70 } 71 createCyclicGraph()72 private Graph<String> createCyclicGraph() { 73 Graph<String> g = new Graph<>(); 74 g.addNode("3"); 75 g.addNode("2"); 76 g.addNode("1"); 77 78 g.addPredecessor("3", "2"); 79 g.addPredecessor("2", "1"); 80 g.addPredecessor("1", "3"); 81 82 return g; 83 } 84 85 @Test findPredecessors()86 public void findPredecessors() { 87 Graph<String> g = new Graph<>(); 88 g.addNode("3"); 89 g.addNode("1"); 90 g.addNode("2.2"); 91 g.addNode("independent"); 92 g.addNode("2.1"); 93 g.addNode("2"); 94 95 // 1 -> 2.1, 2.2, 2.3 --> 3 96 g.addPredecessor("3", "2"); 97 g.addPredecessor("3", "2.1"); 98 g.addPredecessor("3", "2.2"); 99 g.addPredecessor("2", "1"); 100 g.addPredecessor("2.1", "1"); 101 g.addPredecessor("2.2", "1"); 102 103 // Invoke sort to make sure there is no side effect 104 g.topologicalSort(); 105 106 // 107 // Test findPredecessors 108 // 109 { 110 List<String> predecessors = g.findPredecessors("2"); 111 Assert.assertTrue(predecessors.size() == 1); 112 Assert.assertTrue(predecessors.get(0).equals("1")); 113 } 114 115 { 116 List<String> predecessors = g.findPredecessors("3"); 117 118 Assert.assertTrue(predecessors.size() == 4); 119 Assert.assertTrue(predecessors.get(0).equals("1")); 120 Assert.assertTrue(predecessors.get(1).equals("2.1") 121 || predecessors.get(1).equals("2.2") 122 || predecessors.get(1).equals("2")); 123 Assert.assertTrue(predecessors.get(2).equals("2.1") 124 || predecessors.get(2).equals("2.2") 125 || predecessors.get(2).equals("2")); 126 Assert.assertTrue(predecessors.get(3).equals("2.1") 127 || predecessors.get(3).equals("2.2") 128 || predecessors.get(3).equals("2")); 129 } 130 } 131 132 // Using an earlier implementation of Graph.findPrecessors, finding 133 // predecessors in certain kinds of graphs where many nodes have the 134 // same predecessors could be very slow, since the old implementation 135 // would explore the same nodes repeatedly. This situation could 136 // happen when test methods are organized in several groups, with 137 // dependsOnGroups annotations so that each method in one group depends 138 // on all of the methods in another group. If there were several 139 // such groups depending on each other in a chain, the combinatorics 140 // of the old method became excessive. This test builds a 72-node graph that 141 // emulates this situation, then call Graph.findPredecessors. The old 142 // implementation run this in 70+ seconds on my computer, the new implementation 143 // takes a few milliseconds. In practice, with larger graphs, the former 144 // slowness could get very extreme, taking hours or more to complete 145 // in some real user situations. 146 // 147 @Test(timeOut = 5000) // If this takes more than 5 seconds we've definitely regressed. findPredecessorsTiming()148 public void findPredecessorsTiming() { 149 Graph<String> g = new Graph<>(); 150 151 final String rootNode = "myroot"; 152 final String independentNode = "independent"; 153 g.addNode(rootNode); 154 g.addNode(independentNode); 155 156 final int maxDepth = 7; 157 final int nodesPerDepth = 10; // must be < 100 158 // 159 // Add maxDepth groups of new nodes, where each group contains nodesPerDepth 160 // nodes, and each node in a group a depth N has each node in the group 161 // at depth (N-1) as a predecessor. 162 // 163 for (int depth = 1; depth <= maxDepth; depth++) { 164 for (int i = 0; i < nodesPerDepth; i++) { 165 String newNode = String.valueOf(i + (100 * depth)); 166 g.addNode(newNode); 167 if (depth == 1) { 168 continue; 169 } 170 for (int j = 0; j < nodesPerDepth; j++) { 171 String prevNode = String.valueOf(j + (100 * (depth - 1))); 172 g.addPredecessor(newNode, prevNode); 173 } 174 } 175 } 176 177 // Finally, make all of the nodes in the group at depth maxDepth 178 // be predecessors of rootNode. 179 // 180 for (int i = 0; i < nodesPerDepth; i++) { 181 String node = String.valueOf(i + (100 * maxDepth)); 182 g.addPredecessor(rootNode, node); 183 } 184 185 // Now we're done building the graph, which has (maxDepth * nodesPerDepth) + 2 186 // nodes. rootNode has all of the other nodes except independentNode 187 // as predecessors. 188 189 // 190 // Test findPredecessors 191 // 192 { 193 List<String> predecessors = g.findPredecessors(rootNode); 194 Assert.assertTrue(predecessors.size() == (maxDepth * nodesPerDepth)); 195 } 196 } 197 } 198