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());
     }