TopologicalSorter { public List<VertexClass> sort() { while (numVerts > 0) { int currentVertex = noSuccessors(); if (currentVertex == -1) { throw new IllegalStateException("BuildTypes have a cyclical dependencies"); } sortedArray[numVerts - 1] = vertices[currentVertex]; deleteVertex(currentVertex); } ArrayList<VertexClass> result = newArrayList(); for (Vertex vertex : sortedArray) result.add((VertexClass) vertex); return result; } TopologicalSorter(int size);  TopologicalSorter(Collection<VertexClass> vertices); int addVertex(VertexClass buildTypeId); void addEdge(int start, int end); List<VertexClass> sort(); int noSuccessors();  }
@Test public void dependsOnProperlyOrdered() { TestNode n4 = new TestNode(buildTypeId4); TestNode n3 = new TestNode(buildTypeId3, n4); TestNode n2 = new TestNode(buildTypeId2, n3); TestNode n1 = new TestNode(buildTypeId1, n2); List<TestNode> sorted = new TopologicalSorter<TestNode>(ImmutableList.of(n1, n2, n3, n4)).sort(); assertTrue(sorted.indexOf(n1) < sorted.indexOf(n2)); assertTrue(sorted.indexOf(n2) < sorted.indexOf(n3)); assertTrue(sorted.indexOf(n3) < sorted.indexOf(n4)); }
@Test public void missingDependency() { TestNode n4 = new TestNode(buildTypeId4); TestNode n3 = new TestNode(buildTypeId3, n4); TestNode n2 = new TestNode(buildTypeId2, n3); TestNode n1 = new TestNode(buildTypeId1, n2); List<TestNode> sorted = new TopologicalSorter<TestNode>(ImmutableList.of(n1, n2, n3)).sort(); assertTrue(sorted.indexOf(n1) < sorted.indexOf(n2)); assertTrue(sorted.indexOf(n2) < sorted.indexOf(n3)); assertTrue(sorted.indexOf(n4) == -1); }