You are viewing a plain text version of this content. The canonical link for it is here.
Posted to commits@jena.apache.org by an...@apache.org on 2012/04/25 20:16:15 UTC
svn commit: r1330462 - in /incubator/jena/Jena2/ARQ/trunk/src:
main/java/com/hp/hpl/jena/sparql/path/eval/
test/java/com/hp/hpl/jena/sparql/path/
Author: andy
Date: Wed Apr 25 18:16:15 2012
New Revision: 1330462
URL: http://svn.apache.org/viewvc?rev=1330462&view=rev
Log:
Implement latest [April 2012] SPARQL semantics for property paths (which happen to the original semantics of ARQ).
Modified:
incubator/jena/Jena2/ARQ/trunk/src/main/java/com/hp/hpl/jena/sparql/path/eval/PathEngine.java
incubator/jena/Jena2/ARQ/trunk/src/main/java/com/hp/hpl/jena/sparql/path/eval/PathEngine1.java
incubator/jena/Jena2/ARQ/trunk/src/main/java/com/hp/hpl/jena/sparql/path/eval/PathEngineN.java
incubator/jena/Jena2/ARQ/trunk/src/main/java/com/hp/hpl/jena/sparql/path/eval/PathEngineSPARQL.java
incubator/jena/Jena2/ARQ/trunk/src/main/java/com/hp/hpl/jena/sparql/path/eval/PathEval.java
incubator/jena/Jena2/ARQ/trunk/src/main/java/com/hp/hpl/jena/sparql/path/eval/PathEvaluator.java
incubator/jena/Jena2/ARQ/trunk/src/test/java/com/hp/hpl/jena/sparql/path/TestPath.java
Modified: incubator/jena/Jena2/ARQ/trunk/src/main/java/com/hp/hpl/jena/sparql/path/eval/PathEngine.java
URL: http://svn.apache.org/viewvc/incubator/jena/Jena2/ARQ/trunk/src/main/java/com/hp/hpl/jena/sparql/path/eval/PathEngine.java?rev=1330462&r1=1330461&r2=1330462&view=diff
==============================================================================
--- incubator/jena/Jena2/ARQ/trunk/src/main/java/com/hp/hpl/jena/sparql/path/eval/PathEngine.java (original)
+++ incubator/jena/Jena2/ARQ/trunk/src/main/java/com/hp/hpl/jena/sparql/path/eval/PathEngine.java Wed Apr 25 18:16:15 2012
@@ -33,11 +33,22 @@ import com.hp.hpl.jena.sparql.path.Path
import com.hp.hpl.jena.sparql.path.eval.PathEvaluator.FilterExclude ;
abstract public class PathEngine {
-
- protected abstract void doNegatedPropertySet(P_NegPropSet pathNotOneOf, Node node, Collection<Node> output) ;
-
- protected abstract void doZeroOrOne(Path pathStep, Node node, Collection<Node> output) ;
+ protected final Iter<Node> eval(Graph graph, Path path, Node node)
+ {
+ return PathEval.eval$(graph, node, path, this) ;
+ }
+
+ protected final void eval(Graph graph, Path path, Node node, Collection<Node> output)
+ {
+ PathEval.eval$(graph, node, path, this, output) ;
+ }
+
+ protected abstract void flipDirection() ;
+ protected abstract boolean direction() ;
+
+ protected abstract Collection<Node> collector() ;
+
// protected abstract void doZero(Path pathStep, Node node, Collection<Node> output) ;
// protected abstract void doOne(Path pathStep, Node node, Collection<Node> output) ;
@@ -56,39 +67,41 @@ abstract public class PathEngine {
Iter<Triple> iter1 = Iter.iter(graph.find(Node.ANY, property, node)) ;
iter2 = iter1.map(PathEngine.selectSubject) ;
}
-
+
return iter2 ;
}
- protected final Iter<Node> eval(Graph graph, Path path, Node node)
- {
- return PathEval.eval$(graph, node, path, this) ;
- }
-
- protected final void eval(Graph graph, Path path, Node node, Collection<Node> output)
- {
- PathEval.eval$(graph, node, path, this, output) ;
- }
-
- protected abstract void flipDirection() ;
- protected abstract boolean direction() ;
-
- protected abstract Collection<Node> collector() ;
-
- protected abstract void doOneOrMore(Path pathStep, Node node, Collection<Node> output) ;
+ protected abstract void doSeq(Path pathStepLeft, Path pathStepRight, Node node, Collection<Node> output) ;
+
+ protected abstract void doAlt(Path pathStepLeft, Path pathStepRight, Node node, Collection<Node> output) ;
+ // path*
protected abstract void doZeroOrMore(Path pathStep, Node node, Collection<Node> output) ;
- protected abstract void doFixedLengthPath(Path pathStep, Node node, long fixedLength, Collection<Node> output) ;
+ // path+
+ protected abstract void doOneOrMore(Path pathStep, Node node, Collection<Node> output) ;
- protected abstract void doMultiLengthPath(Path pathStep, Node node, long min, long max, Collection<Node> output) ;
+ // path?
+ protected abstract void doZeroOrOne(Path pathStep, Node node, Collection<Node> output) ;
- protected abstract void doAlt(Path pathStepLeft, Path pathStepRight, Node node, Collection<Node> output) ;
+ protected abstract void doNegatedPropertySet(P_NegPropSet pathNotOneOf, Node node, Collection<Node> output) ;
- protected abstract void doSeq(Path pathStepLeft, Path pathStepRight, Node node, Collection<Node> output) ;
+ // path{*} : default implementation
+ protected void doZeroOrMoreN(Path pathStep, Node node, Collection<Node> output)
+ { doZeroOrMore(pathStep, node, output) ; }
+
+ // path{+} : default implementation
+ protected void doOneOrMoreN(Path pathStep, Node node, Collection<Node> output)
+ { doOneOrMore(pathStep, node, output) ; }
protected abstract void doZero(Path path, Node node, Collection<Node> output) ;
+ // {N,M} and variations
+
+ protected abstract void doFixedLengthPath(Path pathStep, Node node, long fixedLength, Collection<Node> output) ;
+
+ protected abstract void doMultiLengthPath(Path pathStep, Node node, long min, long max, Collection<Node> output) ;
+
protected final void fill(Iterator<Node> iter, Collection<Node> output)
{
for ( ; iter.hasNext() ; )
Modified: incubator/jena/Jena2/ARQ/trunk/src/main/java/com/hp/hpl/jena/sparql/path/eval/PathEngine1.java
URL: http://svn.apache.org/viewvc/incubator/jena/Jena2/ARQ/trunk/src/main/java/com/hp/hpl/jena/sparql/path/eval/PathEngine1.java?rev=1330462&r1=1330461&r2=1330462&view=diff
==============================================================================
--- incubator/jena/Jena2/ARQ/trunk/src/main/java/com/hp/hpl/jena/sparql/path/eval/PathEngine1.java (original)
+++ incubator/jena/Jena2/ARQ/trunk/src/main/java/com/hp/hpl/jena/sparql/path/eval/PathEngine1.java Wed Apr 25 18:16:15 2012
@@ -59,6 +59,32 @@ final class PathEngine1 extends PathEngi
protected boolean direction()
{ return forwardMode ; }
+ @Override
+ protected void doAlt(Path pathStepLeft, Path pathStepRight, Node node, Collection<Node> output)
+ {
+ // Must be duplicate supressing.
+ Collection<Node> nodes = new HashSet<Node>() ;
+ // Insert directly.
+ eval(graph, pathStepLeft, node, nodes) ;
+ // Need to reduce/check other side.
+ eval(graph, pathStepRight, node, nodes) ;
+ output.addAll(nodes) ;
+ }
+
+ @Override
+ protected void doSeq(Path pathStepLeft, Path pathStepRight, Node node, Collection<Node> output)
+ {
+ Path part1 = forwardMode ? pathStepLeft : pathStepRight ;
+ Path part2 = forwardMode ? pathStepRight : pathStepLeft ;
+
+ Collection<Node> nodes = collector() ;
+ eval(graph, part1, node, nodes) ;
+ Collection<Node> nodes2 = new HashSet<Node>() ;
+ for ( Node n : nodes )
+ eval(graph, part2, n, nodes2) ;
+ output.addAll(nodes2) ;
+ }
+
// Can use .addAll if collector is set-like.
private static void fillUnique(Iterator<Node> nodes, Collection<Node> acc)
{
@@ -238,30 +264,4 @@ final class PathEngine1 extends PathEngi
if ( !output.contains(node) )
output.add(node) ;
}
-
- @Override
- protected void doAlt(Path pathStepLeft, Path pathStepRight, Node node, Collection<Node> output)
- {
- // Must be duplicate supressing.
- Collection<Node> nodes = new HashSet<Node>() ;
- // Insert directly.
- eval(graph, pathStepLeft, node, nodes) ;
- // Need to reduce/check other side.
- eval(graph, pathStepRight, node, nodes) ;
- output.addAll(nodes) ;
- }
-
- @Override
- protected void doSeq(Path pathStepLeft, Path pathStepRight, Node node, Collection<Node> output)
- {
- Path part1 = forwardMode ? pathStepLeft : pathStepRight ;
- Path part2 = forwardMode ? pathStepRight : pathStepLeft ;
-
- Collection<Node> nodes = collector() ;
- eval(graph, part1, node, nodes) ;
- Collection<Node> nodes2 = new HashSet<Node>() ;
- for ( Node n : nodes )
- eval(graph, part2, n, nodes2) ;
- output.addAll(nodes2) ;
- }
}
Modified: incubator/jena/Jena2/ARQ/trunk/src/main/java/com/hp/hpl/jena/sparql/path/eval/PathEngineN.java
URL: http://svn.apache.org/viewvc/incubator/jena/Jena2/ARQ/trunk/src/main/java/com/hp/hpl/jena/sparql/path/eval/PathEngineN.java?rev=1330462&r1=1330461&r2=1330462&view=diff
==============================================================================
--- incubator/jena/Jena2/ARQ/trunk/src/main/java/com/hp/hpl/jena/sparql/path/eval/PathEngineN.java (original)
+++ incubator/jena/Jena2/ARQ/trunk/src/main/java/com/hp/hpl/jena/sparql/path/eval/PathEngineN.java Wed Apr 25 18:16:15 2012
@@ -202,7 +202,6 @@ final class PathEngineN extends PathEngi
@Override
protected void doZeroOrMore(Path path, Node node, Collection<Node> output)
{
- //Deque<Node> visited = new ArrayDeque<Node>() ;
Set<Node> visited = new HashSet<Node>() ;
ALP(node, path, visited, output) ;
}
Modified: incubator/jena/Jena2/ARQ/trunk/src/main/java/com/hp/hpl/jena/sparql/path/eval/PathEngineSPARQL.java
URL: http://svn.apache.org/viewvc/incubator/jena/Jena2/ARQ/trunk/src/main/java/com/hp/hpl/jena/sparql/path/eval/PathEngineSPARQL.java?rev=1330462&r1=1330461&r2=1330462&view=diff
==============================================================================
--- incubator/jena/Jena2/ARQ/trunk/src/main/java/com/hp/hpl/jena/sparql/path/eval/PathEngineSPARQL.java (original)
+++ incubator/jena/Jena2/ARQ/trunk/src/main/java/com/hp/hpl/jena/sparql/path/eval/PathEngineSPARQL.java Wed Apr 25 18:16:15 2012
@@ -18,10 +18,7 @@
package com.hp.hpl.jena.sparql.path.eval;
-import java.util.ArrayList ;
-import java.util.Collection ;
-import java.util.Iterator ;
-import java.util.LinkedList ;
+import java.util.* ;
import org.openjena.atlas.iterator.Iter ;
@@ -39,7 +36,7 @@ public class PathEngineSPARQL extends Pa
private final Graph graph ;
private boolean forwardMode ;
- private PathEngineSPARQL(Graph graph, boolean forward)
+ public PathEngineSPARQL(Graph graph, boolean forward)
{
this.graph = graph ;
this.forwardMode = forward ;
@@ -96,7 +93,7 @@ public class PathEngineSPARQL extends Pa
{
// Reuse "output"
Collection<Node> visited = new LinkedList<Node>() ; //new HashSet<Node>() ;
- ALP1(graph, forwardMode, 0, -1, node, pathStep, visited) ;
+ ALP_1(graph, forwardMode, 0, -1, node, pathStep, visited) ;
output.addAll(visited) ;
}
@@ -110,12 +107,19 @@ public class PathEngineSPARQL extends Pa
for ( ; iter1.hasNext() ; )
{
Node n1 = iter1.next();
- ALP1(graph, forwardMode, 0, -1, n1, pathStep, visited) ;
+ ALP_1(graph, forwardMode, 0, -1, n1, pathStep, visited) ;
}
output.addAll(visited) ;
}
+
+ @Override
+ protected void doZero(Path path, Node node, Collection<Node> output)
+ {
+ // Not SPARQL
+ output.add(node) ;
+ }
- private void ALP1(Graph graph, boolean forwardMode, int stepCount, int maxStepCount, Node node, Path path, Collection<Node> visited)
+ private void ALP_1(Graph graph, boolean forwardMode, int stepCount, int maxStepCount, Node node, Path path, Collection<Node> visited)
{
if ( false ) System.out.printf("ALP1 node=%s\n visited=%s\n output=%s\n", node, visited) ;
if ( maxStepCount >=0 && stepCount > maxStepCount ) return ;
@@ -129,15 +133,51 @@ public class PathEngineSPARQL extends Pa
for ( ; iter1.hasNext() ; )
{
Node n1 = iter1.next();
- ALP1(graph, forwardMode, stepCount+1, maxStepCount, n1, path, visited) ;
+ ALP_1(graph, forwardMode, stepCount+1, maxStepCount, n1, path, visited) ;
}
}
@Override
- protected void doZero(Path path, Node node, Collection<Node> output)
+ protected void doZeroOrMoreN(Path pathStep, Node node, Collection<Node> output)
{
- // Not SPARQL
- output.add(node) ;
+ Set<Node> visited = new HashSet<Node>() ;
+ ALP_N(node, pathStep, visited, output) ;
+ }
+
+ @Override
+ protected void doOneOrMoreN(Path pathStep, Node node, Collection<Node> output)
+ {
+ Set<Node> visited = new HashSet<Node>() ;
+ // Do one step without including.
+ Iterator<Node> iter1 = eval(graph, pathStep, node) ;
+ for ( ; iter1.hasNext() ; )
+ {
+ Node n1 = iter1.next();
+ ALP_N(n1, pathStep, visited, output) ;
+ }
+ }
+
+ // This is the worker function for path{*}
+ private void ALP_N(Node node, Path path, Collection<Node> visited, Collection<Node> output)
+ {
+ if ( visited.contains(node) ) return ;
+
+ // If output is a set, then no point going on if node has been added to the results.
+ // If output includes duplicates, more solutions are generated
+ // "visited" is nodes on this path (see the matching .remove).
+ if ( ! output.add(node) )
+ return ;
+
+ visited.add(node) ;
+
+ Iterator<Node> iter1 = eval(graph, path, node) ;
+ // For each step, add to results and recurse.
+ for ( ; iter1.hasNext() ; )
+ {
+ Node n1 = iter1.next();
+ ALP_N(n1, path, visited, output) ;
+ }
+ visited.remove(node) ;
}
@Override
Modified: incubator/jena/Jena2/ARQ/trunk/src/main/java/com/hp/hpl/jena/sparql/path/eval/PathEval.java
URL: http://svn.apache.org/viewvc/incubator/jena/Jena2/ARQ/trunk/src/main/java/com/hp/hpl/jena/sparql/path/eval/PathEval.java?rev=1330462&r1=1330461&r2=1330462&view=diff
==============================================================================
--- incubator/jena/Jena2/ARQ/trunk/src/main/java/com/hp/hpl/jena/sparql/path/eval/PathEval.java (original)
+++ incubator/jena/Jena2/ARQ/trunk/src/main/java/com/hp/hpl/jena/sparql/path/eval/PathEval.java Wed Apr 25 18:16:15 2012
@@ -35,15 +35,15 @@ public class PathEval
/** Evaluate a path : SPARQL semantics */
static public Iterator<Node> eval(Graph graph, Node node, Path path)
{
- //return eval$(graph, node, path, new PathEngineSPARQL(graph, true)) ;
- return eval$(graph, node, path, new PathEngineN(graph, true)) ;
+ return eval$(graph, node, path, new PathEngineSPARQL(graph, true)) ;
+ //return eval$(graph, node, path, new PathEngineN(graph, true)) ;
}
/** Evaluate a path */
static public Iterator<Node> evalReverse(Graph graph, Node node, Path path)
{
- //return eval$(graph, node, path, new PathEngineSPARQL(graph, false)) ;
- return eval$(graph, node, path, new PathEngineN(graph, false)) ;
+ return eval$(graph, node, path, new PathEngineSPARQL(graph, false)) ;
+ //return eval$(graph, node, path, new PathEngineN(graph, false)) ;
}
Modified: incubator/jena/Jena2/ARQ/trunk/src/main/java/com/hp/hpl/jena/sparql/path/eval/PathEvaluator.java
URL: http://svn.apache.org/viewvc/incubator/jena/Jena2/ARQ/trunk/src/main/java/com/hp/hpl/jena/sparql/path/eval/PathEvaluator.java?rev=1330462&r1=1330461&r2=1330462&view=diff
==============================================================================
--- incubator/jena/Jena2/ARQ/trunk/src/main/java/com/hp/hpl/jena/sparql/path/eval/PathEvaluator.java (original)
+++ incubator/jena/Jena2/ARQ/trunk/src/main/java/com/hp/hpl/jena/sparql/path/eval/PathEvaluator.java Wed Apr 25 18:16:15 2012
@@ -99,12 +99,12 @@ final class PathEvaluator implements Pat
if ( pathMod.isZeroOrMore() )
{
// :p{0,}
- engine.doOneOrMore(pathMod.getSubPath(), node, output) ;
+ engine.doOneOrMoreN(pathMod.getSubPath(), node, output) ;
return ;
}
if ( pathMod.isOneOrMore() )
{
- engine.doOneOrMore(pathMod.getSubPath(), node, output) ;
+ engine.doOneOrMoreN(pathMod.getSubPath(), node, output) ;
return ;
}
@@ -127,61 +127,34 @@ final class PathEvaluator implements Pat
@Override
public void visit(P_ZeroOrOne path)
{
- //WORK
engine.doZeroOrOne(path.getSubPath(), node, output) ;
}
@Override
public void visit(P_ZeroOrMore1 path)
{
- // Regardless of engine, do distinct.
- PathEngine engine2 = engine ;
- engine = new PathEngine1(graph, engine.direction()) ;
engine.doZeroOrMore(path.getSubPath(), node, output) ;
- engine = engine2 ;
}
@Override
public void visit(P_ZeroOrMoreN path)
{
- // TEMP: Do as engine.
- engine.doZeroOrMore(path.getSubPath(), node, output) ;
-
-// // Regardless of engine, do counting.
-// PathEngine engine2 = engine ;
-// engine = new PathEngineN(graph, engine.direction()) ;
-// engine.doZeroOrMore(path.getSubPath(), node, output) ;
-// engine = engine2 ;
+ engine.doZeroOrMoreN(path.getSubPath(), node, output) ;
}
@Override
public void visit(P_OneOrMore1 path)
{
- // Regardless of engine, do distinct.
- PathEngine engine2 = engine ;
- engine = new PathEngine1(graph, engine.direction()) ;
engine.doOneOrMore(path.getSubPath(), node, output) ;
- engine = engine2 ;
}
@Override
public void visit(P_OneOrMoreN path)
{
- // TEMP Do as engine.
- engine.doOneOrMore(path.getSubPath(), node, output) ;
-
-// PathEngine engine2 = engine ;
-// engine = new PathEngineN(graph, engine.direction()) ;
-// engine.doOneOrMore(path.getSubPath(), node, output) ;
-// engine = engine2 ;
+ engine.doOneOrMoreN(path.getSubPath(), node, output) ;
}
-
-// protected abstract void doZero(Path pathStep, Node node, Collection<Node> output) ;
-// protected abstract void doOne(Path pathStep, Node node, Collection<Node> output) ;
-
-
@Override
public void visit(P_Alt pathAlt)
{
Modified: incubator/jena/Jena2/ARQ/trunk/src/test/java/com/hp/hpl/jena/sparql/path/TestPath.java
URL: http://svn.apache.org/viewvc/incubator/jena/Jena2/ARQ/trunk/src/test/java/com/hp/hpl/jena/sparql/path/TestPath.java?rev=1330462&r1=1330461&r2=1330462&view=diff
==============================================================================
--- incubator/jena/Jena2/ARQ/trunk/src/test/java/com/hp/hpl/jena/sparql/path/TestPath.java (original)
+++ incubator/jena/Jena2/ARQ/trunk/src/test/java/com/hp/hpl/jena/sparql/path/TestPath.java Wed Apr 25 18:16:15 2012
@@ -194,7 +194,6 @@ public class TestPath
assertEquals(p1, p2) ;
}
-
@Test public void path_01() { test(graph1, n1, ":p", n2) ; }
@Test public void path_02() { test(graph1, n1, ":p{0}", n1) ; }
@Test public void path_03() { test(graph1, n1, ":p{1}", n2) ; }
@@ -211,13 +210,8 @@ public class TestPath
@Test public void path_14() { test(graph1, n2, "^:p", n1) ; }
@Test public void path_15() { test(graph1, n2, "^:p^:p" ) ; }
@Test public void path_16() { test(graph1, n4, "^:p^:p", n2) ; }
-
-
-
-
@Test public void path_17() { test(graph1, n4, "^(:p/:p)", n2) ; }
-
@Test public void path_18() { test(graph1, n2, "^:p/:p", n2) ; }
@Test public void path_20() { test(graph2, n1, ":p", n2,n3) ; }
@@ -230,11 +224,17 @@ public class TestPath
@Test public void path_30() { test(graph1, n1, ":p*", n1,n2,n3,n4) ; }
@Test public void path_31() { test(graph2, n1, ":p*", n1,n2,n3) ; }
- @Test public void path_32() { test(graph3, n1, ":p{*}", n1,n2,n3,n4,n4) ; }
+
+// // A DAG, one property
+// graph3.add(new Triple(n1, p, n2)) ;
+// graph3.add(new Triple(n1, p, n3)) ;
+// graph3.add(new Triple(n2, p, n4)) ;
+// graph3.add(new Triple(n3, p, n4)) ;
+
+
+ @Test public void path_32() { test(graph3, n1, ":p{*}", n1,n2,n3,n4,n4) ; }
@Test public void path_33() { test(graph3, n1, ":p*", n1,n2,n3,n4) ; }
@Test public void path_34() { test(graph3, n1, ":p+", n2,n3,n4) ; }
- @Test public void path_35() { test(graph3, n1, ":p{+}", n2,n3,n4,n4) ; }
-
// TODO Shortest path is not implemented yet. These also need to be verified that they are correct.
@Ignore @Test public void path_40() { test(graph1, n1, "shortest(:p*)", n1) ; }
@@ -268,7 +268,7 @@ public class TestPath
Assert.assertTrue("expected:"+expected+", got:"+results, sameUnorder(expected, results)) ;
}
- private static boolean sameUnorder(List<Node> expected, List<Node> results)
+ static boolean sameUnorder(List<Node> expected, List<Node> results)
{
// Copy - this is modified.
List<Node> x = new ArrayList<Node>(results) ;