tinkerpop-commits mailing list archives

Site index · List index
Message view « Date » · « Thread »
Top « Date » · « Thread »
From ok...@apache.org
Subject incubator-tinkerpop git commit: GraphFilterStrategy was pretty easy to create. Its registered as a default GraphComputer TraveralStrategy, though we might want to make it computer specific given that TinkerGraphComputer is not efficient with filters give
Date Fri, 06 May 2016 22:05:25 GMT
Repository: incubator-tinkerpop
Updated Branches:
  refs/heads/TINKERPOP-1293 [created] edd2f96da


GraphFilterStrategy was pretty easy to create. Its registered as a default GraphComputer TraveralStrategy,
though we might want to make it computer specific given that TinkerGraphComputer is not efficient
with filters given everything is in-memory. Also, its a bit dirty -- would like to clean up
GraphFilter. I don't like the 'helper logic' in there.


Project: http://git-wip-us.apache.org/repos/asf/incubator-tinkerpop/repo
Commit: http://git-wip-us.apache.org/repos/asf/incubator-tinkerpop/commit/edd2f96d
Tree: http://git-wip-us.apache.org/repos/asf/incubator-tinkerpop/tree/edd2f96d
Diff: http://git-wip-us.apache.org/repos/asf/incubator-tinkerpop/diff/edd2f96d

Branch: refs/heads/TINKERPOP-1293
Commit: edd2f96da8a96f6b1ba4f499e3d6c573e4402977
Parents: bba8d67
Author: Marko A. Rodriguez <okrammarko@gmail.com>
Authored: Fri May 6 16:05:15 2016 -0600
Committer: Marko A. Rodriguez <okrammarko@gmail.com>
Committed: Fri May 6 16:05:15 2016 -0600

----------------------------------------------------------------------
 .../gremlin/process/computer/Computer.java      |  14 +-
 .../optimization/GraphFilterStrategy.java       | 141 +++++++++++++++++++
 .../process/traversal/TraversalStrategies.java  |   2 +
 .../process/computer/GraphFilterTest.java       |  52 +++++--
 .../optimization/GraphFilterStrategyTest.java   |  77 ++++++++++
 5 files changed, 274 insertions(+), 12 deletions(-)
----------------------------------------------------------------------


http://git-wip-us.apache.org/repos/asf/incubator-tinkerpop/blob/edd2f96d/gremlin-core/src/main/java/org/apache/tinkerpop/gremlin/process/computer/Computer.java
----------------------------------------------------------------------
diff --git a/gremlin-core/src/main/java/org/apache/tinkerpop/gremlin/process/computer/Computer.java
b/gremlin-core/src/main/java/org/apache/tinkerpop/gremlin/process/computer/Computer.java
index ce31d5d..8fca818 100644
--- a/gremlin-core/src/main/java/org/apache/tinkerpop/gremlin/process/computer/Computer.java
+++ b/gremlin-core/src/main/java/org/apache/tinkerpop/gremlin/process/computer/Computer.java
@@ -136,18 +136,26 @@ public final class Computer implements Function<Graph, GraphComputer>,
Serializa
         return this.graphComputerClass;
     }
 
