From 49f480288a0f84034ac204bd52d92177ce19a9d1 Mon Sep 17 00:00:00 2001 From: gjoranv Date: Mon, 22 Jul 2019 11:34:26 +0200 Subject: Add utility to find cycles in a directed graph. - These classes are independent from di classes and can be used as a tool for graphs in general. --- .../di/componentgraph/cycle/CycleFinder.java | 97 ++++++++++++++++++++++ .../container/di/componentgraph/cycle/Graph.java | 39 +++++++++ .../di/componentgraph/cycle/CycleFinderTest.java | 87 +++++++++++++++++++ .../di/componentgraph/cycle/GraphTest.java | 69 +++++++++++++++ 4 files changed, 292 insertions(+) create mode 100644 container-di/src/main/java/com/yahoo/container/di/componentgraph/cycle/CycleFinder.java create mode 100644 container-di/src/main/java/com/yahoo/container/di/componentgraph/cycle/Graph.java create mode 100644 container-di/src/test/java/com/yahoo/container/di/componentgraph/cycle/CycleFinderTest.java create mode 100644 container-di/src/test/java/com/yahoo/container/di/componentgraph/cycle/GraphTest.java diff --git a/container-di/src/main/java/com/yahoo/container/di/componentgraph/cycle/CycleFinder.java b/container-di/src/main/java/com/yahoo/container/di/componentgraph/cycle/CycleFinder.java new file mode 100644 index 00000000000..14d64dd1863 --- /dev/null +++ b/container-di/src/main/java/com/yahoo/container/di/componentgraph/cycle/CycleFinder.java @@ -0,0 +1,97 @@ +/* + * Copyright 2019 Oath Inc. Licensed under the terms of the Apache 2.0 license. See LICENSE in the project root. + */ +package com.yahoo.container.di.componentgraph.cycle; + +import java.util.ArrayList; +import java.util.LinkedHashMap; +import java.util.List; +import java.util.Map; +import java.util.logging.Logger; +import java.util.stream.Collectors; + +import static com.yahoo.container.di.componentgraph.cycle.CycleFinder.State.BLACK; +import static com.yahoo.container.di.componentgraph.cycle.CycleFinder.State.GRAY; +import static com.yahoo.container.di.componentgraph.cycle.CycleFinder.State.WHITE; +import static com.yahoo.log.LogLevel.DEBUG; +import static java.util.Collections.singletonList; + + +/** + *

Applies the + * three-color algorithm + * to detect a cycle in a directed graph. If there are multiple cycles, this implementation only detects one + * of them and does not guarantee that the shortest cycle is found. + *

+ * + * @author gjoranv + */ +public class CycleFinder { + private static final Logger log = Logger.getLogger(CycleFinder.class.getName()); + + enum State { + WHITE, GRAY, BLACK; + } + + private final Graph graph; + + private Map colors; + + private List cycle; + + public CycleFinder(Graph graph) { + this.graph = graph; + } + + private void resetState() { + cycle = null; + colors = new LinkedHashMap<>(); + graph.getVertices().forEach(v -> colors.put(v, WHITE)); + } + + /** + * Returns a list of vertices constituting a cycle in the graph, or an empty + * list if no cycle was found. Only the first encountered cycle is returned. + */ + public List 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(DEBUG, "Cycle detected: " + cycle); + return cycle; + } + } + } + return new ArrayList<>(); + } + + private boolean visitDepthFirst(T vertex, List path) { + colors.put(vertex, GRAY); + log.log(DEBUG, "Vertex start " + vertex + " - colors: " + colors + " - path: " + path); + for (T adjacent : graph.getAdjacent(vertex)) { + path.add(adjacent); + if (colors.get(adjacent) == GRAY) { + cycle = removePathIntoCycle(path); + return true; + } + if (colors.get(adjacent) == WHITE && visitDepthFirst(adjacent, path)) { + return true; + } + path.remove(adjacent); + } + colors.put(vertex, BLACK); + log.log(DEBUG, "Vertex end " + vertex + " - colors: " + colors + " - path: " + path); + return false; + } + + private List removePathIntoCycle(List pathWithCycle) { + T cycleStart = pathWithCycle.get(pathWithCycle.size() - 1); + return pathWithCycle.stream() + .dropWhile(vertex -> ! vertex.equals(cycleStart)) + .collect(Collectors.toList()); + } + +} diff --git a/container-di/src/main/java/com/yahoo/container/di/componentgraph/cycle/Graph.java b/container-di/src/main/java/com/yahoo/container/di/componentgraph/cycle/Graph.java new file mode 100644 index 00000000000..ca1b791f642 --- /dev/null +++ b/container-di/src/main/java/com/yahoo/container/di/componentgraph/cycle/Graph.java @@ -0,0 +1,39 @@ +package com.yahoo.container.di.componentgraph.cycle; + +import java.util.LinkedHashMap; +import java.util.LinkedHashSet; +import java.util.Map; +import java.util.Set; + +/** + * Class representing a directed graph. + * + * @author gjoranv + */ +public class Graph { + + private final Map> adjMap = new LinkedHashMap<>(); + + public void edge(T from, T to) { + if (from == null || to == null) + throw new IllegalArgumentException("Null vertices are not allowed, edge: " + from + "->" + to); + + adjMap.computeIfAbsent(from, k -> new LinkedHashSet<>()).add(to); + adjMap.computeIfAbsent(to, k -> new LinkedHashSet<>()); + } + + Set getVertices() { + return adjMap.keySet(); + } + + /** + * Returns the outgoing edges of the given vertex. + */ + Set getAdjacent(T vertex) { + return adjMap.get(vertex); + } + + private void throwIfMissingVertex(T vertex) { + if (! adjMap.containsKey(vertex)) throw new IllegalArgumentException("No such vertex in the graph: " + vertex); + } +} diff --git a/container-di/src/test/java/com/yahoo/container/di/componentgraph/cycle/CycleFinderTest.java b/container-di/src/test/java/com/yahoo/container/di/componentgraph/cycle/CycleFinderTest.java new file mode 100644 index 00000000000..219aa6b5e8b --- /dev/null +++ b/container-di/src/test/java/com/yahoo/container/di/componentgraph/cycle/CycleFinderTest.java @@ -0,0 +1,87 @@ +/* + * Copyright 2019 Oath Inc. Licensed under the terms of the Apache 2.0 license. See LICENSE in the project root. + */ + +package com.yahoo.container.di.componentgraph.cycle; + +import org.junit.Test; + +import static com.yahoo.container.di.componentgraph.cycle.CycleFinderTest.Vertices.A; +import static com.yahoo.container.di.componentgraph.cycle.CycleFinderTest.Vertices.B; +import static com.yahoo.container.di.componentgraph.cycle.CycleFinderTest.Vertices.C; +import static com.yahoo.container.di.componentgraph.cycle.CycleFinderTest.Vertices.D; +import static org.hamcrest.Matchers.contains; +import static org.hamcrest.Matchers.empty; +import static org.junit.Assert.assertThat; + +/** + * @author gjoranv + */ +public class CycleFinderTest { + + enum Vertices {A, B, C, D} + + @Test + public void graph_without_cycles_returns_no_cycle() { + var graph = new Graph(); + 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(); + 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(); + 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(); + 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(); + 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(); + graph.edge(A, B); + + var cycleFinder = new CycleFinder<>(graph); + assertThat(cycleFinder.findCycle(), empty()); + assertThat(cycleFinder.findCycle(), empty()); + } + +} diff --git a/container-di/src/test/java/com/yahoo/container/di/componentgraph/cycle/GraphTest.java b/container-di/src/test/java/com/yahoo/container/di/componentgraph/cycle/GraphTest.java new file mode 100644 index 00000000000..588c1e30ffe --- /dev/null +++ b/container-di/src/test/java/com/yahoo/container/di/componentgraph/cycle/GraphTest.java @@ -0,0 +1,69 @@ +/* + * Copyright 2019 Oath Inc. Licensed under the terms of the Apache 2.0 license. See LICENSE in the project root. + */ + +package com.yahoo.container.di.componentgraph.cycle; + +import org.junit.Rule; +import org.junit.Test; +import org.junit.rules.ExpectedException; + +import static com.yahoo.container.di.componentgraph.cycle.GraphTest.Vertices.A; +import static com.yahoo.container.di.componentgraph.cycle.GraphTest.Vertices.B; +import static com.yahoo.container.di.componentgraph.cycle.GraphTest.Vertices.C; +import static org.hamcrest.CoreMatchers.is; +import static org.hamcrest.Matchers.contains; +import static org.hamcrest.Matchers.containsInAnyOrder; +import static org.hamcrest.Matchers.empty; +import static org.junit.Assert.assertThat; + +/** + * @author gjoranv + */ +public class GraphTest { + + enum Vertices {A, B, C} + + @Rule + public ExpectedException expectedException = ExpectedException.none(); + + @Test + public void vertices_and_edges_are_added_and_can_be_retrieved() { + var graph = new Graph(); + graph.edge(A, B); + graph.edge(B, C); + graph.edge(A, C); + + assertThat(graph.getVertices().size(), is(3)); + assertThat(graph.getAdjacent(A), containsInAnyOrder(B, C)); + assertThat(graph.getAdjacent(B), containsInAnyOrder(C)); + assertThat(graph.getAdjacent(C), empty()); + } + + @Test + public void null_vertices_are_not_allowed() { + var graph = new Graph(); + + expectedException.expect(IllegalArgumentException.class); + expectedException.expectMessage("Null vertices are not allowed"); + graph.edge(A, null); + } + + @Test + public void duplicate_edges_are_ignored() { + var graph = new Graph(); + graph.edge(A, B); + graph.edge(A, B); + + assertThat(graph.getAdjacent(A).size(), is(1)); + } + + @Test + public void self_edges_are_allowed() { + var graph = new Graph(); + graph.edge(A, A); + + assertThat(graph.getAdjacent(A), contains(A)); + } + +} -- cgit v1.2.3 From 220dd38e6c4e0c7e2c651ef77759920f844aaa12 Mon Sep 17 00:00:00 2001 From: gjoranv Date: Mon, 22 Jul 2019 11:36:06 +0200 Subject: Output cycle in the dependency graph. --- .../di/componentgraph/core/ComponentGraph.java | 24 ++++++++++++++++++++-- .../di/componentgraph/core/ComponentGraphTest.java | 1 + 2 files changed, 23 insertions(+), 2 deletions(-) diff --git a/container-di/src/main/java/com/yahoo/container/di/componentgraph/core/ComponentGraph.java b/container-di/src/main/java/com/yahoo/container/di/componentgraph/core/ComponentGraph.java index 4a0598d3436..cdd886b4672 100644 --- a/container-di/src/main/java/com/yahoo/container/di/componentgraph/core/ComponentGraph.java +++ b/container-di/src/main/java/com/yahoo/container/di/componentgraph/core/ComponentGraph.java @@ -13,6 +13,8 @@ import com.yahoo.component.ComponentId; import com.yahoo.component.provider.ComponentRegistry; import com.yahoo.config.ConfigInstance; import com.yahoo.container.di.componentgraph.Provider; +import com.yahoo.container.di.componentgraph.cycle.CycleFinder; +import com.yahoo.container.di.componentgraph.cycle.Graph; import com.yahoo.log.LogLevel; import com.yahoo.vespa.config.ConfigKey; import net.jcip.annotations.NotThreadSafe; @@ -372,13 +374,19 @@ public class ComponentGraph { /** * The returned list is the nodes from the graph bottom-up. * + * For each iteration, the algorithm finds the components that are not "wanted by" any other component, + * and prepends those components into the resulting 'sorted' list. Hence, the first element in the returned + * list is the component that is directly or indirectly wanted by "most" other components. + * * @return A list where a earlier than b in the list implies that there is no path from a to b */ private static List topologicalSort(Collection nodes) { Map numIncoming = new HashMap<>(); nodes.forEach( - node -> node.usedComponents().forEach(injectedNode -> numIncoming.merge(injectedNode.componentId(), 1, (a, b) -> a + b))); + node -> node.usedComponents().forEach( + injectedNode -> numIncoming.merge(injectedNode.componentId(), 1, (a, b) -> a + b))); + LinkedList sorted = new LinkedList<>(); List unsorted = new ArrayList<>(nodes); @@ -394,7 +402,7 @@ public class ComponentGraph { }); if (ready.isEmpty()) { - throw new IllegalStateException("There is a cycle in the component injection graph."); + throw new IllegalStateException("There is a cycle in the component injection graph: " + findCycle(notReady)); } ready.forEach(node -> node.usedComponents() @@ -404,4 +412,16 @@ public class ComponentGraph { } return sorted; } + + private static List findCycle(List nodes) { + var cyclicGraph = new Graph(); + for (var node : nodes) { + for (var adjacent : node.usedComponents()) { + cyclicGraph.edge(node.componentId().stringValue(), + adjacent.componentId().stringValue()); + } + } + return new CycleFinder<>(cyclicGraph).findCycle(); + } + } diff --git a/container-di/src/test/java/com/yahoo/container/di/componentgraph/core/ComponentGraphTest.java b/container-di/src/test/java/com/yahoo/container/di/componentgraph/core/ComponentGraphTest.java index a5934bcf098..8d323233ef5 100644 --- a/container-di/src/test/java/com/yahoo/container/di/componentgraph/core/ComponentGraphTest.java +++ b/container-di/src/test/java/com/yahoo/container/di/componentgraph/core/ComponentGraphTest.java @@ -323,6 +323,7 @@ public class ComponentGraphTest { fail("Cycle exception expected."); } catch (Throwable e) { assertThat(e.getMessage(), containsString("cycle")); + assertThat(e.getMessage(), containsString("ComponentCausingCycle")); } } -- cgit v1.2.3 From b3a7c34db491d3769daa7ad27f66f10768af6dfa Mon Sep 17 00:00:00 2001 From: gjoranv Date: Mon, 22 Jul 2019 14:39:33 +0200 Subject: Add missing copyright header. --- .../java/com/yahoo/container/di/componentgraph/cycle/CycleFinder.java | 1 + .../main/java/com/yahoo/container/di/componentgraph/cycle/Graph.java | 4 ++++ 2 files changed, 5 insertions(+) diff --git a/container-di/src/main/java/com/yahoo/container/di/componentgraph/cycle/CycleFinder.java b/container-di/src/main/java/com/yahoo/container/di/componentgraph/cycle/CycleFinder.java index 14d64dd1863..3b29fa0a04f 100644 --- a/container-di/src/main/java/com/yahoo/container/di/componentgraph/cycle/CycleFinder.java +++ b/container-di/src/main/java/com/yahoo/container/di/componentgraph/cycle/CycleFinder.java @@ -1,6 +1,7 @@ /* * Copyright 2019 Oath Inc. Licensed under the terms of the Apache 2.0 license. See LICENSE in the project root. */ + package com.yahoo.container.di.componentgraph.cycle; import java.util.ArrayList; diff --git a/container-di/src/main/java/com/yahoo/container/di/componentgraph/cycle/Graph.java b/container-di/src/main/java/com/yahoo/container/di/componentgraph/cycle/Graph.java index ca1b791f642..e1b110d51ee 100644 --- a/container-di/src/main/java/com/yahoo/container/di/componentgraph/cycle/Graph.java +++ b/container-di/src/main/java/com/yahoo/container/di/componentgraph/cycle/Graph.java @@ -1,3 +1,7 @@ +/* + * Copyright 2019 Oath Inc. Licensed under the terms of the Apache 2.0 license. See LICENSE in the project root. + */ + package com.yahoo.container.di.componentgraph.cycle; import java.util.LinkedHashMap; -- cgit v1.2.3