CycleFinder { public List<T> findCycle() { resetState(); for (T vertex : graph.getVertices()) { if (colors.get(vertex) == WHITE) { if (visitDepthFirst(vertex, new ArrayList<>(singletonList(vertex)))) { if (cycle == null) throw new IllegalStateException("Null cycle - this should never happen"); if (cycle.isEmpty()) throw new IllegalStateException("Empty cycle - this should never happen"); log.log(FINE, "Cycle detected: " + cycle); return cycle; } } } return new ArrayList<>(); } CycleFinder(Graph<T> graph); List<T> findCycle();  }
@Test public void graph_without_cycles_returns_no_cycle() { var graph = new Graph<Vertices>(); graph.edge(A, B); graph.edge(B, C); graph.edge(A, C); graph.edge(D, A); var cycleFinder = new CycleFinder<>(graph); assertThat(cycleFinder.findCycle(), empty()); }
@Test public void graph_with_cycle_returns_cycle() { var graph = new Graph<Vertices>(); graph.edge(A, B); graph.edge(B, C); graph.edge(C, A); var cycleFinder = new CycleFinder<>(graph); assertThat(cycleFinder.findCycle(), contains(A, B, C, A)); }
@Test public void graph_with_self_referencing_vertex_returns_cycle() { var graph = new Graph<Vertices>(); graph.edge(A, A); var cycleFinder = new CycleFinder<>(graph); assertThat(cycleFinder.findCycle(), contains(A, A)); }
@Test public void leading_nodes_are_stripped_from_cycle() { var graph = new Graph<Vertices>(); graph.edge(A, B); graph.edge(B, C); graph.edge(C, B); var cycleFinder = new CycleFinder<>(graph); assertThat(cycleFinder.findCycle(), contains(B, C, B)); }
@Test public void findCycle_is_idempotent_with_cycle() { var graph = new Graph<Vertices>(); graph.edge(A, A); var cycleFinder = new CycleFinder<>(graph); assertThat(cycleFinder.findCycle(), contains(A, A)); assertThat(cycleFinder.findCycle(), contains(A, A)); }
@Test public void findCycle_is_idempotent_without_cycle() { var graph = new Graph<Vertices>(); graph.edge(A, B); var cycleFinder = new CycleFinder<>(graph); assertThat(cycleFinder.findCycle(), empty()); assertThat(cycleFinder.findCycle(), empty()); }