-    public Map<String,Object> getConfiguration()  {
+    public Map<String, Object> getConfiguration() {
         return this.configuration;
     }
 
-    public Traversal<Vertex,Vertex> getVertices() {
+    public Traversal<Vertex, Vertex> getVertices() {
         return this.vertices;
     }
 
-    public Traversal<Vertex,Edge> getEdges() {
+    public Traversal<Vertex, Edge> getEdges() {
         return this.edges;
     }
 
+    public GraphComputer.Persist getPersist() {
+        return this.persist;
+    }
+
+    public GraphComputer.ResultGraph getResultGraph() {
+        return this.resultGraph;
+    }
+
     public int getWorkers() {
         return this.workers;
     }

http://git-wip-us.apache.org/repos/asf/incubator-tinkerpop/blob/edd2f96d/gremlin-core/src/main/java/org/apache/tinkerpop/gremlin/process/computer/traversal/strategy/optimization/GraphFilterStrategy.java
----------------------------------------------------------------------
diff --git a/gremlin-core/src/main/java/org/apache/tinkerpop/gremlin/process/computer/traversal/strategy/optimization/GraphFilterStrategy.java
b/gremlin-core/src/main/java/org/apache/tinkerpop/gremlin/process/computer/traversal/strategy/optimization/GraphFilterStrategy.java
new file mode 100644
index 0000000..eea33ed
--- /dev/null
+++ b/gremlin-core/src/main/java/org/apache/tinkerpop/gremlin/process/computer/traversal/strategy/optimization/GraphFilterStrategy.java
@@ -0,0 +1,141 @@
+/*
+ * 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.tinkerpop.gremlin.process.computer.traversal.strategy.optimization;
+
+import org.apache.tinkerpop.gremlin.process.computer.Computer;
+import org.apache.tinkerpop.gremlin.process.computer.GraphComputer;
+import org.apache.tinkerpop.gremlin.process.computer.traversal.step.map.TraversalVertexProgramStep;
+import org.apache.tinkerpop.gremlin.process.computer.traversal.step.map.VertexProgramStep;
+import org.apache.tinkerpop.gremlin.process.traversal.Traversal;
+import org.apache.tinkerpop.gremlin.process.traversal.TraversalStrategy;
+import org.apache.tinkerpop.gremlin.process.traversal.dsl.graph.__;
+import org.apache.tinkerpop.gremlin.process.traversal.step.map.GraphStep;
+import org.apache.tinkerpop.gremlin.process.traversal.step.map.VertexStep;
+import org.apache.tinkerpop.gremlin.process.traversal.strategy.AbstractTraversalStrategy;
+import org.apache.tinkerpop.gremlin.process.traversal.util.TraversalHelper;
+import org.apache.tinkerpop.gremlin.structure.Direction;
+import org.apache.tinkerpop.gremlin.structure.Edge;
+import org.apache.tinkerpop.gremlin.structure.Graph;
+import org.apache.tinkerpop.gremlin.structure.Vertex;
+import org.apache.tinkerpop.gremlin.structure.util.empty.EmptyGraph;
+
+import java.util.Collections;
+import java.util.HashMap;
+import java.util.HashSet;
+import java.util.Map;
+import java.util.Set;
+
+/**
+ * @author Marko A. Rodriguez (http://markorodriguez.com)
+ */
+public final class GraphFilterStrategy extends AbstractTraversalStrategy<TraversalStrategy.OptimizationStrategy>
implements TraversalStrategy.OptimizationStrategy {
+
+    private static final GraphFilterStrategy INSTANCE = new GraphFilterStrategy();
+
+    private GraphFilterStrategy() {
+    }
+
+    @Override
+    public void apply(final Traversal.Admin<?, ?> traversal) {
+        if (TraversalHelper.getStepsOfAssignableClass(VertexProgramStep.class, traversal).size()
> 1)
+            return;
+        final Graph graph = traversal.getGraph().orElse(EmptyGraph.instance()); // best guess
at what the graph will be as its dynamically determined
+        for (final TraversalVertexProgramStep step : TraversalHelper.getStepsOfClass(TraversalVertexProgramStep.class,
traversal)) {
+            final Traversal.Admin<?, ?> computerTraversal = step.generateProgram(graph).getTraversal().get().clone();
+            if (!computerTraversal.isLocked())
+                computerTraversal.applyStrategies();
+            final Computer computer = step.getComputer();
+            if (null == computer.getEdges() && !GraphComputer.Persist.EDGES.equals(computer.getPersist()))
{
+                final Traversal.Admin<Vertex, Edge> edgeFilter = getEdgeFilter(computerTraversal);
+                if (null != edgeFilter)
+                    step.setComputer(computer.edges(edgeFilter));
+            }
+        }
+    }
+
+    protected static Traversal.Admin<Vertex, Edge> getEdgeFilter(final Traversal.Admin<?,
?> traversal) {
+        if (traversal.getStartStep() instanceof GraphStep && ((GraphStep) traversal.getStartStep()).returnsEdge())
+            return null;
+        final Map<Direction, Set<String>> directionLabels = new HashMap<>();
+        final Set<String> outLabels = new HashSet<>();
+        final Set<String> inLabels = new HashSet<>();
+        final Set<String> bothLabels = new HashSet<>();
+        directionLabels.put(Direction.OUT, outLabels);
+        directionLabels.put(Direction.IN, inLabels);
+        directionLabels.put(Direction.BOTH, bothLabels);
+        TraversalHelper.getStepsOfAssignableClassRecursively(VertexStep.class, traversal).forEach(step
-> {
+            // in-edge traversals require the outgoing edges for attachement
+            final Direction direction = step.getDirection().equals(Direction.IN) &&
step.returnsEdge() ?
+                    Direction.BOTH :
+                    step.getDirection();
+            final String[] edgeLabels = step.getEdgeLabels();
+            Set<String> temp = directionLabels.get(direction);
+            if (edgeLabels.length == 0)
+                temp.add(null);
+            else
+                Collections.addAll(temp, edgeLabels);
+        });
+        for (final String label : outLabels) {
+            if (inLabels.contains(label)) {
+                if (null == label)
+                    bothLabels.clear();
+                if (!bothLabels.contains(null))
+                    bothLabels.add(label);
+            }
+        }
+        if (bothLabels.contains(null)) {
+            outLabels.clear();
+            inLabels.clear();
+        }
+        for (final String label : bothLabels) {
+            outLabels.remove(label);
+            inLabels.remove(label);
+        }
+        // construct edges(...)
+        if (bothLabels.contains(null))
+            return null;
+        else if (outLabels.isEmpty() && inLabels.isEmpty() && bothLabels.isEmpty())
+            return __.<Vertex>bothE().limit(0).asAdmin();
+        else {
+            final String[] ins = inLabels.contains(null) ? new String[]{} : inLabels.toArray(new
String[inLabels.size()]);
+            final String[] outs = outLabels.contains(null) ? new String[]{} : outLabels.toArray(new
String[outLabels.size()]);
+            final String[] boths = bothLabels.contains(null) ? new String[]{} : bothLabels.toArray(new
String[bothLabels.size()]);
+
+            if (outLabels.isEmpty() && inLabels.isEmpty())
+                return __.<Vertex>bothE(boths).asAdmin();
+            else if (inLabels.isEmpty() && bothLabels.isEmpty())
+                return __.<Vertex>outE(outs).asAdmin();
+            else if (outLabels.isEmpty() && bothLabels.isEmpty())
+                return __.<Vertex>inE(ins).asAdmin();
+            else if (outLabels.isEmpty())
+                return __.<Vertex, Edge>union(__.inE(ins), __.bothE(boths)).asAdmin();
+            else if (inLabels.isEmpty())
+                return __.<Vertex, Edge>union(__.outE(outs), __.bothE(boths)).asAdmin();
+            else if (bothLabels.isEmpty())
+                return __.<Vertex, Edge>union(__.inE(ins), __.outE(outs)).asAdmin();
+            else
+                return null;  // no filter
+        }
+    }
+
+    public static GraphFilterStrategy instance() {
+        return INSTANCE;
+    }
+}

http://git-wip-us.apache.org/repos/asf/incubator-tinkerpop/blob/edd2f96d/gremlin-core/src/main/java/org/apache/tinkerpop/gremlin/process/traversal/TraversalStrategies.java
----------------------------------------------------------------------
diff --git a/gremlin-core/src/main/java/org/apache/tinkerpop/gremlin/process/traversal/TraversalStrategies.java
b/gremlin-core/src/main/java/org/apache/tinkerpop/gremlin/process/traversal/TraversalStrategies.java
index e365243..137abb9 100644
--- a/gremlin-core/src/main/java/org/apache/tinkerpop/gremlin/process/traversal/TraversalStrategies.java
+++ b/gremlin-core/src/main/java/org/apache/tinkerpop/gremlin/process/traversal/TraversalStrategies.java
@@ -19,6 +19,7 @@
 package org.apache.tinkerpop.gremlin.process.traversal;
 
 import org.apache.tinkerpop.gremlin.process.computer.GraphComputer;
+import org.apache.tinkerpop.gremlin.process.computer.traversal.strategy.optimization.GraphFilterStrategy;
 import org.apache.tinkerpop.gremlin.process.traversal.strategy.decoration.ConnectiveStrategy;
 import org.apache.tinkerpop.gremlin.process.traversal.strategy.finalization.ProfileStrategy;
 import org.apache.tinkerpop.gremlin.process.traversal.strategy.optimization.AdjacentToIncidentStrategy;
@@ -203,6 +204,7 @@ public interface TraversalStrategies extends Serializable, Cloneable {
 
             final TraversalStrategies graphComputerStrategies = new DefaultTraversalStrategies();
             graphComputerStrategies.addStrategies(
+                    GraphFilterStrategy.instance(),
                     OrderLimitStrategy.instance(),
                     PathProcessorStrategy.instance(),
                     ComputerVerificationStrategy.instance());

http://git-wip-us.apache.org/repos/asf/incubator-tinkerpop/blob/edd2f96d/gremlin-core/src/test/java/org/apache/tinkerpop/gremlin/process/computer/GraphFilterTest.java
----------------------------------------------------------------------
diff --git a/gremlin-core/src/test/java/org/apache/tinkerpop/gremlin/process/computer/GraphFilterTest.java
b/gremlin-core/src/test/java/org/apache/tinkerpop/gremlin/process/computer/GraphFilterTest.java
index 9f04fb9..c73324b 100644
--- a/gremlin-core/src/test/java/org/apache/tinkerpop/gremlin/process/computer/GraphFilterTest.java
+++ b/gremlin-core/src/test/java/org/apache/tinkerpop/gremlin/process/computer/GraphFilterTest.java
@@ -19,18 +19,52 @@
 
 package org.apache.tinkerpop.gremlin.process.computer;
 
+import org.apache.tinkerpop.gremlin.process.traversal.dsl.graph.__;
+import org.apache.tinkerpop.gremlin.structure.Direction;
+import org.apache.tinkerpop.gremlin.structure.Vertex;
+import org.junit.Test;
+
+import static org.junit.Assert.assertEquals;
+import static org.junit.Assert.assertFalse;
+import static org.junit.Assert.assertTrue;
+
 /**
  * @author Marko A. Rodriguez (http://markorodriguez.com)
  */
 public class GraphFilterTest {
 
-    /*@Test
-    public void shouldHandleStarGraph() {
-        final StarGraph graph = StarGraph.open();
-        final Vertex vertex = graph.addVertex("person");
-        for (int i = 0; i < 10; i++) {
-            vertex.addEdge("created", graph.addVertex(i < 5 ? "software" : "hardware"),
"weight", 1);
-        }
-        final GraphFilter graphFilter = new GraphFilter();
-    }*/
+    @Test
+    public void shouldHaveProperEdgeLegality() {
+        GraphFilter graphFilter = new GraphFilter();
+        assertFalse(graphFilter.hasEdgeFilter());
+        assertEquals(GraphFilter.Legal.YES, graphFilter.checkEdgeLegality(Direction.IN));
+        assertEquals(GraphFilter.Legal.YES, graphFilter.checkEdgeLegality(Direction.BOTH));
+        assertEquals(GraphFilter.Legal.YES, graphFilter.checkEdgeLegality(Direction.OUT));
+        //
+        graphFilter = new GraphFilter();
+        graphFilter.setEdgeFilter(__.<Vertex>bothE().limit(0));
+        assertTrue(graphFilter.hasEdgeFilter());
+        assertEquals(GraphFilter.Legal.NO, graphFilter.checkEdgeLegality(Direction.IN));
+        assertEquals(GraphFilter.Legal.NO, graphFilter.checkEdgeLegality(Direction.BOTH));
+        assertEquals(GraphFilter.Legal.NO, graphFilter.checkEdgeLegality(Direction.OUT));
+        //
+        graphFilter = new GraphFilter();
+        graphFilter.setEdgeFilter(__.outE());
+        assertTrue(graphFilter.hasEdgeFilter());
+        assertEquals(GraphFilter.Legal.NO, graphFilter.checkEdgeLegality(Direction.IN));
+        assertEquals(GraphFilter.Legal.NO, graphFilter.checkEdgeLegality(Direction.BOTH));
+        assertEquals(GraphFilter.Legal.MAYBE, graphFilter.checkEdgeLegality(Direction.OUT));
+        assertEquals(GraphFilter.Legal.MAYBE, graphFilter.checkEdgeLegality(Direction.OUT,
"knows"));
+        //
+        graphFilter = new GraphFilter();
+        graphFilter.setEdgeFilter(__.union(__.inE("bought"), __.outE("created"), __.bothE("knows",
"likes")));
+        assertTrue(graphFilter.hasEdgeFilter());
+        assertEquals(GraphFilter.Legal.MAYBE, graphFilter.checkEdgeLegality(Direction.IN));
+        assertEquals(GraphFilter.Legal.MAYBE, graphFilter.checkEdgeLegality(Direction.BOTH));
+        assertEquals(GraphFilter.Legal.MAYBE, graphFilter.checkEdgeLegality(Direction.OUT));
+        assertEquals(GraphFilter.Legal.MAYBE, graphFilter.checkEdgeLegality(Direction.OUT,
"created"));
+        assertEquals(GraphFilter.Legal.MAYBE, graphFilter.checkEdgeLegality(Direction.OUT,
"likes"));
+        assertEquals(GraphFilter.Legal.MAYBE, graphFilter.checkEdgeLegality(Direction.IN,
"created"));
+        assertEquals(GraphFilter.Legal.MAYBE, graphFilter.checkEdgeLegality(Direction.OUT,
"worksFor"));
+    }
 }
\ No newline at end of file

http://git-wip-us.apache.org/repos/asf/incubator-tinkerpop/blob/edd2f96d/gremlin-core/src/test/java/org/apache/tinkerpop/gremlin/process/computer/traversal/strategy/optimization/GraphFilterStrategyTest.java
----------------------------------------------------------------------
diff --git a/gremlin-core/src/test/java/org/apache/tinkerpop/gremlin/process/computer/traversal/strategy/optimization/GraphFilterStrategyTest.java
b/gremlin-core/src/test/java/org/apache/tinkerpop/gremlin/process/computer/traversal/strategy/optimization/GraphFilterStrategyTest.java
new file mode 100644
index 0000000..de812e0
--- /dev/null
+++ b/gremlin-core/src/test/java/org/apache/tinkerpop/gremlin/process/computer/traversal/strategy/optimization/GraphFilterStrategyTest.java
@@ -0,0 +1,77 @@
+/*
+ * 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.tinkerpop.gremlin.process.computer.traversal.strategy.optimization;
+
+import org.apache.tinkerpop.gremlin.process.traversal.Traversal;
+import org.apache.tinkerpop.gremlin.process.traversal.dsl.graph.__;
+import org.junit.Test;
+import org.junit.runner.RunWith;
+import org.junit.runners.Parameterized;
+
+import java.util.Arrays;
+
+import static org.apache.tinkerpop.gremlin.process.traversal.dsl.graph.__.as;
+import static org.junit.Assert.assertEquals;
+
+/**
+ * @author Marko A. Rodriguez (http://markorodriguez.com)
+ */
+@RunWith(Parameterized.class)
+public class GraphFilterStrategyTest {
+
+    @Parameterized.Parameter(value = 0)
+    public Traversal original;
+
+    @Parameterized.Parameter(value = 1)
+    public Traversal edgeFilter;
+
+
+    @Test
+    public void doTest() {
+        assertEquals(GraphFilterStrategy.instance().getEdgeFilter(this.original.asAdmin()),
this.edgeFilter);
+    }
+
+    @Parameterized.Parameters(name = "{0}")
+    public static Iterable<Object[]> generateTestParameters() {
+
+        return Arrays.asList(new Traversal[][]{
+                {__.V().count(), __.bothE().limit(0)},
+                {__.V().both().has("name"), null},
+                {__.bothE(), null},
+                {__.V().outE(), __.outE()},
+                {__.V().in(), __.inE()},
+                {__.V().local(__.outE("knows", "created").limit(10)), __.outE("knows", "created")},
+                {__.out("created"), __.outE("created")},
+                {__.in("created", "knows"), __.inE("created", "knows")},
+                {__.V().both("created"), __.bothE("created")},
+                {__.V().out("created").repeat(__.both("knows").until(__.inE("bought", "likes"))).outE("likes"),
__.union(__.outE("created"), __.bothE("bought", "knows", "likes"))},
+                {__.union(__.inE("created"), __.bothE()), null},
+                {__.union(__.inE("created"), __.outE("created")), __.bothE("created")},
+                {__.union(__.inE("knows"), __.outE("created")), __.union(__.outE("created"),
__.bothE("knows"))},
+                {__.union(__.inE("knows", "created"), __.outE("created")), __.bothE("knows",
"created")},
+                {__.V().match(
+                        as("a").in("created").as("b"),
+                        as("b").in("knows").as("c")).select("c").out("created").values("name"),
__.union(__.inE("knows"), __.bothE("created"))},
+                {__.V().out().out().match(
+                        as("a").in("created").as("b"),
+                        as("b").in("knows").as("c")).select("c").out("created").values("name"),
null}
+        });
+    }
+}


Mime
View raw message