Repository: incubator-tinkerpop Updated Branches: refs/heads/TINKERPOP-1312 [created] 5f3305315
Tweaked `RangeByIsCountStrategy`. The pattern `outE().count().is(0)` is now replaced by `not(outE())` Project: http://git-wip-us.apache.org/repos/asf/incubator-tinkerpop/repo Commit: http://git-wip-us.apache.org/repos/asf/incubator-tinkerpop/commit/5f330531 Tree: http://git-wip-us.apache.org/repos/asf/incubator-tinkerpop/tree/5f330531 Diff: http://git-wip-us.apache.org/repos/asf/incubator-tinkerpop/diff/5f330531 Branch: refs/heads/TINKERPOP-1312 Commit: 5f3305315052258d3e659b1d984e87e73ad2b0af Parents: 55a509f Author: Daniel Kuppitz <daniel_kupp...@hotmail.com> Authored: Wed May 25 21:13:48 2016 +0200 Committer: Daniel Kuppitz <daniel_kupp...@hotmail.com> Committed: Wed May 25 21:13:48 2016 +0200 ---------------------------------------------------------------------- .../optimization/RangeByIsCountStrategy.java | 27 +++-- .../RangeByIsCountStrategyTest.java | 105 ++++++++++++++++++- .../structure/TinkerGraphPlayTest.java | 43 ++++---- 3 files changed, 144 insertions(+), 31 deletions(-) ---------------------------------------------------------------------- http://git-wip-us.apache.org/repos/asf/incubator-tinkerpop/blob/5f330531/gremlin-core/src/main/java/org/apache/tinkerpop/gremlin/process/traversal/strategy/optimization/RangeByIsCountStrategy.java ---------------------------------------------------------------------- diff --git a/gremlin-core/src/main/java/org/apache/tinkerpop/gremlin/process/traversal/strategy/optimization/RangeByIsCountStrategy.java b/gremlin-core/src/main/java/org/apache/tinkerpop/gremlin/process/traversal/strategy/optimization/RangeByIsCountStrategy.java index f2d60b1..f3168a3 100644 --- a/gremlin-core/src/main/java/org/apache/tinkerpop/gremlin/process/traversal/strategy/optimization/RangeByIsCountStrategy.java +++ b/gremlin-core/src/main/java/org/apache/tinkerpop/gremlin/process/traversal/strategy/optimization/RangeByIsCountStrategy.java @@ -18,18 +18,20 @@ */ package org.apache.tinkerpop.gremlin.process.traversal.strategy.optimization; +import org.apache.tinkerpop.gremlin.process.traversal.Compare; +import org.apache.tinkerpop.gremlin.process.traversal.Contains; +import org.apache.tinkerpop.gremlin.process.traversal.P; 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.dsl.graph.__; import org.apache.tinkerpop.gremlin.process.traversal.step.filter.IsStep; +import org.apache.tinkerpop.gremlin.process.traversal.step.filter.NotStep; import org.apache.tinkerpop.gremlin.process.traversal.step.filter.RangeGlobalStep; import org.apache.tinkerpop.gremlin.process.traversal.step.map.CountGlobalStep; import org.apache.tinkerpop.gremlin.process.traversal.strategy.AbstractTraversalStrategy; import org.apache.tinkerpop.gremlin.process.traversal.util.ConnectiveP; import org.apache.tinkerpop.gremlin.process.traversal.util.TraversalHelper; -import org.apache.tinkerpop.gremlin.process.traversal.Compare; -import org.apache.tinkerpop.gremlin.process.traversal.Contains; -import org.apache.tinkerpop.gremlin.process.traversal.P; import java.util.Collection; import java.util.Collections; @@ -47,7 +49,7 @@ import java.util.function.BiPredicate; * * @author Daniel Kuppitz (http://gremlin.guru) * @example <pre> - * __.outE().count().is(0) // is replaced by __.outE().limit(1).count().is(0) + * __.outE().count().is(0) // is replaced by __.not(outE()) * __.outE().count().is(lt(3)) // is replaced by __.outE().limit(3).count().is(lt(3)) * __.outE().count().is(gt(3)) // is replaced by __.outE().limit(4).count().is(gt(3)) * </pre> @@ -78,6 +80,7 @@ public final class RangeByIsCountStrategy extends AbstractTraversalStrategy<Trav final IsStep isStep = (IsStep) next; final P isStepPredicate = isStep.getPredicate(); Long highRange = null; + boolean useNotStep = false; for (P p : isStepPredicate instanceof ConnectiveP ? ((ConnectiveP<?>) isStepPredicate).getPredicates() : Collections.singletonList(isStepPredicate)) { final Object value = p.getValue(); final BiPredicate predicate = p.getBiPredicate(); @@ -85,7 +88,11 @@ public final class RangeByIsCountStrategy extends AbstractTraversalStrategy<Trav final long highRangeOffset = INCREASED_OFFSET_SCALAR_PREDICATES.contains(predicate) ? 1L : 0L; final Long highRangeCandidate = ((Number) value).longValue() + highRangeOffset; final boolean update = highRange == null || highRangeCandidate > highRange; - if (update) highRange = highRangeCandidate; + if (update) { + highRange = highRangeCandidate; + useNotStep = (highRange <= 1L && predicate.equals(Compare.lt)) || + (highRange == 1L && (predicate.equals(Compare.eq) || predicate.equals(Compare.lte))); + } } else { final Long highRangeOffset = RANGE_PREDICATES.get(predicate); if (value instanceof Collection && highRangeOffset != null) { @@ -99,7 +106,15 @@ public final class RangeByIsCountStrategy extends AbstractTraversalStrategy<Trav } } if (highRange != null) { - TraversalHelper.insertBeforeStep(new RangeGlobalStep<>(traversal, 0L, highRange), curr, traversal); + if (useNotStep) { + traversal.asAdmin().removeStep(next); // IsStep + traversal.asAdmin().removeStep(curr); // CountStep + final Traversal.Admin inner = __.start().asAdmin(); + TraversalHelper.insertAfterStep(prev, inner.getStartStep(), inner); + TraversalHelper.replaceStep(prev, new NotStep<>(traversal, inner), traversal); + } else { + TraversalHelper.insertBeforeStep(new RangeGlobalStep<>(traversal, 0L, highRange), curr, traversal); + } i++; } } http://git-wip-us.apache.org/repos/asf/incubator-tinkerpop/blob/5f330531/gremlin-core/src/test/java/org/apache/tinkerpop/gremlin/process/traversal/strategy/optimization/RangeByIsCountStrategyTest.java ---------------------------------------------------------------------- diff --git a/gremlin-core/src/test/java/org/apache/tinkerpop/gremlin/process/traversal/strategy/optimization/RangeByIsCountStrategyTest.java b/gremlin-core/src/test/java/org/apache/tinkerpop/gremlin/process/traversal/strategy/optimization/RangeByIsCountStrategyTest.java index 1642b41..a72df8e 100644 --- a/gremlin-core/src/test/java/org/apache/tinkerpop/gremlin/process/traversal/strategy/optimization/RangeByIsCountStrategyTest.java +++ b/gremlin-core/src/test/java/org/apache/tinkerpop/gremlin/process/traversal/strategy/optimization/RangeByIsCountStrategyTest.java @@ -22,6 +22,7 @@ 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.step.filter.NotStep; import org.apache.tinkerpop.gremlin.process.traversal.step.filter.RangeGlobalStep; import org.apache.tinkerpop.gremlin.process.traversal.step.filter.TraversalFilterStep; import org.apache.tinkerpop.gremlin.process.traversal.util.DefaultTraversalStrategies; @@ -36,7 +37,16 @@ import java.util.Arrays; import java.util.List; import java.util.concurrent.atomic.AtomicInteger; -import static org.apache.tinkerpop.gremlin.process.traversal.P.*; +import static org.apache.tinkerpop.gremlin.process.traversal.P.eq; +import static org.apache.tinkerpop.gremlin.process.traversal.P.gt; +import static org.apache.tinkerpop.gremlin.process.traversal.P.gte; +import static org.apache.tinkerpop.gremlin.process.traversal.P.inside; +import static org.apache.tinkerpop.gremlin.process.traversal.P.lt; +import static org.apache.tinkerpop.gremlin.process.traversal.P.lte; +import static org.apache.tinkerpop.gremlin.process.traversal.P.neq; +import static org.apache.tinkerpop.gremlin.process.traversal.P.outside; +import static org.apache.tinkerpop.gremlin.process.traversal.P.within; +import static org.apache.tinkerpop.gremlin.process.traversal.P.without; import static org.junit.Assert.assertEquals; import static org.mockito.Mockito.mock; import static org.mockito.Mockito.when; @@ -78,6 +88,32 @@ public class RangeByIsCountStrategyTest { } @RunWith(Parameterized.class) + public static class StandardNotTest extends AbstractRangeByIsCountStrategyTest { + + @Parameterized.Parameters(name = "{0}") + public static Iterable<Object[]> data() { + return generateNotTestParameters(); + } + + @Parameterized.Parameter(value = 0) + public String name; + + @Parameterized.Parameter(value = 1) + public Object predicate; + + @Before + public void setup() { + this.traversalEngine = mock(TraversalEngine.class); + when(this.traversalEngine.getType()).thenReturn(TraversalEngine.Type.STANDARD); + } + + @Test + public void shouldApplyStrategy() { + doTest(predicate); + } + } + + @RunWith(Parameterized.class) public static class ComputerTest extends AbstractRangeByIsCountStrategyTest { @Parameterized.Parameters(name = "{0}") @@ -106,6 +142,32 @@ public class RangeByIsCountStrategyTest { } } + @RunWith(Parameterized.class) + public static class ComputerNotTest extends AbstractRangeByIsCountStrategyTest { + + @Parameterized.Parameters(name = "{0}") + public static Iterable<Object[]> data() { + return generateNotTestParameters(); + } + + @Parameterized.Parameter(value = 0) + public String name; + + @Parameterized.Parameter(value = 1) + public Object predicate; + + @Before + public void setup() { + this.traversalEngine = mock(TraversalEngine.class); + when(this.traversalEngine.getType()).thenReturn(TraversalEngine.Type.COMPUTER); + } + + @Test + public void shouldApplyStrategy() { + doTest(predicate); + } + } + public static class SpecificComputerTest extends AbstractRangeByIsCountStrategyTest { @Before @@ -115,16 +177,31 @@ public class RangeByIsCountStrategyTest { } @Test - public void nestedCountEqualsNullShouldLimitToOne() { + public void nestedCountEqualsOneShouldLimitToTwo() { final AtomicInteger counter = new AtomicInteger(0); - final Traversal traversal = __.out().where(__.outE("created").count().is(0)); + final Traversal traversal = __.out().where(__.outE("created").count().is(1)); applyRangeByIsCountStrategy(traversal); final TraversalFilterStep filterStep = TraversalHelper.getStepsOfClass(TraversalFilterStep.class, traversal.asAdmin()).stream().findFirst().get(); final Traversal nestedTraversal = (Traversal) filterStep.getLocalChildren().get(0); TraversalHelper.getStepsOfClass(RangeGlobalStep.class, nestedTraversal.asAdmin()).stream().forEach(step -> { assertEquals(0, step.getLowRange()); - assertEquals(1, step.getHighRange()); + assertEquals(2, step.getHighRange()); + counter.incrementAndGet(); + }); + assertEquals(1, counter.get()); + } + + @Test + public void nestedCountEqualsNullShouldUseNotStep() { + final AtomicInteger counter = new AtomicInteger(0); + final Traversal traversal = __.out().where(__.outE("created").count().is(0)); + applyRangeByIsCountStrategy(traversal); + + final TraversalFilterStep filterStep = TraversalHelper.getStepsOfClass(TraversalFilterStep.class, traversal.asAdmin()).stream().findFirst().get(); + final Traversal nestedTraversal = (Traversal) filterStep.getLocalChildren().get(0); + TraversalHelper.getStepsOfClass(NotStep.class, nestedTraversal.asAdmin()).stream().forEach(step -> { + assertEquals(__.outE("created"), step.getLocalChildren().get(0)); counter.incrementAndGet(); }); assertEquals(1, counter.get()); @@ -162,10 +239,20 @@ public class RangeByIsCountStrategyTest { assertEquals(1, counter.intValue()); } + public void doTest(final Object predicate) { + final Traversal traversal = __.out().count().is(predicate); + + applyRangeByIsCountStrategy(traversal); + + final List<NotStep> steps = TraversalHelper.getStepsOfClass(NotStep.class, traversal.asAdmin()); + assertEquals(1, steps.size()); + + steps.forEach(step -> assertEquals(__.out(), step.getLocalChildren().get(0))); + } + static Iterable<Object[]> generateTestParameters() { return Arrays.asList(new Object[][]{ - {"countEqualsNullShouldLimitToOne", eq(0l), 1l}, {"countNotEqualsFourShouldLimitToFive", neq(4l), 5l}, {"countLessThanOrEqualThreeShouldLimitToFour", lte(3l), 4l}, {"countLessThanThreeShouldLimitToThree", lt(3l), 3l}, @@ -176,5 +263,13 @@ public class RangeByIsCountStrategyTest { {"countWithinTwoSixFourShouldLimitToSeven", within(2l, 6l, 4l), 7l}, {"countWithoutTwoSixFourShouldLimitToSix", without(2l, 6l, 4l), 6l}}); } + + static Iterable<Object[]> generateNotTestParameters() { + + return Arrays.asList(new Object[][]{ + {"countEqualsNullShouldUseNotStep", eq(0l)}, + {"countLessThanOneShouldUseNotStep", lt(1l)}, + {"countLessThanOrEqualNullShouldUseNotStep", lte(0l)}}); + } } } http://git-wip-us.apache.org/repos/asf/incubator-tinkerpop/blob/5f330531/tinkergraph-gremlin/src/test/java/org/apache/tinkerpop/gremlin/tinkergraph/structure/TinkerGraphPlayTest.java ---------------------------------------------------------------------- diff --git a/tinkergraph-gremlin/src/test/java/org/apache/tinkerpop/gremlin/tinkergraph/structure/TinkerGraphPlayTest.java b/tinkergraph-gremlin/src/test/java/org/apache/tinkerpop/gremlin/tinkergraph/structure/TinkerGraphPlayTest.java index c9f3e6d..269f400 100644 --- a/tinkergraph-gremlin/src/test/java/org/apache/tinkerpop/gremlin/tinkergraph/structure/TinkerGraphPlayTest.java +++ b/tinkergraph-gremlin/src/test/java/org/apache/tinkerpop/gremlin/tinkergraph/structure/TinkerGraphPlayTest.java @@ -18,7 +18,6 @@ */ package org.apache.tinkerpop.gremlin.tinkergraph.structure; -import org.apache.tinkerpop.gremlin.process.computer.bulkloading.BulkLoaderVertexProgram; import org.apache.tinkerpop.gremlin.process.traversal.Operator; import org.apache.tinkerpop.gremlin.process.traversal.Order; import org.apache.tinkerpop.gremlin.process.traversal.P; @@ -32,20 +31,30 @@ import org.apache.tinkerpop.gremlin.structure.Graph; import org.apache.tinkerpop.gremlin.structure.T; import org.apache.tinkerpop.gremlin.structure.Vertex; import org.apache.tinkerpop.gremlin.structure.io.graphml.GraphMLIo; -import org.apache.tinkerpop.gremlin.structure.util.GraphFactory; import org.apache.tinkerpop.gremlin.util.TimeUtil; import org.junit.Ignore; import org.junit.Test; import org.slf4j.Logger; import org.slf4j.LoggerFactory; -import java.io.File; import java.util.Arrays; import java.util.List; -import java.util.function.Function; import java.util.function.Supplier; -import static org.apache.tinkerpop.gremlin.process.traversal.dsl.graph.__.*; +import static org.apache.tinkerpop.gremlin.process.traversal.P.lt; +import static org.apache.tinkerpop.gremlin.process.traversal.dsl.graph.__.as; +import static org.apache.tinkerpop.gremlin.process.traversal.dsl.graph.__.both; +import static org.apache.tinkerpop.gremlin.process.traversal.dsl.graph.__.choose; +import static org.apache.tinkerpop.gremlin.process.traversal.dsl.graph.__.count; +import static org.apache.tinkerpop.gremlin.process.traversal.dsl.graph.__.fold; +import static org.apache.tinkerpop.gremlin.process.traversal.dsl.graph.__.has; +import static org.apache.tinkerpop.gremlin.process.traversal.dsl.graph.__.in; +import static org.apache.tinkerpop.gremlin.process.traversal.dsl.graph.__.out; +import static org.apache.tinkerpop.gremlin.process.traversal.dsl.graph.__.outE; +import static org.apache.tinkerpop.gremlin.process.traversal.dsl.graph.__.select; +import static org.apache.tinkerpop.gremlin.process.traversal.dsl.graph.__.union; +import static org.apache.tinkerpop.gremlin.process.traversal.dsl.graph.__.valueMap; +import static org.apache.tinkerpop.gremlin.process.traversal.dsl.graph.__.values; /** * @author Stephen Mallette (http://stephen.genoprime.com) @@ -71,7 +80,7 @@ public class TinkerGraphPlayTest { graph.io(GraphMLIo.build()).readGraph("data/grateful-dead.xml"); ///////// - g.V().group().by(T.label).by(values("name")).forEachRemaining(x->logger.info(x.toString())); + g.V().group().by(T.label).by(values("name")).forEachRemaining(x -> logger.info(x.toString())); logger.info("group: " + g.V().both("followedBy").both("followedBy").group().by("songType").by(count()).next()); logger.info("groupV3d0: " + g.V().both("followedBy").both("followedBy").groupV3d0().by("songType").by().by(__.count(Scope.local)).next()); @@ -126,7 +135,7 @@ public class TinkerGraphPlayTest { v7.addEdge("link", v9, "weight", 1f); v8.addEdge("link", v9, "weight", 7f); - g.traversal().withSack(Float.MIN_VALUE).V(v1).repeat(outE().sack(Operator.max, "weight").inV()).times(5).sack().forEachRemaining(x->logger.info(x.toString())); + g.traversal().withSack(Float.MIN_VALUE).V(v1).repeat(outE().sack(Operator.max, "weight").inV()).times(5).sack().forEachRemaining(x -> logger.info(x.toString())); } /* @Test @@ -200,18 +209,12 @@ public class TinkerGraphPlayTest { @Ignore public void testPlayDK() throws Exception { - new File("/tmp/tinkergraph2.kryo").deleteOnExit(); - new File("/tmp/tinkergraph3.kryo").deleteOnExit(); - - final Graph graph1 = TinkerFactory.createModern(); - final Graph graph2 = GraphFactory.open("/tmp/graph2.properties"); - TinkerFactory.generateModern((TinkerGraph) graph2); - graph2.close(); - - logger.info("graph1 -> graph2"); - graph1.compute().workers(1).program(BulkLoaderVertexProgram.build().userSuppliedIds(true).writeGraph("/tmp/graph2.properties").create(graph1)).submit().get(); - logger.info("graph1 -> graph3"); - graph1.compute().workers(1).program(BulkLoaderVertexProgram.build().userSuppliedIds(true).writeGraph("/tmp/graph3.properties").create(graph1)).submit().get(); + Graph graph = TinkerGraph.open(); + GraphTraversalSource g = graph.traversal(); + graph.io(GraphMLIo.build()).readGraph("/projects/apache/incubator-tinkerpop/data/grateful-dead.xml"); + System.out.println(g.V().filter(outE("sungBy").count().is(0)).explain()); + System.out.println(g.V().filter(outE("sungBy").count().is(lt(1))).explain()); + System.out.println(g.V().filter(outE("sungBy").count().is(1)).explain()); } @Test @@ -256,7 +259,7 @@ public class TinkerGraphPlayTest { logger.info(traversal.get().toString()); logger.info(traversal.get().iterate().toString()); - traversal.get().forEachRemaining(x->logger.info(x.toString())); + traversal.get().forEachRemaining(x -> logger.info(x.toString())); }