You are viewing a plain text version of this content. The canonical link for it is here.
Posted to commits@tinkerpop.apache.org by ok...@apache.org on 2016/05/06 22:05:25 UTC
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
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 <ok...@gmail.com>
Authored: Fri May 6 16:05:15 2016 -0600
Committer: Marko A. Rodriguez <ok...@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}
+ });
+ }
+}