This is an automated email from the ASF dual-hosted git repository.
mthl pushed a commit to branch trunk
in repository https://gitbox.apache.org/repos/asf/ofbiz-framework.git
commit 7044af8a6fe9261f4fc5806fd6fefd9e537ee5be
Author: Samuel Trégouët <samuel.trego...@nereide.fr>
AuthorDate: Wed Oct 30 17:21:40 2019 +0100
Implemented: Add a generic directed graph utilitary class
(OFBIZ-11275)
---
build.gradle | 2 +
config/checkstyle/checkstyle.xml | 5 +-
.../java/org/apache/ofbiz/base/util/Digraph.java | 118 +++++++++++++++++++++
.../org/apache/ofbiz/base/util/DiGraphTest.java | 93 ++++++++++++++++
4 files changed, 217 insertions(+), 1 deletion(-)
diff --git a/build.gradle b/build.gradle
index 1f14f95..a4d9466 100644
--- a/build.gradle
+++ b/build.gradle
@@ -207,6 +207,8 @@ dependencies {
testImplementation 'org.hamcrest:hamcrest:2.1'
testImplementation 'org.hamcrest:hamcrest-library:2.1' // Enable junit4 to
not depend on hamcrest-1.3
testImplementation 'org.mockito:mockito-core:3.1.0'
+ testImplementation 'com.pholser:junit-quickcheck-core:0.9'
+ testImplementation 'com.pholser:junit-quickcheck-generators:0.9'
runtimeOnly 'javax.xml.soap:javax.xml.soap-api:1.4.0'
runtimeOnly 'de.odysseus.juel:juel-spi:2.2.7'
runtimeOnly 'net.sf.barcode4j:barcode4j-fop-ext:2.1'
diff --git a/config/checkstyle/checkstyle.xml b/config/checkstyle/checkstyle.xml
index 3e3606b..426c5c3 100644
--- a/config/checkstyle/checkstyle.xml
+++ b/config/checkstyle/checkstyle.xml
@@ -109,7 +109,10 @@ under the License.
<module name="SimplifyBooleanReturn"/>
<!-- Checks for class design -->
- <module name="DesignForExtension"/>
+ <module name="DesignForExtension">
+ <property name="ignoredAnnotations"
+ value="After, AfterClass, Before, BeforeClass, Test,
Property"/>
+ </module>
<module name="FinalClass"/>
<module name="HideUtilityClassConstructor"/>
<module name="InterfaceIsType"/>
diff --git
a/framework/base/src/main/java/org/apache/ofbiz/base/util/Digraph.java
b/framework/base/src/main/java/org/apache/ofbiz/base/util/Digraph.java
new file mode 100644
index 0000000..8314ef1
--- /dev/null
+++ b/framework/base/src/main/java/org/apache/ofbiz/base/util/Digraph.java
@@ -0,0 +1,118 @@
+/*
+ * Licensed to the Apache Software Foundation (ASF) under one
+ * or more contributor license agreements. See the NOTICE file
+ * distributed with this work for additional information
+ * regarding copyright ownership. The ASF licenses this file
+ * to you under the Apache License, Version 2.0 (the
+ * "License"); you may not use this file except in compliance
+ * with the License. You may obtain a copy of the License at
+ *
+ * http://www.apache.org/licenses/LICENSE-2.0
+ *
+ * Unless required by applicable law or agreed to in writing,
+ * software distributed under the License is distributed on an
+ * "AS IS" BASIS, WITHOUT WARRANTIES OR CONDITIONS OF ANY
+ * KIND, either express or implied. See the License for the
+ * specific language governing permissions and limitations
+ * under the License.
+ */
+package org.apache.ofbiz.base.util;
+
+import static java.util.stream.Collectors.toSet;
+
+import java.util.ArrayList;
+import java.util.Collection;
+import java.util.HashSet;
+import java.util.List;
+import java.util.Map;
+import java.util.Set;
+
+/**
+ * A basic directed graph utilitary.
+ * <p>
+ * A directed graph is a data structure consisting of nodes and arrows
connecting those nodes
+ * which are called <em>edges</em>. In a directed graph edges are ordered
pairs of respectively
+ * source and target nodes.
+ * <p>
+ * This implementation is adapted to small in-memory graphs.
+ *
+ * @param <T> the type of the nodes
+ * @see <a href="https://www.wikipedia.org/wiki/Directed_graph";>Directed
graph</a>
+ */
+public class Digraph<T> {
+ /** The map associating source nodes to their adjacent target nodes. */
+ private final Map<T, Collection<T>> edges;
+ /** The set of nodes */
+ private final Set<T> nodes;
+
+ /**
+ * Constructs a directed graph from a specification Map.
+ *
+ * @param spec the map defining a set of source nodes (keys) that are
linked to a collection
+ * of adjacent target nodes (values). Both keys and values
must not be {@code null}.
+ * @throws IllegalArgumentException when a target node is not present in
the sources nodes.
+ */
+ public Digraph(Map<T, Collection<T>> spec) throws IllegalArgumentException
{
+ this.edges = spec;
+ this.nodes = spec.keySet();
+ // Check that all adjacent nodes are present as keys in the map.
+ Set<T> undeclaredNodes = spec.values().stream()
+ .flatMap(Collection::stream)
+ .filter(child -> !nodes.contains(child))
+ .collect(toSet());
+ if (!undeclaredNodes.isEmpty()) {
+ String msg = String.format("%s nodes are not present in the
graph", undeclaredNodes);
+ throw new IllegalArgumentException(msg);
+ }
+ }
+
+ /**
+ * Sort nodes in a topological ordering assuming that this graph is
acyclic.
+ * <p>
+ * A graph without cycles is often called a <em>Directed Acyclic
Graph</em> (DAG).
+ *
+ * @return a linear ordering of nodes such for every edge in the graph its
target node
+ * is present before its source node.
+ * @throws IllegalStateException when this graph contains a cycle.
+ * @see <a
href="https://www.wikipedia.org/wiki/Topological_sorting";>topological
sorting</a>
+ * @see <a
href="https://www.wikipedia.org/wiki/Directed_acyclic_graph";>DAG</a>
+ */
+ public List<T> sort() throws IllegalStateException {
+ Set<T> permanents = new HashSet<>();
+ Set<T> temporaries = new HashSet<>();
+ List<T> result = new ArrayList<>();
+ for (T node : nodes) {
+ if (!permanents.contains(node)) {
+ visit(result, node, permanents, temporaries);
+ }
+ }
+ return result;
+ }
+
+ /**
+ * Traverses the graph using <em>Depth First Search</em> (DFS) to
construct a topological ordering.
+ *
+ * @param res the ordered list that we are building
+ * @param root the current node we are visiting
+ * @param permanents the nodes that have been successfully been visited
+ * @param temporaries the nodes that we have started to visit but might
contain cycles.
+ * @throws IllegalStateException when a cycle is found.
+ * @see #sort
+ * @see <a href="https://www.wikipedia.org/wiki/Depth-first_search";>Depth
Dirst Search</a>
+ */
+ private void visit(List<T> res, T root, Set<T> permanents, Set<T>
temporaries) throws IllegalStateException {
+ if (permanents.contains(root)) {
+ return;
+ } else if (temporaries.contains(root)) {
+ throw new IllegalStateException("A cycle has been found");
+ } else {
+ temporaries.add(root);
+ for (T next : edges.get(root)) {
+ visit(res, next, permanents, temporaries);
+ }
+ temporaries.remove(root);
+ permanents.add(root);
+ res.add(root);
+ }
+ }
+}
diff --git
a/framework/base/src/test/java/org/apache/ofbiz/base/util/DiGraphTest.java
b/framework/base/src/test/java/org/apache/ofbiz/base/util/DiGraphTest.java
new file mode 100644
index 0000000..de299cd
--- /dev/null
+++ b/framework/base/src/test/java/org/apache/ofbiz/base/util/DiGraphTest.java
@@ -0,0 +1,93 @@
+/*
+ * Licensed to the Apache Software Foundation (ASF) under one
+ * or more contributor license agreements. See the NOTICE file
+ * distributed with this work for additional information
+ * regarding copyright ownership. The ASF licenses this file
+ * to you under the Apache License, Version 2.0 (the
+ * "License"); you may not use this file except in compliance
+ * with the License. You may obtain a copy of the License at
+ *
+ * http://www.apache.org/licenses/LICENSE-2.0
+ *
+ * Unless required by applicable law or agreed to in writing,
+ * software distributed under the License is distributed on an
+ * "AS IS" BASIS, WITHOUT WARRANTIES OR CONDITIONS OF ANY
+ * KIND, either express or implied. See the License for the
+ * specific language governing permissions and limitations
+ * under the License.
+ */
+package org.apache.ofbiz.base.util;
+
+import static java.util.Arrays.asList;
+import static java.util.Collections.emptyList;
+import static org.hamcrest.MatcherAssert.assertThat;
+import static org.hamcrest.Matchers.in;
+import static org.hamcrest.Matchers.is;
+import static org.junit.Assume.assumeNoException;
+
+import java.util.ArrayList;
+import java.util.Collection;
+import java.util.List;
+import java.util.Map;
+
+import org.junit.Test;
+import org.junit.runner.RunWith;
+
+import com.pholser.junit.quickcheck.Property;
+import com.pholser.junit.quickcheck.runner.JUnitQuickcheck;
+
+@RunWith(JUnitQuickcheck.class)
+public class DiGraphTest {
+
+ @Test
+ public void testAcyclic() {
+ checkTopologicalOrder(UtilMisc.toMap(
+ "a", asList("b"),
+ "b", asList("c", "d"),
+ "c", emptyList(),
+ "d", emptyList(),
+ "z", emptyList(),
+ "f", emptyList(),
+ "e", asList("z", "b")));
+ }
+
+ @Test(expected = IllegalStateException.class)
+ public void testWithCycle() {
+ Map<String, Collection<String>> g = UtilMisc.toMap(
+ "a", asList("b"),
+ "b", asList("c"),
+ "c", asList("a"));
+ Digraph<String> dg = new Digraph<>(g);
+ dg.sort();
+ }
+
+ @Test
+ public void testMultipleParents() {
+ checkTopologicalOrder(UtilMisc.toMap(
+ "a", asList("b"),
+ "b", emptyList(),
+ "c", asList("b")));
+ }
+
+ @Property
+ public <T> void topologicalOrderProperty(Map<T, Collection<T>> graphspec) {
+ try {
+ checkTopologicalOrder(graphspec);
+ } catch (IllegalArgumentException e) {
+ assumeNoException("Invalid Graph", e);
+ } catch (IllegalStateException e) {
+ assumeNoException("Not a directed acyclic graph", e);
+ }
+ }
+
+ private static <T> void checkTopologicalOrder(Map<T, Collection<T>>
graphspec) {
+ Digraph<T> g = new Digraph<>(graphspec);
+ List<T> seen = new ArrayList<>();
+ for (T node : g.sort()) {
+ for (T adjacent : graphspec.get(node)) {
+ assertThat("child nodes are before their parents", adjacent,
is(in(seen)));
+ }
+ seen.add(node);
+ }
+ }
+}
