You are viewing a plain text version of this content. The canonical link for it is here.
Posted to commits@tinkerpop.apache.org by dk...@apache.org on 2015/05/06 17:07:48 UTC
incubator-tinkerpop git commit: implemented IncidentToAdjacentStrategy
Repository: incubator-tinkerpop
Updated Branches:
refs/heads/master 1ca27d469 -> c395647fe
implemented IncidentToAdjacentStrategy
Project: http://git-wip-us.apache.org/repos/asf/incubator-tinkerpop/repo
Commit: http://git-wip-us.apache.org/repos/asf/incubator-tinkerpop/commit/c395647f
Tree: http://git-wip-us.apache.org/repos/asf/incubator-tinkerpop/tree/c395647f
Diff: http://git-wip-us.apache.org/repos/asf/incubator-tinkerpop/diff/c395647f
Branch: refs/heads/master
Commit: c395647fe70d750118478d13d7729f51591eea1d
Parents: 1ca27d4
Author: Daniel Kuppitz <da...@hotmail.com>
Authored: Wed May 6 17:07:29 2015 +0200
Committer: Daniel Kuppitz <da...@hotmail.com>
Committed: Wed May 6 17:07:29 2015 +0200
----------------------------------------------------------------------
.../process/traversal/TraversalStrategies.java | 1 +
.../AdjacentToIncidentStrategy.java | 15 ++-
.../IncidentToAdjacentStrategy.java | 117 +++++++++++++++++
.../IncidentToAdjacentStrategyTest.java | 130 +++++++++++++++++++
.../tinkergraph/structure/TinkerGraphTest.java | 10 +-
5 files changed, 269 insertions(+), 4 deletions(-)
----------------------------------------------------------------------
http://git-wip-us.apache.org/repos/asf/incubator-tinkerpop/blob/c395647f/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 3fb7ed2..e6f91f1 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
@@ -153,6 +153,7 @@ public interface TraversalStrategies extends Serializable, Cloneable {
ConjunctionStrategy.instance(),
EngineDependentStrategy.instance(),
ProfileStrategy.instance(),
+ IncidentToAdjacentStrategy.instance(),
AdjacentToIncidentStrategy.instance(),
ComparatorHolderRemovalStrategy.instance(),
DedupBijectionStrategy.instance(),
http://git-wip-us.apache.org/repos/asf/incubator-tinkerpop/blob/c395647f/gremlin-core/src/main/java/org/apache/tinkerpop/gremlin/process/traversal/strategy/optimization/AdjacentToIncidentStrategy.java
----------------------------------------------------------------------
diff --git a/gremlin-core/src/main/java/org/apache/tinkerpop/gremlin/process/traversal/strategy/optimization/AdjacentToIncidentStrategy.java b/gremlin-core/src/main/java/org/apache/tinkerpop/gremlin/process/traversal/strategy/optimization/AdjacentToIncidentStrategy.java
index 4a02eb1..0b07c37 100644
--- a/gremlin-core/src/main/java/org/apache/tinkerpop/gremlin/process/traversal/strategy/optimization/AdjacentToIncidentStrategy.java
+++ b/gremlin-core/src/main/java/org/apache/tinkerpop/gremlin/process/traversal/strategy/optimization/AdjacentToIncidentStrategy.java
@@ -34,6 +34,10 @@ import org.apache.tinkerpop.gremlin.structure.Edge;
import org.apache.tinkerpop.gremlin.structure.PropertyType;
import org.apache.tinkerpop.gremlin.structure.Vertex;
+import java.util.Collections;
+import java.util.List;
+import java.util.Set;
+
/**
* This strategy looks for vertex- and value-emitting steps followed by a {@link CountGlobalStep} and replaces the
* pattern with an edge- or property-emitting step followed by a <code>CountGlobalStep</code>. Furthermore, if a vertex-
@@ -55,16 +59,18 @@ public final class AdjacentToIncidentStrategy extends AbstractTraversalStrategy<
implements TraversalStrategy.OptimizationStrategy {
private static final AdjacentToIncidentStrategy INSTANCE = new AdjacentToIncidentStrategy();
+ private static final Set<Class<? extends OptimizationStrategy>> PRIORS = Collections.singleton(IncidentToAdjacentStrategy.class);
private AdjacentToIncidentStrategy() {
}
@Override
public void apply(Traversal.Admin<?, ?> traversal) {
- final int size = traversal.getSteps().size() - 1;
+ final List<Step> steps = traversal.getSteps();
+ final int size = steps.size() - 1;
Step prev = null;
for (int i = 0; i <= size; i++) {
- final Step curr = traversal.getSteps().get(i);
+ final Step curr = steps.get(i);
if (i == size && isOptimizable(curr)) {
final TraversalParent parent = curr.getTraversal().getParent();
if (parent instanceof HasTraversalStep || parent instanceof ConjunctionStep) {
@@ -81,6 +87,11 @@ public final class AdjacentToIncidentStrategy extends AbstractTraversalStrategy<
}
}
+ @Override
+ public Set<Class<? extends OptimizationStrategy>> applyPrior() {
+ return PRIORS;
+ }
+
/**
* Checks whether a given step is optimizable or not.
*
http://git-wip-us.apache.org/repos/asf/incubator-tinkerpop/blob/c395647f/gremlin-core/src/main/java/org/apache/tinkerpop/gremlin/process/traversal/strategy/optimization/IncidentToAdjacentStrategy.java
----------------------------------------------------------------------
diff --git a/gremlin-core/src/main/java/org/apache/tinkerpop/gremlin/process/traversal/strategy/optimization/IncidentToAdjacentStrategy.java b/gremlin-core/src/main/java/org/apache/tinkerpop/gremlin/process/traversal/strategy/optimization/IncidentToAdjacentStrategy.java
new file mode 100644
index 0000000..53c3001
--- /dev/null
+++ b/gremlin-core/src/main/java/org/apache/tinkerpop/gremlin/process/traversal/strategy/optimization/IncidentToAdjacentStrategy.java
@@ -0,0 +1,117 @@
+/*
+ * 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.traversal.strategy.optimization;
+
+import org.apache.tinkerpop.gremlin.process.traversal.Step;
+import org.apache.tinkerpop.gremlin.process.traversal.Traversal;
+import org.apache.tinkerpop.gremlin.process.traversal.TraversalStrategy;
+import org.apache.tinkerpop.gremlin.process.traversal.step.LambdaHolder;
+import org.apache.tinkerpop.gremlin.process.traversal.step.map.EdgeOtherVertexStep;
+import org.apache.tinkerpop.gremlin.process.traversal.step.map.EdgeVertexStep;
+import org.apache.tinkerpop.gremlin.process.traversal.step.map.PathStep;
+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.Vertex;
+import org.javatuples.Pair;
+
+import java.util.ArrayList;
+import java.util.Collection;
+
+/**
+ * This strategy looks for <code>.outE().inV()</code>, <code>.inE().outV()</code> and <code>.bothE().otherV()</code>
+ * and replaces these step sequences with <code>.out()</code>, <code>.in()</code> or <code>.both()</code> respectively.
+ * The strategy won't modify the traversal if:
+ * <ul>
+ * <li>the edge step is labeled</li>
+ * <li>the traversal contains a <code>path</code> step</li>
+ * <li>the traversal contains a lambda step</li>
+ * </ul>
+ * <p/>
+ *
+ * @author Daniel Kuppitz (http://gremlin.guru)
+ */
+public final class IncidentToAdjacentStrategy extends AbstractTraversalStrategy<TraversalStrategy.OptimizationStrategy>
+ implements TraversalStrategy.OptimizationStrategy {
+
+ private static final IncidentToAdjacentStrategy INSTANCE = new IncidentToAdjacentStrategy();
+
+ private IncidentToAdjacentStrategy() {
+ }
+
+ @Override
+ public void apply(Traversal.Admin<?, ?> traversal) {
+ final int size = traversal.getSteps().size() - 1;
+ boolean isOptimizable = true;
+ final Collection<Pair<VertexStep, Step>> stepsToReplace = new ArrayList<>();
+ Step prev = null;
+ for (int i = 0; i <= size && isOptimizable; i++) {
+ final Step curr = traversal.getSteps().get(i);
+ if (isOptimizable(prev, curr)) {
+ stepsToReplace.add(Pair.with((VertexStep) prev, curr));
+ }
+ isOptimizable = !(curr instanceof PathStep) && !(curr instanceof LambdaHolder);
+ prev = curr;
+ }
+ if (isOptimizable && !stepsToReplace.isEmpty()) {
+ for (final Pair<VertexStep, Step> steps : stepsToReplace) {
+ optimizeSteps(traversal, steps.getValue0(), steps.getValue1());
+ }
+ }
+ }
+
+ /**
+ * Checks whether a given step is optimizable or not.
+ *
+ * @param step1 an edge-emitting step
+ * @param step2 a vertex-emitting step
+ * @return <code>true</code> if step1 is not labeled and emits edges and step2 emits vertices,
+ * otherwise <code>false</code>
+ */
+ private static boolean isOptimizable(final Step step1, final Step step2) {
+ if (step1 instanceof VertexStep && Edge.class.equals(((VertexStep) step1).getReturnClass()) && step1.getLabels().isEmpty()) {
+ final Direction step1Dir = ((VertexStep) step1).getDirection();
+ if (step1Dir.equals(Direction.BOTH)) {
+ return step2 instanceof EdgeOtherVertexStep;
+ }
+ return step2 instanceof EdgeVertexStep && ((EdgeVertexStep) step2).getDirection().equals(step1Dir.opposite());
+ }
+ return false;
+ }
+
+ /**
+ * Optimizes the given edge-emitting step and the vertex-emitting step by replacing them with a single
+ * vertex-emitting step.
+ *
+ * @param traversal the traversal that holds the given steps
+ * @param step1 the edge-emitting step to replace
+ * @param step2 the vertex-emitting step to replace
+ */
+ private static void optimizeSteps(final Traversal.Admin traversal, final VertexStep step1, final Step step2) {
+ final Step newStep = new VertexStep(traversal, Vertex.class, step1.getDirection(), step1.getEdgeLabels());
+ TraversalHelper.replaceStep(step1, newStep, traversal);
+ traversal.removeStep(step2);
+ }
+
+ public static IncidentToAdjacentStrategy instance() {
+ return INSTANCE;
+ }
+}
http://git-wip-us.apache.org/repos/asf/incubator-tinkerpop/blob/c395647f/gremlin-core/src/test/java/org/apache/tinkerpop/gremlin/process/traversal/strategy/optimization/IncidentToAdjacentStrategyTest.java
----------------------------------------------------------------------
diff --git a/gremlin-core/src/test/java/org/apache/tinkerpop/gremlin/process/traversal/strategy/optimization/IncidentToAdjacentStrategyTest.java b/gremlin-core/src/test/java/org/apache/tinkerpop/gremlin/process/traversal/strategy/optimization/IncidentToAdjacentStrategyTest.java
new file mode 100644
index 0000000..2816b3e
--- /dev/null
+++ b/gremlin-core/src/test/java/org/apache/tinkerpop/gremlin/process/traversal/strategy/optimization/IncidentToAdjacentStrategyTest.java
@@ -0,0 +1,130 @@
+/*
+ * 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.traversal.strategy.optimization;
+
+import org.apache.tinkerpop.gremlin.process.traversal.Traversal;
+import org.apache.tinkerpop.gremlin.process.traversal.TraversalEngine;
+import org.apache.tinkerpop.gremlin.process.traversal.TraversalStrategies;
+import org.apache.tinkerpop.gremlin.process.traversal.dsl.graph.__;
+import org.apache.tinkerpop.gremlin.process.traversal.util.DefaultTraversalStrategies;
+import org.junit.Before;
+import org.junit.Test;
+import org.junit.experimental.runners.Enclosed;
+import org.junit.runner.RunWith;
+import org.junit.runners.Parameterized;
+
+import java.util.Arrays;
+
+import static org.junit.Assert.assertEquals;
+import static org.mockito.Mockito.mock;
+import static org.mockito.Mockito.when;
+
+/**
+ * @author Daniel Kuppitz (http://gremlin.guru)
+ */
+@RunWith(Enclosed.class)
+public class IncidentToAdjacentStrategyTest {
+
+ @RunWith(Parameterized.class)
+ public static class StandardTest extends AbstractIncidentToAdjacentStrategyTest {
+
+ @Parameterized.Parameters(name = "{0}")
+ public static Iterable<Object[]> data() {
+ return generateTestParameters();
+ }
+
+ @Parameterized.Parameter(value = 0)
+ public Traversal original;
+
+ @Parameterized.Parameter(value = 1)
+ public Traversal optimized;
+
+ @Before
+ public void setup() {
+ this.traversalEngine = mock(TraversalEngine.class);
+ when(this.traversalEngine.getType()).thenReturn(TraversalEngine.Type.STANDARD);
+ }
+
+ @Test
+ public void shouldApplyStrategy() {
+ doTest(original, optimized);
+ }
+ }
+
+ @RunWith(Parameterized.class)
+ public static class ComputerTest extends AbstractIncidentToAdjacentStrategyTest {
+
+ @Parameterized.Parameters(name = "{0}")
+ public static Iterable<Object[]> data() {
+ return generateTestParameters();
+ }
+
+ @Parameterized.Parameter(value = 0)
+ public Traversal original;
+
+ @Parameterized.Parameter(value = 1)
+ public Traversal optimized;
+
+ @Before
+ public void setup() {
+ this.traversalEngine = mock(TraversalEngine.class);
+ when(this.traversalEngine.getType()).thenReturn(TraversalEngine.Type.COMPUTER);
+ }
+
+ @Test
+ public void shouldApplyStrategy() {
+ doTest(original, optimized);
+ }
+ }
+
+ private static abstract class AbstractIncidentToAdjacentStrategyTest {
+
+ protected TraversalEngine traversalEngine;
+
+ void applyIncidentToAdjacentStrategy(final Traversal traversal) {
+ final TraversalStrategies strategies = new DefaultTraversalStrategies();
+ strategies.addStrategies(IncidentToAdjacentStrategy.instance());
+
+ traversal.asAdmin().setStrategies(strategies);
+ traversal.asAdmin().applyStrategies();
+ traversal.asAdmin().setEngine(traversalEngine);
+ }
+
+ public void doTest(final Traversal traversal, final Traversal optimized) {
+ applyIncidentToAdjacentStrategy(traversal);
+ assertEquals(optimized.toString(), traversal.toString());
+ }
+
+ static Iterable<Object[]> generateTestParameters() {
+
+ return Arrays.asList(new Traversal[][]{
+ {__.outE().inV(), __.out()},
+ {__.inE().outV(), __.in()},
+ {__.bothE().otherV(), __.both()},
+ {__.outE().outV(), __.outE().outV()},
+ {__.inE().inV(), __.inE().inV()},
+ {__.bothE().bothV(), __.bothE().bothV()},
+ {__.bothE().inV(), __.bothE().inV()},
+ {__.bothE().outV(), __.bothE().outV()},
+ {__.outE().as("a").inV(), __.outE().as("a").inV()}, // todo: this can be optimized, but requires a lot more checks
+ {__.outE().inV().path(), __.outE().inV().path()},
+ {__.outE().inV().map(e -> e), __.outE().inV().map(e -> e)}});
+ }
+ }
+}
http://git-wip-us.apache.org/repos/asf/incubator-tinkerpop/blob/c395647f/tinkergraph-gremlin/src/test/java/org/apache/tinkerpop/gremlin/tinkergraph/structure/TinkerGraphTest.java
----------------------------------------------------------------------
diff --git a/tinkergraph-gremlin/src/test/java/org/apache/tinkerpop/gremlin/tinkergraph/structure/TinkerGraphTest.java b/tinkergraph-gremlin/src/test/java/org/apache/tinkerpop/gremlin/tinkergraph/structure/TinkerGraphTest.java
index c9670cc..b6fc864 100644
--- a/tinkergraph-gremlin/src/test/java/org/apache/tinkerpop/gremlin/tinkergraph/structure/TinkerGraphTest.java
+++ b/tinkergraph-gremlin/src/test/java/org/apache/tinkerpop/gremlin/tinkergraph/structure/TinkerGraphTest.java
@@ -142,8 +142,14 @@ public class TinkerGraphTest {
public void testPlayDK() throws Exception {
final Graph graph = TinkerFactory.createModern();
final GraphTraversalSource g = graph.traversal();
- final Traversal traversal = g.V().hasNot(out());
- traversal.iterate();
+ Traversal traversal = g.V().outE().inV().has(__.out("created")).has(__.outE("knows").inV().has("name", "josh"));
+ System.out.println(traversal.toString());
+ traversal.forEachRemaining(System.out::println);
+ System.out.println(traversal.toString());
+ System.out.println("--");
+ traversal = g.V().outE().inV().has(__.out("created")).has(__.outE("knows").inV());
+ System.out.println(traversal.toString());
+ traversal.forEachRemaining(System.out::println);
System.out.println(traversal.toString());
}