DependencyGraph { public Stream<T> getBuildChain() throws CycleDetectedException { DefaultDirectedGraph<T, DefaultEdge> graph = builder.build(); ensureNoCycle(graph); return Iterators.toStream(new TopologicalOrderIterator<>(graph)); } DependencyGraph(Function<T, Optional<T>> getParent); void registerItem(T item); Stream<T> getBuildChain(); String toString();  }
@Test public void getBuildChainShouldReturnOrderedMailbox() { Commit a = new Commit("A"); Commit b = new Commit("B", a); Commit c = new Commit("C", b); DependencyGraph<Commit> graph = new DependencyGraph<>(Commit::getParent); Stream.of(b, a, c) .forEach(graph::registerItem); Stream<Commit> orderedMailboxes = graph.getBuildChain(); assertThat(orderedMailboxes).extracting(Commit::getMessage).containsExactly("A", "B", "C"); }
@Test public void getBuildChainWithEmptyGraphShouldReturnEmpty() { DependencyGraph<Commit> graph = new DependencyGraph<>(m -> null); assertThat(graph.getBuildChain()).isEmpty(); }
@Test public void getBuildChainOnIsolatedVerticesShouldReturnSameOrder() { DependencyGraph<Commit> graph = new DependencyGraph<>(m -> Optional.empty()); ImmutableList<Commit> isolatedMailboxes = ImmutableList.of(new Commit("A"), new Commit("B"), new Commit("C")); isolatedMailboxes.forEach(graph::registerItem); List<Commit> orderedResultList = graph.getBuildChain().collect(Collectors.toList()); assertThat(orderedResultList).isEqualTo(isolatedMailboxes); }
@Test public void getBuildChainOnTwoIsolatedTreesShouldWork() { Commit a = new Commit("A"); Commit b = new Commit("B", a); Commit c = new Commit("C", b); Commit d = new Commit("D"); Commit e = new Commit("E", d); Commit f = new Commit("F", d); DependencyGraph<Commit> testee = new DependencyGraph<>(Commit::getParent); Stream.of(b, a, e, d, f, c) .forEach(testee::registerItem); Stream<Commit> actual = testee.getBuildChain(); assertThat(actual).extracting(Commit::getMessage).containsExactly("A", "D", "B", "E", "F", "C"); }
@Test public void getBuildChainOnComplexTreeShouldWork() { Commit a = new Commit("A"); Commit b = new Commit("B", a); Commit c = new Commit("C", a); Commit d = new Commit("D", b); Commit e = new Commit("E", b); Commit f = new Commit("F", c); Commit g = new Commit("G", e); DependencyGraph<Commit> testee = new DependencyGraph<>(Commit::getParent); Stream.of(b, a, e, g, d, f, c) .forEach(testee::registerItem); Stream<Commit> actual = testee.getBuildChain(); assertThat(actual).extracting(Commit::getMessage).containsExactly("A", "B", "C", "E", "D", "F", "G"); }
@Test(expected = CycleDetectedException.class) public void getBuildChainOnTreeWithLoopShouldFail() { Commit a = new Commit("A"); Commit b = new Commit("B", a); a.setParent(b); DependencyGraph<Commit> testee = new DependencyGraph<>(Commit::getParent); Stream.of(a, b) .forEach(testee::registerItem); testee.getBuildChain(); }
@Test(expected = CycleDetectedException.class) public void getBuildChainOnTreeWithComplexLoopShouldFail() { Commit a = new Commit("A"); Commit b = new Commit("B", a); Commit c = new Commit("C"); Commit d = new Commit("D", c); Commit e = new Commit("E", d); Commit f = new Commit("F", e); c.setParent(f); DependencyGraph<Commit> testee = new DependencyGraph<>(Commit::getParent); Stream.of(a, b, c, d, e, f) .forEach(testee::registerItem); testee.getBuildChain(); }