This is an automated email from the ASF dual-hosted git repository.
andy pushed a commit to branch main
in repository https://gitbox.apache.org/repos/asf/jena.git
The following commit(s) were added to refs/heads/main by this push:
new 286abc034f GH-2487: add StdModels#findShortestPath
286abc034f is described below
commit 286abc034f40c059ae81abc635d9196d13ca5100
Author: sszuev <[email protected]>
AuthorDate: Sun Jul 14 14:12:33 2024 +0300
GH-2487: add StdModels#findShortestPath
---
.../org/apache/jena/ontapi/utils/StdModels.java | 79 ++++++++
.../java/org/apache/jena/ontapi/StdModelsTest.java | 218 +++++++++++++++++++++
2 files changed, 297 insertions(+)
diff --git
a/jena-ontapi/src/main/java/org/apache/jena/ontapi/utils/StdModels.java
b/jena-ontapi/src/main/java/org/apache/jena/ontapi/utils/StdModels.java
index 5bd085396c..1bf7372f22 100644
--- a/jena-ontapi/src/main/java/org/apache/jena/ontapi/utils/StdModels.java
+++ b/jena-ontapi/src/main/java/org/apache/jena/ontapi/utils/StdModels.java
@@ -41,12 +41,19 @@ import org.apache.jena.sparql.util.NodeCmp;
import org.apache.jena.util.iterator.ExtendedIterator;
import org.apache.jena.vocabulary.RDF;
+import java.util.ArrayDeque;
+import java.util.ArrayList;
import java.util.Collection;
import java.util.Comparator;
+import java.util.Deque;
+import java.util.HashSet;
import java.util.Iterator;
+import java.util.List;
import java.util.Map;
+import java.util.Objects;
import java.util.Set;
import java.util.function.Function;
+import java.util.function.Predicate;
import java.util.stream.Collectors;
/**
@@ -233,4 +240,76 @@ public class StdModels {
if (p != null) return false;
return o == null;
}
+
+ /**
+ * Answers the shortest path from the {@code start} resource to the {@code
end} RDF node,
+ * such that every step on the path is accepted by the given filter.
+ * A path is a {@link List} of RDF {@link Statement}s.
+ * The subject of the first statement in the list is {@code start},
+ * and the object of the last statement in the list is {@code end}.
+ * <p>
+ * The {@code onPath} argument is a {@link Predicate}, which accepts a
statement and returns
+ * {@code true} if the statement should be considered to be on the path.
+ * To search for an unconstrained path, pass {@code ()->true} or {@code
null} as an argument.
+ * If there is more than one path of minimal length from {@code start} to
{@code end},
+ * this method returns an arbitrary one.
+ * The algorithm is blind breadth-first search, with loop detection.
+ *
+ * @param m the model in which we are seeking a path, not {@code null}
+ * @param start the starting resource, not {@code null}
+ * @param end the end, or goal, node, not {@code null}
+ * @param onPath a filter which determines whether a given statement can
be considered part of the path
+ * @return a path, consisting of a list of statements whose first subject
is {@code start},
+ * and whose last object is {@code end}, empty if no such path exists
+ */
+ public static List<Statement> findShortestPath(Model m, Resource start,
RDFNode end, Predicate<Statement> onPath) {
+ Objects.requireNonNull(m);
+ Objects.requireNonNull(start);
+ Objects.requireNonNull(end);
+ if (onPath == null) {
+ onPath = s -> true;
+ }
+ Deque<List<Statement>> bfs = new ArrayDeque<>();
+ Set<RDFNode> seen = new HashSet<>();
+
+ // initialize the paths
+ for (Iterator<Statement> i = m.listStatements(start, null, (RDFNode)
null).filterKeep(onPath); i.hasNext(); ) {
+ List<Statement> statements = new ArrayList<>();
+ statements.add(i.next());
+ bfs.add(statements);
+ }
+
+ // search
+ List<Statement> solution = new ArrayList<>();
+ while (solution.isEmpty() && !bfs.isEmpty()) {
+ List<Statement> candidate = bfs.removeFirst();
+
+ RDFNode terminalNode = candidate.isEmpty() ? null :
candidate.get(candidate.size() - 1).getObject();
+ if (terminalNode == null) {
+ continue;
+ }
+ if (end.equals(terminalNode)) {
+ solution = candidate;
+ continue;
+ }
+ if (!terminalNode.isResource()) {
+ continue;
+ }
+ Resource terminalResource = terminalNode.asResource();
+ seen.add(terminalResource);
+
+ // breadth-first expansion
+ for (Iterator<Statement> i =
terminalResource.listProperties().filterKeep(onPath); i.hasNext(); ) {
+ Statement link = i.next();
+
+ // no looping allowed, so we skip this link if it takes us to
a node we've seen
+ if (!seen.contains(link.getObject())) {
+ List<Statement> statements = new ArrayList<>(candidate);
+ statements.add(link);
+ bfs.add(statements);
+ }
+ }
+ }
+ return solution;
+ }
}
diff --git
a/jena-ontapi/src/test/java/org/apache/jena/ontapi/StdModelsTest.java
b/jena-ontapi/src/test/java/org/apache/jena/ontapi/StdModelsTest.java
new file mode 100644
index 0000000000..435a845fb6
--- /dev/null
+++ b/jena-ontapi/src/test/java/org/apache/jena/ontapi/StdModelsTest.java
@@ -0,0 +1,218 @@
+/*
+ * 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.jena.ontapi;
+
+import org.apache.jena.ontapi.utils.StdModels;
+import org.apache.jena.rdf.model.Model;
+import org.apache.jena.rdf.model.ModelFactory;
+import org.apache.jena.rdf.model.Property;
+import org.apache.jena.rdf.model.Resource;
+import org.apache.jena.rdf.model.ResourceFactory;
+import org.apache.jena.rdf.model.Statement;
+import org.apache.jena.vocabulary.OWL2;
+import org.junit.jupiter.api.Assertions;
+import org.junit.jupiter.api.Test;
+
+import java.util.List;
+import java.util.Set;
+
+public class StdModelsTest {
+ static final String NS = "http://example.com/test#";;
+
+ static Model createStdModelClassesABCDEFGThing() {
+ Model m = ModelFactory.createDefaultModel();
+ m.createResource(NS + "A", OWL2.Class);
+ m.createResource(NS + "B", OWL2.Class);
+ m.createResource(NS + "C", OWL2.Class);
+ m.createResource(NS + "D", OWL2.Class);
+ m.createResource(NS + "E", OWL2.Class);
+ m.createResource(NS + "F", OWL2.Class);
+ m.createResource(NS + "G", OWL2.Class);
+ m.createResource(OWL2.Thing.getURI(), OWL2.Class);
+ return m;
+ }
+
+ @Test
+ public void testShortestPath0() {
+ Model m = createStdModelClassesABCDEFGThing();
+ Resource A = m.getResource(NS + "A");
+ Resource B = m.getResource(NS + "B");
+
+ List<Statement> actual = StdModels.findShortestPath(m, A, B, s ->
true);
+ Assertions.assertTrue(actual.isEmpty());
+ }
+
+ @Test
+ public void testShortestPath1() {
+ Model m = createStdModelClassesABCDEFGThing();
+ Resource A = m.getResource(NS + "A");
+ Resource B = m.getResource(NS + "B");
+ Property p = m.createProperty(NS + "p");
+ A.addProperty(p, B);
+
+ List<Statement> actual = StdModels.findShortestPath(m, A, B, s ->
true);
+ Assertions.assertEquals(List.of(p),
actual.stream().map(Statement::getPredicate).toList());
+ }
+
+ @Test
+ public void testShortestPath2() {
+ Model m = createStdModelClassesABCDEFGThing();
+ Resource A = m.getResource(NS + "A");
+ Resource B = m.getResource(NS + "B");
+ Resource C = m.getResource(NS + "C");
+ Property p = m.createProperty(NS + "p");
+ A.addProperty(p, B);
+ B.addProperty(p, C);
+
+ List<Statement> actual = StdModels.findShortestPath(m, A, C, s ->
true);
+ Assertions.assertEquals(List.of(p, p),
actual.stream().map(Statement::getPredicate).toList());
+ }
+
+ @Test
+ public void testShortestPath3() {
+ Model m = createStdModelClassesABCDEFGThing();
+ Resource A = m.getResource(NS + "A");
+ Resource B = m.getResource(NS + "B");
+ Resource C = m.getResource(NS + "C");
+ Resource D = m.getResource(NS + "D");
+ Resource E = m.getResource(NS + "E");
+ Resource F = m.getResource(NS + "F");
+ Property p = m.createProperty(NS + "p");
+ // a - b - c
+ A.addProperty(p, B);
+ B.addProperty(p, C);
+
+ // a - d - e - f
+ A.addProperty(p, D);
+ D.addProperty(p, E);
+ E.addProperty(p, F);
+
+ List<Statement> actual1 = StdModels.findShortestPath(m, A, C, s ->
true);
+ Assertions.assertEquals(List.of(p, p),
actual1.stream().map(Statement::getPredicate).toList());
+
+ List<Statement> actual2 = StdModels.findShortestPath(m, A, F, s ->
true);
+ Assertions.assertEquals(List.of(p, p, p),
actual2.stream().map(Statement::getPredicate).toList());
+
+ List<Statement> actual3 = StdModels.findShortestPath(m, A, C, s ->
p.equals(s.getPredicate()));
+ Assertions.assertEquals(List.of(p, p),
actual3.stream().map(Statement::getPredicate).toList());
+
+ List<Statement> actual4 = StdModels.findShortestPath(m, A, F, s ->
p.equals(s.getPredicate()));
+ Assertions.assertEquals(List.of(p, p, p),
actual4.stream().map(Statement::getPredicate).toList());
+ }
+
+ @Test
+ public void testShortestPath4() {
+ Model m = createStdModelClassesABCDEFGThing();
+ Resource A = m.getResource(NS + "A");
+ Resource B = m.getResource(NS + "B");
+ Resource C = m.getResource(NS + "C");
+ Resource D = m.getResource(NS + "D");
+ Resource E = m.getResource(NS + "E");
+ Resource F = m.getResource(NS + "F");
+ Property p = m.createProperty(NS + "p");
+ Property q = m.createProperty(NS + "q");
+
+ // a - b - c by q
+ A.addProperty(q, B);
+ B.addProperty(q, C);
+
+ // a - d - e - f by p
+ A.addProperty(p, D);
+ D.addProperty(p, E);
+ E.addProperty(p, F);
+
+ List<Statement> actual1 = StdModels.findShortestPath(m, A, C, s ->
p.equals(s.getPredicate()));
+ Assertions.assertTrue(actual1.isEmpty());
+ List<Statement> actual2 = StdModels.findShortestPath(m, A, F, s ->
p.equals(s.getPredicate()));
+ Assertions.assertEquals(List.of(p, p, p),
actual2.stream().map(Statement::getPredicate).toList());
+ }
+
+ @Test
+ public void testShortestPath5() {
+ Model m = createStdModelClassesABCDEFGThing();
+ Resource A = m.getResource(NS + "A");
+ Property p = m.createProperty(NS + "p");
+ A.addProperty(p, A);
+
+ List<Statement> actual = StdModels.findShortestPath(m, A, A, s ->
true);
+ Assertions.assertEquals(List.of(p),
actual.stream().map(Statement::getPredicate).toList());
+ }
+
+ @Test
+ public void testShortestPath6() {
+ Model m = createStdModelClassesABCDEFGThing();
+ Resource A = m.getResource(NS + "A");
+ Resource B = m.getResource(NS + "B");
+ Resource C = m.getResource(NS + "C");
+ Property p = m.createProperty(NS + "p");
+ Property q = m.createProperty(NS + "q");
+ // a - b - a by q
+ // tests loop detection
+ A.addProperty(q, B);
+ B.addProperty(q, A);
+
+ List<Statement> actual = StdModels.findShortestPath(m, A, C, s ->
Set.of(p, q).contains(s.getPredicate()));
+ Assertions.assertTrue(actual.isEmpty());
+ }
+
+ @Test
+ public void testShortestPath7() {
+ Model m = createStdModelClassesABCDEFGThing();
+ Resource A = m.getResource(NS + "A");
+ Resource B = m.getResource(NS + "B");
+ Resource D = m.getResource(NS + "D");
+ Resource E = m.getResource(NS + "E");
+ Resource F = m.getResource(NS + "F");
+ Property p = m.createProperty(NS + "p");
+ Property q = m.createProperty(NS + "q");
+
+ // a - d - e - f by p and q
+ A.addProperty(p, D);
+ D.addProperty(q, E);
+ D.addProperty(q, B);
+ E.addProperty(p, F);
+
+ List<Statement> actual = StdModels.findShortestPath(m, A, F, s ->
Set.of(p, q).contains(s.getPredicate()));
+ Assertions.assertEquals(List.of(p, q, p),
actual.stream().map(Statement::getPredicate).toList());
+ }
+
+ @Test
+ public void testShortestPath8() {
+ Model m = createStdModelClassesABCDEFGThing();
+ Resource A = m.getResource(NS + "A");
+ Resource B = m.getResource(NS + "B");
+ Resource D = m.getResource(NS + "D");
+ Resource E = m.getResource(NS + "E");
+ Resource F = m.getResource(NS + "F");
+ Property p = m.createProperty(NS + "p");
+ Property q = m.createProperty(NS + "q");
+
+ // a - d - e - f by p and q
+ A.addProperty(p, D);
+ D.addProperty(q, E);
+ D.addProperty(q, "bluff");
+ D.addProperty(q, B);
+ E.addProperty(p, F);
+ F.addProperty(q, "arnie");
+
+ List<Statement> actual = StdModels.findShortestPath(m, A,
ResourceFactory.createPlainLiteral("arnie"),
+ s -> Set.of(p, q).contains(s.getPredicate()));
+ Assertions.assertEquals(List.of(p, q, p, q),
actual.stream().map(Statement::getPredicate).toList());
+ }
+}
