TopologicalSorter { public List<Node> sort(Node root, boolean failOnCycles) { return new Sort(root, failOnCycles).compute(); }  List<Node> sort(Node root, boolean failOnCycles);  }
@Test public void happy_case() { Node a = createNode("a", "1"); Node b = createNode("b", "1"); Node c = createNode("c", "1"); Node d = createNode("d", "1"); Node e = createNode("e", "1"); a.addChildNode(b); a.addChildNode(c); b.addChildNode(d); c.addChildNode(e); List<String> r = new TopologicalSorter().sort(a, true).stream().map(Node::getArtifactId).collect(Collectors.toList()); Assert.assertTrue(r.indexOf("a") > r.indexOf("b")); Assert.assertTrue(r.indexOf("a") > r.indexOf("c")); Assert.assertTrue(r.indexOf("b") > r.indexOf("d")); Assert.assertTrue(r.indexOf("c") > r.indexOf("e")); }
@Test public void depth_first_counter_example() { Node a = createNode("a", "1"); Node b = createNode("b", "1"); Node c = createNode("c", "2"); Node oc = createOmittedNode("c", "1"); Node d = createNode("d", "1"); a.addChildNode(oc); a.addChildNode(b); b.addChildNode(c); c.addChildNode(d); List<Node> resultNodes = new TopologicalSorter().sort(a, true); List<String> r = resultNodes.stream().map(Node::getArtifactId).collect(Collectors.toList()); Assert.assertTrue(r.indexOf("a") > r.indexOf("c")); Assert.assertTrue(r.indexOf("a") > r.indexOf("b")); Assert.assertTrue(r.indexOf("b") > r.indexOf("c")); Assert.assertTrue(r.indexOf("c") > r.indexOf("d")); Assert.assertTrue(resultNodes.contains(c)); }
@Test public void breadth_first_counter_example() { Node a = createNode("a", "1"); Node b = createNode("b", "1"); Node c = createNode("c", "1"); Node d = createNode("d", "1"); Node od = createOmittedNode("d", "2"); Node e = createNode("e", "1"); a.addChildNode(b); b.addChildNode(c); c.addChildNode(od); a.addChildNode(d); d.addChildNode(e); List<Node> resultNodes = new TopologicalSorter().sort(a, true); List<String> r = resultNodes.stream().map(Node::getArtifactId).collect(Collectors.toList()); Assert.assertTrue(r.indexOf("a") > r.indexOf("b")); Assert.assertTrue(r.indexOf("b") > r.indexOf("c")); Assert.assertTrue(r.indexOf("a") > r.indexOf("d")); Assert.assertTrue(r.indexOf("d") > r.indexOf("e")); Assert.assertTrue(resultNodes.contains(d)); }
@Test public void cycle_lenient() { Node a = createNode("a", "1"); Node b = createNode("b", "1"); Node c = createNode("c", "1"); Node d = createNode("d", "1"); Node oc = createOmittedNode("c", "1"); Node ob = createOmittedNode("b", "1"); a.addChildNode(b); a.addChildNode(c); b.addChildNode(d); c.addChildNode(ob); b.addChildNode(oc); List<Node> resultNodes = new TopologicalSorter().sort(a, false); List<String> r = resultNodes.stream().map(Node::getArtifactId).collect(Collectors.toList()); Assert.assertTrue(r.indexOf("a") > r.indexOf("b")); Assert.assertTrue(r.indexOf("a") > r.indexOf("c")); Assert.assertTrue(r.indexOf("b") > r.indexOf("d")); }
@Test public void cycle_strict() { Node a = createNode("a", "1"); Node b = createNode("b", "1"); Node c = createNode("c", "1"); Node d = createNode("d", "1"); Node oc = createOmittedNode("c", "1"); Node ob = createOmittedNode("b", "1"); a.addChildNode(b); a.addChildNode(c); b.addChildNode(d); c.addChildNode(ob); b.addChildNode(oc); try { new TopologicalSorter().sort(a, true); } catch (CarnotzetDefinitionException e) { Assert.assertTrue(e.getMessage().contains("Cycle detected")); return; } fail("Expected a CarnotzetDefinitionException to be thrown, but it was not."); }
@Test public void cycle_larger() { Node a = createNode("a", "1"); Node b = createNode("b", "1"); Node c = createNode("c", "1"); Node d = createNode("d", "1"); Node oa = createOmittedNode("a", "1"); a.addChildNode(b); b.addChildNode(c); c.addChildNode(d); d.addChildNode(oa); try { new TopologicalSorter().sort(a, true); } catch (CarnotzetDefinitionException e) { Assert.assertTrue(e.getMessage().contains("Cycle detected")); return; } fail("Expected a CarnotzetDefinitionException to be thrown, but it was not."); }