[01/13] tinkerpop git commit: Created OrdertedTraverser which allows us to move beyond the star graph for OrderGlobalStep by()-projections. Moreover, it reduces the complexity of ordering as the objects of comparison are already determined. Going to gene [Forced Update!]

[dk...@apache.org]

Repository: tinkerpop
Updated Branches:
  refs/heads/centrality-recipes e97255f20 -> 5577ea564 (forced update)


Created OrdertedTraverser which allows us to move beyond the star graph for OrderGlobalStep by()-projections. Moreover, it reduces the complexity of ordering as the objects of comparison are already determined. Going to generalize fully to a ProjectedTraverser which will allow us to do the same for SampleGlobalStep, DedupGlobalStep, and down the road maintain order even as the computation is re-distributed to workers.


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

Branch: refs/heads/centrality-recipes
Commit: 501e97a1ecb23f76b2fddba8eaed1dba4a5a839e
Parents: e80a4cd
Author: Marko A. Rodriguez <ok...@gmail.com>
Authored: Wed Jan 18 09:08:24 2017 -0700
Committer: Marko A. Rodriguez <ok...@gmail.com>
Committed: Wed Jan 18 09:08:24 2017 -0700

----------------------------------------------------------------------
 CHANGELOG.asciidoc                              |   1 +
 .../traversal/step/map/OrderGlobalStep.java     |  61 ++---
 .../step/util/CollectingBarrierStep.java        |   4 +-
 .../ComputerVerificationStrategy.java           |   5 +-
 .../traversal/traverser/OrderedTraverser.java   | 235 +++++++++++++++++++
 .../gremlin/structure/io/gryo/GryoVersion.java  |   4 +-
 6 files changed, 277 insertions(+), 33 deletions(-)
----------------------------------------------------------------------


http://git-wip-us.apache.org/repos/asf/tinkerpop/blob/501e97a1/CHANGELOG.asciidoc
----------------------------------------------------------------------
diff --git a/CHANGELOG.asciidoc b/CHANGELOG.asciidoc
index 4f3f9ce..86c6b4f 100644
--- a/CHANGELOG.asciidoc
+++ b/CHANGELOG.asciidoc
@@ -26,6 +26,7 @@ image::https://raw.githubusercontent.com/apache/tinkerpop/master/docs/static/ima
 TinkerPop 3.2.4 (Release Date: NOT OFFICIALLY RELEASED YET)
 ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
 
+* `OrderGlobalStep` now emits traversers with their `by()`-projections and thus, can move beyond the local star graph.
 * SASL negotiation supports both a byte array and Base64 encoded bytes as a string for authentication to Gremlin Server.
 * Deprecated `TinkerIoRegistry` replacing it with the more consistently named `TinkerIoRegistryV1d0`.
 * Made error messaging more consistent during result iteration timeouts in Gremlin Server.

http://git-wip-us.apache.org/repos/asf/tinkerpop/blob/501e97a1/gremlin-core/src/main/java/org/apache/tinkerpop/gremlin/process/traversal/step/map/OrderGlobalStep.java
----------------------------------------------------------------------
diff --git a/gremlin-core/src/main/java/org/apache/tinkerpop/gremlin/process/traversal/step/map/OrderGlobalStep.java b/gremlin-core/src/main/java/org/apache/tinkerpop/gremlin/process/traversal/step/map/OrderGlobalStep.java
index a7d21b2..ac5df90 100644
--- a/gremlin-core/src/main/java/org/apache/tinkerpop/gremlin/process/traversal/step/map/OrderGlobalStep.java
+++ b/gremlin-core/src/main/java/org/apache/tinkerpop/gremlin/process/traversal/step/map/OrderGlobalStep.java
@@ -27,10 +27,10 @@ import org.apache.tinkerpop.gremlin.process.traversal.step.ByModulating;
 import org.apache.tinkerpop.gremlin.process.traversal.step.ComparatorHolder;
 import org.apache.tinkerpop.gremlin.process.traversal.step.TraversalParent;
 import org.apache.tinkerpop.gremlin.process.traversal.step.util.CollectingBarrierStep;
+import org.apache.tinkerpop.gremlin.process.traversal.traverser.OrderedTraverser;
 import org.apache.tinkerpop.gremlin.process.traversal.traverser.TraverserRequirement;
 import org.apache.tinkerpop.gremlin.process.traversal.traverser.util.TraverserSet;
 import org.apache.tinkerpop.gremlin.structure.util.StringFactory;
-import org.apache.tinkerpop.gremlin.util.function.ChainedComparator;
 import org.javatuples.Pair;
 
 import java.io.Serializable;
@@ -49,8 +49,8 @@ import java.util.stream.Collectors;
 public final class OrderGlobalStep<S, C extends Comparable> extends CollectingBarrierStep<S> implements ComparatorHolder<S, C>, TraversalParent, ByModulating {
 
     private List<Pair<Traversal.Admin<S, C>, Comparator<C>>> comparators = new ArrayList<>();
-    private ChainedComparator<S, C> chainedComparator = null;
     private long limit = Long.MAX_VALUE;
+    private boolean isShuffle = false;
 
     public OrderGlobalStep(final Traversal.Admin traversal) {
         super(traversal);
@@ -58,12 +58,30 @@ public final class OrderGlobalStep<S, C extends Comparable> extends CollectingBa
 
     @Override
     public void barrierConsumer(final TraverserSet<S> traverserSet) {
-        if (null == this.chainedComparator)
-            this.chainedComparator = new ChainedComparator<>(true, this.comparators);
-        if (this.chainedComparator.isShuffle())
+        if (this.isShuffle)
             traverserSet.shuffle();
         else
-            traverserSet.sort((Comparator) this.chainedComparator);
+            traverserSet.sort(Comparator.naturalOrder());
+    }
+
+    @Override
+    public void processAllStarts() {
+        if (this.starts.hasNext()) {
+            while (this.starts.hasNext()) {
+                this.traverserSet.add(new OrderedTraverser<S>(this.starts.next(), (List) this.comparators));
+            }
+            this.barrierConsumer(this.traverserSet);
+        }
+    }
+
+    @Override
+    public Traverser.Admin<S> processNextStart() {
+        if (!this.traverserSet.isEmpty()) {
+            return this.traverserSet.remove();
+        } else if (this.starts.hasNext()) {
+            this.processAllStarts();
+        }
+        return ((OrderedTraverser) this.traverserSet.remove()).getInternal();
     }
 
     public void setLimit(final long limit) {
@@ -76,6 +94,7 @@ public final class OrderGlobalStep<S, C extends Comparable> extends CollectingBa
 
     @Override
     public void addComparator(final Traversal.Admin<S, C> traversal, final Comparator<C> comparator) {
+        this.isShuffle = Order.shuffle == (Comparator) comparator;
         this.comparators.add(new Pair<>(this.integrateChild(traversal), comparator));
     }
 
@@ -125,7 +144,6 @@ public final class OrderGlobalStep<S, C extends Comparable> extends CollectingBa
         for (final Pair<Traversal.Admin<S, C>, Comparator<C>> comparator : this.comparators) {
             clone.comparators.add(new Pair<>(comparator.getValue0().clone(), comparator.getValue1()));
         }
-        clone.chainedComparator = null;
         return clone;
     }
 
@@ -137,47 +155,34 @@ public final class OrderGlobalStep<S, C extends Comparable> extends CollectingBa
 
     @Override
     public MemoryComputeKey<TraverserSet<S>> getMemoryComputeKey() {
-        if (null == this.chainedComparator)
-            this.chainedComparator = new ChainedComparator<>(true, this.comparators);
-        return MemoryComputeKey.of(this.getId(), new OrderBiOperator<>(this.chainedComparator, this.limit), false, true);
+        return MemoryComputeKey.of(this.getId(), new OrderBiOperator<>(this.limit, this.isShuffle), false, true);
     }
 
     ////////////////
 
-    public static final class OrderBiOperator<S> implements BinaryOperator<TraverserSet<S>>, Serializable, Cloneable {
+    public static final class OrderBiOperator<S> implements BinaryOperator<TraverserSet<S>>, Serializable {
 
-        private ChainedComparator chainedComparator;
         private long limit;
+        private boolean isShuffle;
 
         private OrderBiOperator() {
             // for serializers that need a no-arg constructor
         }
 
-        public OrderBiOperator(final ChainedComparator<S, ?> chainedComparator, final long limit) {
-            this.chainedComparator = chainedComparator;
+        public OrderBiOperator(final long limit, final boolean isShuffle) {
             this.limit = limit;
-        }
-
-        @Override
-        public OrderBiOperator<S> clone() {
-            try {
-                final OrderBiOperator<S> clone = (OrderBiOperator<S>) super.clone();
-                clone.chainedComparator = this.chainedComparator.clone();
-                return clone;
-            } catch (final CloneNotSupportedException e) {
-                throw new IllegalStateException(e.getMessage(), e);
-            }
+            this.isShuffle = isShuffle;
         }
 
         @Override
         public TraverserSet<S> apply(final TraverserSet<S> setA, final TraverserSet<S> setB) {
             setA.addAll(setB);
             if (Long.MAX_VALUE != this.limit && setA.bulkSize() > this.limit) {
-                if (this.chainedComparator.isShuffle())
+                if (this.isShuffle)
                     setA.shuffle();
                 else
-                    setA.sort(this.chainedComparator);
-                long counter = 0l;
+                    setA.sort(Comparator.naturalOrder());
+                long counter = 0L;
                 final Iterator<Traverser.Admin<S>> traversers = setA.iterator();
                 while (traversers.hasNext()) {
                     final Traverser.Admin<S> traverser = traversers.next();

http://git-wip-us.apache.org/repos/asf/tinkerpop/blob/501e97a1/gremlin-core/src/main/java/org/apache/tinkerpop/gremlin/process/traversal/step/util/CollectingBarrierStep.java
----------------------------------------------------------------------
diff --git a/gremlin-core/src/main/java/org/apache/tinkerpop/gremlin/process/traversal/step/util/CollectingBarrierStep.java b/gremlin-core/src/main/java/org/apache/tinkerpop/gremlin/process/traversal/step/util/CollectingBarrierStep.java
index f9c85a2..b0cce80 100644
--- a/gremlin-core/src/main/java/org/apache/tinkerpop/gremlin/process/traversal/step/util/CollectingBarrierStep.java
+++ b/gremlin-core/src/main/java/org/apache/tinkerpop/gremlin/process/traversal/step/util/CollectingBarrierStep.java
@@ -39,8 +39,8 @@ import java.util.function.BinaryOperator;
  */
 public abstract class CollectingBarrierStep<S> extends AbstractStep<S, S> implements Barrier<TraverserSet<S>> {
 
-    private TraverserSet<S> traverserSet = new TraverserSet<>();
-    private int maxBarrierSize;
+    protected TraverserSet<S> traverserSet = new TraverserSet<>();
+    protected int maxBarrierSize;
 
     public CollectingBarrierStep(final Traversal.Admin traversal) {
         this(traversal, Integer.MAX_VALUE);

http://git-wip-us.apache.org/repos/asf/tinkerpop/blob/501e97a1/gremlin-core/src/main/java/org/apache/tinkerpop/gremlin/process/traversal/strategy/verification/ComputerVerificationStrategy.java
----------------------------------------------------------------------
diff --git a/gremlin-core/src/main/java/org/apache/tinkerpop/gremlin/process/traversal/strategy/verification/ComputerVerificationStrategy.java b/gremlin-core/src/main/java/org/apache/tinkerpop/gremlin/process/traversal/strategy/verification/ComputerVerificationStrategy.java
index fc73fc3..5777adb 100644
--- a/gremlin-core/src/main/java/org/apache/tinkerpop/gremlin/process/traversal/strategy/verification/ComputerVerificationStrategy.java
+++ b/gremlin-core/src/main/java/org/apache/tinkerpop/gremlin/process/traversal/strategy/verification/ComputerVerificationStrategy.java
@@ -28,6 +28,7 @@ import org.apache.tinkerpop.gremlin.process.traversal.step.GraphComputing;
 import org.apache.tinkerpop.gremlin.process.traversal.step.Mutating;
 import org.apache.tinkerpop.gremlin.process.traversal.step.PathProcessor;
 import org.apache.tinkerpop.gremlin.process.traversal.step.TraversalParent;
+import org.apache.tinkerpop.gremlin.process.traversal.step.filter.SampleGlobalStep;
 import org.apache.tinkerpop.gremlin.process.traversal.step.map.GraphStep;
 import org.apache.tinkerpop.gremlin.process.traversal.step.sideEffect.InjectStep;
 import org.apache.tinkerpop.gremlin.process.traversal.step.sideEffect.SubgraphStep;
@@ -86,8 +87,8 @@ public final class ComputerVerificationStrategy extends AbstractTraversalStrateg
                     throw new VerificationException("Local traversals may not traverse past the local star-graph on GraphComputer: " + traversalOptional.get(), traversal);
             }
 
-            // collecting barriers and dedup global use can only operate on the element and its properties (no incidences)
-            if (step instanceof CollectingBarrierStep && step instanceof TraversalParent) {
+            // sample step use can only operate on the element and its properties (no incidences)
+            if (step instanceof SampleGlobalStep) {
                 if (((TraversalParent) step).getLocalChildren().stream().filter(t -> !TraversalHelper.isLocalProperties(t)).findAny().isPresent())
                     throw new VerificationException("The following barrier step can not process the incident edges of a vertex on GraphComputer: " + step, traversal);
             }

http://git-wip-us.apache.org/repos/asf/tinkerpop/blob/501e97a1/gremlin-core/src/main/java/org/apache/tinkerpop/gremlin/process/traversal/traverser/OrderedTraverser.java
----------------------------------------------------------------------
diff --git a/gremlin-core/src/main/java/org/apache/tinkerpop/gremlin/process/traversal/traverser/OrderedTraverser.java b/gremlin-core/src/main/java/org/apache/tinkerpop/gremlin/process/traversal/traverser/OrderedTraverser.java
new file mode 100644
index 0000000..4dddaa3
--- /dev/null
+++ b/gremlin-core/src/main/java/org/apache/tinkerpop/gremlin/process/traversal/traverser/OrderedTraverser.java
@@ -0,0 +1,235 @@
+/*
+ *  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.traverser;
+
+import org.apache.tinkerpop.gremlin.process.traversal.Order;
+import org.apache.tinkerpop.gremlin.process.traversal.Path;
+import org.apache.tinkerpop.gremlin.process.traversal.Step;
+import org.apache.tinkerpop.gremlin.process.traversal.Traversal;
+import org.apache.tinkerpop.gremlin.process.traversal.TraversalSideEffects;
+import org.apache.tinkerpop.gremlin.process.traversal.Traverser;
+import org.apache.tinkerpop.gremlin.process.traversal.util.TraversalUtil;
+import org.apache.tinkerpop.gremlin.structure.util.Attachable;
+import org.javatuples.Pair;
+
+import java.util.ArrayList;
+import java.util.Comparator;
+import java.util.List;
+import java.util.Set;
+import java.util.function.Function;
+
+/**
+ * @author Marko A. Rodriguez (http://markorodriguez.com)
+ */
+public final class OrderedTraverser<T> implements Traverser.Admin<T> {
+
+    private Traverser.Admin<T> internal;
+    private int order;
+    private final List<Pair<Object, Comparator<?>>> orderChecks = new ArrayList<>();
+
+    private OrderedTraverser() {
+        // for serialization
+    }
+
+    public OrderedTraverser(final Traverser.Admin<T> internal, final List<Pair<Traversal.Admin<T, ?>, Comparator>> checks) {
+        this(internal, 0);
+        for (final Pair<Traversal.Admin<T, ?>, Comparator> pairs : checks) {
+            this.orderChecks.add(Pair.with(TraversalUtil.apply(this.internal, pairs.getValue0()), pairs.getValue1()));
+        }
+    }
+
+    public OrderedTraverser(final Traverser.Admin<T> internal, final int order) {
+        this.internal = internal instanceof OrderedTraverser ? ((OrderedTraverser) internal).internal : internal;
+        this.order = order;
+    }
+
+    public Traverser.Admin<T> getInternal() {
+        return this.internal;
+    }
+
+    public int order() {
+        return this.order;
+    }
+
+    @Override
+    public void merge(final Admin<?> other) {
+        this.internal.merge(other);
+    }
+
+    @Override
+    public <R> Admin<R> split(R r, Step<T, R> step) {
+        return new OrderedTraverser<>(this.internal.split(r, step), this.order);
+    }
+
+    @Override
+    public Admin<T> split() {
+        return new OrderedTraverser<>(this.internal.split(), this.order);
+    }
+
+    @Override
+    public void addLabels(final Set<String> labels) {
+        this.internal.addLabels(labels);
+    }
+
+    @Override
+    public void keepLabels(final Set<String> labels) {
+        this.internal.keepLabels(labels);
+    }
+
+    @Override
+    public void dropLabels(final Set<String> labels) {
+        this.internal.dropLabels(labels);
+    }
+
+    @Override
+    public void dropPath() {
+        this.internal.dropPath();
+    }
+
+    @Override
+    public void set(final T t) {
+        this.internal.set(t);
+    }
+
+    @Override
+    public void incrLoops(final String stepLabel) {
+        this.internal.incrLoops(stepLabel);
+    }
+
+    @Override
+    public void resetLoops() {
+        this.internal.resetLoops();
+    }
+
+    @Override
+    public String getStepId() {
+        return this.internal.getStepId();
+    }
+
+    @Override
+    public void setStepId(final String stepId) {
+        this.internal.setStepId(stepId);
+    }
+
+    @Override
+    public void setBulk(final long count) {
+        this.internal.setBulk(count);
+    }
+
+    @Override
+    public Admin<T> detach() {
+        this.internal = this.internal.detach();
+        return this;
+    }
+
+    @Override
+    public T attach(final Function<Attachable<T>, T> method) {
+        return this.internal.attach(method);
+    }
+
+    @Override
+    public void setSideEffects(final TraversalSideEffects sideEffects) {
+        this.internal.setSideEffects(sideEffects);
+    }
+
+    @Override
+    public TraversalSideEffects getSideEffects() {
+        return this.internal.getSideEffects();
+    }
+
+    @Override
+    public Set<String> getTags() {
+        return this.internal.getTags();
+    }
+
+    @Override
+    public T get() {
+        return this.internal.get();
+    }
+
+    @Override
+    public <S> S sack() {
+        return this.internal.sack();
+    }
+
+    @Override
+    public <S> void sack(final S object) {
+        this.internal.sack(object);
+    }
+
+    @Override
+    public Path path() {
+        return this.internal.path();
+    }
+
+    @Override
+    public int loops() {
+        return this.internal.loops();
+    }
+
+    @Override
+    public long bulk() {
+        return this.internal.bulk();
+    }
+
+    @Override
+    public int hashCode() {
+        return this.internal.hashCode();
+    }
+
+    @Override
+    public boolean equals(final Object object) {
+        return object instanceof OrderedTraverser && ((OrderedTraverser) object).internal.equals(this.internal);
+    }
+
+    @Override
+    public OrderedTraverser<T> clone() {
+        try {
+            final OrderedTraverser<T> clone = (OrderedTraverser<T>) super.clone();
+            clone.internal = (Traverser.Admin<T>) this.internal.clone();
+            return clone;
+        } catch (final CloneNotSupportedException e) {
+            throw new IllegalStateException(e.getMessage(), e);
+        }
+    }
+
+    @Override
+    public int compareTo(final Traverser<T> o) {
+        if (!(o instanceof OrderedTraverser))
+            return 0;
+        else {
+            if (this.orderChecks.isEmpty()) {
+                return Order.incr.compare(this.get(), o.get());
+            } else {
+                final OrderedTraverser<T> other = (OrderedTraverser<T>) o;
+                for (int i = 0; i < this.orderChecks.size(); i++) {
+                    final Comparator comparator = this.orderChecks.get(i).getValue1();
+                    final Object thisObject = this.orderChecks.get(i).getValue0();
+                    final Object otherObject = other.orderChecks.get(i).getValue0();
+                    final int comparison = comparator.compare(thisObject, otherObject);
+                    if (comparison != 0)
+                        return comparison;
+
+                }
+                return 0;
+            }
+        }
+    }
+}
\ No newline at end of file

http://git-wip-us.apache.org/repos/asf/tinkerpop/blob/501e97a1/gremlin-core/src/main/java/org/apache/tinkerpop/gremlin/structure/io/gryo/GryoVersion.java
----------------------------------------------------------------------
diff --git a/gremlin-core/src/main/java/org/apache/tinkerpop/gremlin/structure/io/gryo/GryoVersion.java b/gremlin-core/src/main/java/org/apache/tinkerpop/gremlin/structure/io/gryo/GryoVersion.java
index 0bd9e87..a04f2d9 100644
--- a/gremlin-core/src/main/java/org/apache/tinkerpop/gremlin/structure/io/gryo/GryoVersion.java
+++ b/gremlin-core/src/main/java/org/apache/tinkerpop/gremlin/structure/io/gryo/GryoVersion.java
@@ -51,6 +51,7 @@ import org.apache.tinkerpop.gremlin.process.traversal.traverser.LP_O_OB_P_S_SE_S
 import org.apache.tinkerpop.gremlin.process.traversal.traverser.LP_O_OB_S_SE_SL_Traverser;
 import org.apache.tinkerpop.gremlin.process.traversal.traverser.O_OB_S_SE_SL_Traverser;
 import org.apache.tinkerpop.gremlin.process.traversal.traverser.O_Traverser;
+import org.apache.tinkerpop.gremlin.process.traversal.traverser.OrderedTraverser;
 import org.apache.tinkerpop.gremlin.process.traversal.traverser.util.TraverserSet;
 import org.apache.tinkerpop.gremlin.process.traversal.util.AndP;
 import org.apache.tinkerpop.gremlin.process.traversal.util.DefaultTraversalMetrics;
@@ -221,7 +222,7 @@ public enum GryoVersion {
             add(GryoTypeReg.of(AbstractMap.SimpleImmutableEntry.class, 121));
             add(GryoTypeReg.of(java.sql.Timestamp.class, 161));
             add(GryoTypeReg.of(InetAddress.class, 162, new UtilSerializers.InetAddressSerializer()));
-            add(GryoTypeReg.of(ByteBuffer.class, 163, new UtilSerializers.ByteBufferSerializer()));  // ***LAST ID***
+            add(GryoTypeReg.of(ByteBuffer.class, 163, new UtilSerializers.ByteBufferSerializer()));
 
             add(GryoTypeReg.of(ReferenceEdge.class, 81));
             add(GryoTypeReg.of(ReferenceVertexProperty.class, 82));
@@ -245,6 +246,7 @@ public enum GryoVersion {
             add(GryoTypeReg.of(O_OB_S_SE_SL_Traverser.class, 89));
             add(GryoTypeReg.of(LP_O_OB_S_SE_SL_Traverser.class, 90));
             add(GryoTypeReg.of(LP_O_OB_P_S_SE_SL_Traverser.class, 91));
+            add(GryoTypeReg.of(OrderedTraverser.class, 164));   // ***LAST ID***
             add(GryoTypeReg.of(DefaultRemoteTraverser.class, 123, new GryoSerializers.DefaultRemoteTraverserSerializer()));
 
             add(GryoTypeReg.of(Bytecode.class, 122, new GryoSerializers.BytecodeSerializer()));

[04/13] tinkerpop git commit: updated CHANGELOG and tweaked ProjectTraverser variable naming.

[dk...@apache.org]

updated CHANGELOG and tweaked ProjectTraverser variable naming.


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

Branch: refs/heads/centrality-recipes
Commit: 91e1f50c8b95d295a86cba6f3c9db7a002664233
Parents: b2f0c57
Author: Marko A. Rodriguez <ok...@gmail.com>
Authored: Wed Jan 18 11:17:05 2017 -0700
Committer: Marko A. Rodriguez <ok...@gmail.com>
Committed: Wed Jan 18 11:17:05 2017 -0700

----------------------------------------------------------------------
 CHANGELOG.asciidoc                              |  3 +-
 .../traversal/traverser/ProjectedTraverser.java | 69 +++++++++-----------
 2 files changed, 34 insertions(+), 38 deletions(-)
----------------------------------------------------------------------


http://git-wip-us.apache.org/repos/asf/tinkerpop/blob/91e1f50c/CHANGELOG.asciidoc
----------------------------------------------------------------------
diff --git a/CHANGELOG.asciidoc b/CHANGELOG.asciidoc
index 86c6b4f..052257f 100644
--- a/CHANGELOG.asciidoc
+++ b/CHANGELOG.asciidoc
@@ -26,7 +26,8 @@ image::https://raw.githubusercontent.com/apache/tinkerpop/master/docs/static/ima
 TinkerPop 3.2.4 (Release Date: NOT OFFICIALLY RELEASED YET)
 ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
 
-* `OrderGlobalStep` now emits traversers with their `by()`-projections and thus, can move beyond the local star graph.
+* Added `ProjectedTraverser` which wraps a traverser with a `List<Object>` of projected data.
+* `OrderGlobalStep` and `SampleGlobalStep` now emit traversers with their `by()`-projections and thus, can move beyond the local star graph.
 * SASL negotiation supports both a byte array and Base64 encoded bytes as a string for authentication to Gremlin Server.
 * Deprecated `TinkerIoRegistry` replacing it with the more consistently named `TinkerIoRegistryV1d0`.
 * Made error messaging more consistent during result iteration timeouts in Gremlin Server.

http://git-wip-us.apache.org/repos/asf/tinkerpop/blob/91e1f50c/gremlin-core/src/main/java/org/apache/tinkerpop/gremlin/process/traversal/traverser/ProjectedTraverser.java
----------------------------------------------------------------------
diff --git a/gremlin-core/src/main/java/org/apache/tinkerpop/gremlin/process/traversal/traverser/ProjectedTraverser.java b/gremlin-core/src/main/java/org/apache/tinkerpop/gremlin/process/traversal/traverser/ProjectedTraverser.java
index 5cecdc4..128e377 100644
--- a/gremlin-core/src/main/java/org/apache/tinkerpop/gremlin/process/traversal/traverser/ProjectedTraverser.java
+++ b/gremlin-core/src/main/java/org/apache/tinkerpop/gremlin/process/traversal/traverser/ProjectedTraverser.java
@@ -34,163 +34,158 @@ import java.util.function.Function;
  */
 public final class ProjectedTraverser<T, P> implements Traverser.Admin<T> {
 
-    private Traverser.Admin<T> internal;
+    private Traverser.Admin<T> baseTraverser;
     private List<P> projections;
 
     private ProjectedTraverser() {
         // for serialization
     }
 
-    public ProjectedTraverser(final Traverser.Admin<T> internal, final List<P> projections) {
-        this.internal = internal;
+    public ProjectedTraverser(final Traverser.Admin<T> baseTraverser, final List<P> projections) {
+        this.baseTraverser = baseTraverser;
         this.projections = projections;
     }
 
-
-    public Traverser.Admin<T> getInternal() {
-        return this.internal;
-    }
-
     public List<P> getProjections() {
         return this.projections;
     }
 
     @Override
     public void merge(final Admin<?> other) {
-        this.internal.merge(other);
+        this.baseTraverser.merge(other);
     }
 
     @Override
-    public <R> Admin<R> split(R r, Step<T, R> step) {
-        return new ProjectedTraverser<>(this.internal.split(r, step), this.projections);
+    public <R> Admin<R> split(final R r, final Step<T, R> step) {
+        return new ProjectedTraverser<>(this.baseTraverser.split(r, step), this.projections);
     }
 
     @Override
     public Admin<T> split() {
-        return new ProjectedTraverser<>(this.internal.split(), this.projections);
+        return new ProjectedTraverser<>(this.baseTraverser.split(), this.projections);
     }
 
     @Override
     public void addLabels(final Set<String> labels) {
-        this.internal.addLabels(labels);
+        this.baseTraverser.addLabels(labels);
     }
 
     @Override
     public void keepLabels(final Set<String> labels) {
-        this.internal.keepLabels(labels);
+        this.baseTraverser.keepLabels(labels);
     }
 
     @Override
     public void dropLabels(final Set<String> labels) {
-        this.internal.dropLabels(labels);
+        this.baseTraverser.dropLabels(labels);
     }
 
     @Override
     public void dropPath() {
-        this.internal.dropPath();
+        this.baseTraverser.dropPath();
     }
 
     @Override
     public void set(final T t) {
-        this.internal.set(t);
+        this.baseTraverser.set(t);
     }
 
     @Override
     public void incrLoops(final String stepLabel) {
-        this.internal.incrLoops(stepLabel);
+        this.baseTraverser.incrLoops(stepLabel);
     }
 
     @Override
     public void resetLoops() {
-        this.internal.resetLoops();
+        this.baseTraverser.resetLoops();
     }
 
     @Override
     public String getStepId() {
-        return this.internal.getStepId();
+        return this.baseTraverser.getStepId();
     }
 
     @Override
     public void setStepId(final String stepId) {
-        this.internal.setStepId(stepId);
+        this.baseTraverser.setStepId(stepId);
     }
 
     @Override
     public void setBulk(final long count) {
-        this.internal.setBulk(count);
+        this.baseTraverser.setBulk(count);
     }
 
     @Override
     public Admin<T> detach() {
-        this.internal = this.internal.detach();
+        this.baseTraverser = this.baseTraverser.detach();
         return this;
     }
 
     @Override
     public T attach(final Function<Attachable<T>, T> method) {
-        return this.internal.attach(method);
+        return this.baseTraverser.attach(method);
     }
 
     @Override
     public void setSideEffects(final TraversalSideEffects sideEffects) {
-        this.internal.setSideEffects(sideEffects);
+        this.baseTraverser.setSideEffects(sideEffects);
     }
 
     @Override
     public TraversalSideEffects getSideEffects() {
-        return this.internal.getSideEffects();
+        return this.baseTraverser.getSideEffects();
     }
 
     @Override
     public Set<String> getTags() {
-        return this.internal.getTags();
+        return this.baseTraverser.getTags();
     }
 
     @Override
     public T get() {
-        return this.internal.get();
+        return this.baseTraverser.get();
     }
 
     @Override
     public <S> S sack() {
-        return this.internal.sack();
+        return this.baseTraverser.sack();
     }
 
     @Override
     public <S> void sack(final S object) {
-        this.internal.sack(object);
+        this.baseTraverser.sack(object);
     }
 
     @Override
     public Path path() {
-        return this.internal.path();
+        return this.baseTraverser.path();
     }
 
     @Override
     public int loops() {
-        return this.internal.loops();
+        return this.baseTraverser.loops();
     }
 
     @Override
     public long bulk() {
-        return this.internal.bulk();
+        return this.baseTraverser.bulk();
     }
 
     @Override
     public int hashCode() {
-        return this.internal.hashCode();
+        return this.baseTraverser.hashCode();
     }
 
     @Override
     public boolean equals(final Object object) {
-        return object instanceof ProjectedTraverser && ((ProjectedTraverser) object).internal.equals(this.internal);
+        return object instanceof ProjectedTraverser && ((ProjectedTraverser) object).baseTraverser.equals(this.baseTraverser);
     }
 
     @Override
     public ProjectedTraverser<T, P> clone() {
         try {
             final ProjectedTraverser<T, P> clone = (ProjectedTraverser<T, P>) super.clone();
-            clone.internal = (Traverser.Admin<T>) this.internal.clone();
+            clone.baseTraverser = (Traverser.Admin<T>) this.baseTraverser.clone();
             return clone;
         } catch (final CloneNotSupportedException e) {
             throw new IllegalStateException(e.getMessage(), e);
@@ -198,6 +193,6 @@ public final class ProjectedTraverser<T, P> implements Traverser.Admin<T> {
     }
 
     public static <T> Traverser.Admin<T> tryUnwrap(final Traverser.Admin<T> traverser) {
-        return traverser instanceof ProjectedTraverser ? ((ProjectedTraverser) traverser).getInternal() : traverser;
+        return traverser instanceof ProjectedTraverser ? ((ProjectedTraverser) traverser).baseTraverser : traverser;
     }
 }
\ No newline at end of file

[06/13] tinkerpop git commit: Not going to touch GroupStep in this ticket. Too complicated ... will do for the next release. Minor tweaks and cleanups.

[dk...@apache.org]

Not going to touch GroupStep in this ticket. Too complicated ... will do for the next release. Minor tweaks and cleanups.


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

Branch: refs/heads/centrality-recipes
Commit: 973484d19a81ada87e95f9d3c2b0b66988f362d9
Parents: ee1ab08
Author: Marko A. Rodriguez <ok...@gmail.com>
Authored: Wed Jan 18 12:25:41 2017 -0700
Committer: Marko A. Rodriguez <ok...@gmail.com>
Committed: Wed Jan 18 12:25:41 2017 -0700

----------------------------------------------------------------------
 CHANGELOG.asciidoc                              |  2 +-
 .../traversal/step/filter/SampleGlobalStep.java |  8 +++-----
 .../traversal/step/map/OrderGlobalStep.java     | 21 ++++++++------------
 3 files changed, 12 insertions(+), 19 deletions(-)
----------------------------------------------------------------------


http://git-wip-us.apache.org/repos/asf/tinkerpop/blob/973484d1/CHANGELOG.asciidoc
----------------------------------------------------------------------
diff --git a/CHANGELOG.asciidoc b/CHANGELOG.asciidoc
index 052257f..25ff3e9 100644
--- a/CHANGELOG.asciidoc
+++ b/CHANGELOG.asciidoc
@@ -27,7 +27,7 @@ TinkerPop 3.2.4 (Release Date: NOT OFFICIALLY RELEASED YET)
 ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
 
 * Added `ProjectedTraverser` which wraps a traverser with a `List<Object>` of projected data.
-* `OrderGlobalStep` and `SampleGlobalStep` now emit traversers with their `by()`-projections and thus, can move beyond the local star graph.
+* `OrderGlobalStep` and `SampleGlobalStep` use `ProjectedTraverser` and now can work up to the local star graph in OLAP.
 * SASL negotiation supports both a byte array and Base64 encoded bytes as a string for authentication to Gremlin Server.
 * Deprecated `TinkerIoRegistry` replacing it with the more consistently named `TinkerIoRegistryV1d0`.
 * Made error messaging more consistent during result iteration timeouts in Gremlin Server.

http://git-wip-us.apache.org/repos/asf/tinkerpop/blob/973484d1/gremlin-core/src/main/java/org/apache/tinkerpop/gremlin/process/traversal/step/filter/SampleGlobalStep.java
----------------------------------------------------------------------
diff --git a/gremlin-core/src/main/java/org/apache/tinkerpop/gremlin/process/traversal/step/filter/SampleGlobalStep.java b/gremlin-core/src/main/java/org/apache/tinkerpop/gremlin/process/traversal/step/filter/SampleGlobalStep.java
index 2b2cf20..28d2fb4 100644
--- a/gremlin-core/src/main/java/org/apache/tinkerpop/gremlin/process/traversal/step/filter/SampleGlobalStep.java
+++ b/gremlin-core/src/main/java/org/apache/tinkerpop/gremlin/process/traversal/step/filter/SampleGlobalStep.java
@@ -66,10 +66,8 @@ public final class SampleGlobalStep<S> extends CollectingBarrierStep<S> implemen
 
     @Override
     public void processAllStarts() {
-        if (this.starts.hasNext()) {
-            while (this.starts.hasNext()) {
-                this.traverserSet.add(this.createProjectedTraverser(this.starts.next()));
-            }
+        while (this.starts.hasNext()) {
+            this.traverserSet.add(this.createProjectedTraverser(this.starts.next()));
         }
     }
 
@@ -97,7 +95,7 @@ public final class SampleGlobalStep<S> extends CollectingBarrierStep<S> implemen
                         runningWeight = runningWeight + currentWeight;
                         if (RANDOM.nextDouble() <= ((runningWeight / totalWeight))) {
                             final Traverser.Admin<S> split = s.split();
-                            split.setBulk(1l);
+                            split.setBulk(1L);
                             sampledSet.add(split);
                             runningAmountToSample++;
                             totalWeight = totalWeight - currentWeight;

http://git-wip-us.apache.org/repos/asf/tinkerpop/blob/973484d1/gremlin-core/src/main/java/org/apache/tinkerpop/gremlin/process/traversal/step/map/OrderGlobalStep.java
----------------------------------------------------------------------
diff --git a/gremlin-core/src/main/java/org/apache/tinkerpop/gremlin/process/traversal/step/map/OrderGlobalStep.java b/gremlin-core/src/main/java/org/apache/tinkerpop/gremlin/process/traversal/step/map/OrderGlobalStep.java
index 55d8650..e5c5834 100644
--- a/gremlin-core/src/main/java/org/apache/tinkerpop/gremlin/process/traversal/step/map/OrderGlobalStep.java
+++ b/gremlin-core/src/main/java/org/apache/tinkerpop/gremlin/process/traversal/step/map/OrderGlobalStep.java
@@ -53,7 +53,6 @@ public final class OrderGlobalStep<S, C extends Comparable> extends CollectingBa
     private List<Pair<Traversal.Admin<S, C>, Comparator<C>>> comparators = new ArrayList<>();
     private MultiComparator<C> multiComparator = null;
     private long limit = Long.MAX_VALUE;
-    private boolean isShuffle = false;
 
     public OrderGlobalStep(final Traversal.Admin traversal) {
         super(traversal);
@@ -61,7 +60,9 @@ public final class OrderGlobalStep<S, C extends Comparable> extends CollectingBa
 
     @Override
     public void barrierConsumer(final TraverserSet<S> traverserSet) {
-        if (this.isShuffle)
+        if (null == this.multiComparator) this.multiComparator = this.createMultiComparator();
+        //
+        if (this.multiComparator.isShuffle())
             traverserSet.shuffle();
         else
             traverserSet.sort((Comparator) this.multiComparator);
@@ -69,12 +70,8 @@ public final class OrderGlobalStep<S, C extends Comparable> extends CollectingBa
 
     @Override
     public void processAllStarts() {
-        if (null == this.multiComparator)
-            this.multiComparator = this.createMultiComparator();
-        if (this.starts.hasNext()) {
-            while (this.starts.hasNext()) {
-                this.traverserSet.add(this.createProjectedTraverser(this.starts.next()));
-            }
+        while (this.starts.hasNext()) {
+            this.traverserSet.add(this.createProjectedTraverser(this.starts.next()));
         }
     }
 
@@ -88,7 +85,6 @@ public final class OrderGlobalStep<S, C extends Comparable> extends CollectingBa
 
     @Override
     public void addComparator(final Traversal.Admin<S, C> traversal, final Comparator<C> comparator) {
-        this.isShuffle = Order.shuffle == (Comparator) comparator;
         this.comparators.add(new Pair<>(this.integrateChild(traversal), comparator));
     }
 
@@ -149,13 +145,12 @@ public final class OrderGlobalStep<S, C extends Comparable> extends CollectingBa
 
     @Override
     public MemoryComputeKey<TraverserSet<S>> getMemoryComputeKey() {
-        if (null == this.multiComparator)
-            this.multiComparator = this.createMultiComparator();
+        if (null == this.multiComparator) this.multiComparator = this.createMultiComparator();
         return MemoryComputeKey.of(this.getId(), new OrderBiOperator<>(this.limit, this.multiComparator), false, true);
     }
 
-    private final ProjectedTraverser<S,Object> createProjectedTraverser(final Traverser.Admin<S> traverser) {
-        final List<Object> projections = new ArrayList<>(this.comparators.size());
+    private final ProjectedTraverser<S, C> createProjectedTraverser(final Traverser.Admin<S> traverser) {
+        final List<C> projections = new ArrayList<>(this.comparators.size());
         for (final Pair<Traversal.Admin<S, C>, Comparator<C>> pair : this.comparators) {
             projections.add(TraversalUtil.apply(traverser, pair.getValue0()));
         }

[11/13] tinkerpop git commit: updated CHANGELOG.

[dk...@apache.org]

updated CHANGELOG.


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

Branch: refs/heads/centrality-recipes
Commit: 6002299925e7ef68275b9576331aac1194642bef
Parents: d54b490
Author: Marko A. Rodriguez <ok...@gmail.com>
Authored: Thu Jan 19 10:16:43 2017 -0700
Committer: Marko A. Rodriguez <ok...@gmail.com>
Committed: Thu Jan 19 10:16:43 2017 -0700

----------------------------------------------------------------------
 CHANGELOG.asciidoc | 1 +
 1 file changed, 1 insertion(+)
----------------------------------------------------------------------


http://git-wip-us.apache.org/repos/asf/tinkerpop/blob/60022999/CHANGELOG.asciidoc
----------------------------------------------------------------------
diff --git a/CHANGELOG.asciidoc b/CHANGELOG.asciidoc
index 5f28790..fb0f8da 100644
--- a/CHANGELOG.asciidoc
+++ b/CHANGELOG.asciidoc
@@ -26,6 +26,7 @@ image::https://raw.githubusercontent.com/apache/tinkerpop/master/docs/static/ima
 TinkerPop 3.2.4 (Release Date: NOT OFFICIALLY RELEASED YET)
 ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
 
+* Fixed a bug associated with user-provided maps and `GroupSideEffectStep`.
 * `GroupBiOperator` no longer maintains a detached traversal and thus, no more side-effect related OLAP inconsistencies.
 * Added `ProjectedTraverser` which wraps a traverser with a `List<Object>` of projected data.
 * Fixed an optimization bug in `CollectionBarrierSteps` where the barrier was being consumed on each `addBarrier()`.

[13/13] tinkerpop git commit: Updated the closeness and betweeness centrality recipes.

[dk...@apache.org]

Updated the closeness and betweeness centrality recipes.

1) added a disclaimer that both recipes should be used with care (only on small (sub)graphs)
2) optimized the execution plan
3) took multiple shortest paths between a pair of vertices into account
4) updated the sample graph to one that has multiple shortest paths between certain pairs of vertices


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

Branch: refs/heads/centrality-recipes
Commit: 5577ea564e8a9634d3b0699cbddee59b039db90f
Parents: 8ad2911
Author: Daniel Kuppitz <da...@hotmail.com>
Authored: Fri Jan 20 16:36:42 2017 +0100
Committer: Daniel Kuppitz <da...@hotmail.com>
Committed: Fri Jan 20 16:41:09 2017 +0100

----------------------------------------------------------------------
 docs/src/recipes/centrality.asciidoc | 121 +++++++++++++++++-------------
 1 file changed, 67 insertions(+), 54 deletions(-)
----------------------------------------------------------------------


http://git-wip-us.apache.org/repos/asf/tinkerpop/blob/5577ea56/docs/src/recipes/centrality.asciidoc
----------------------------------------------------------------------
diff --git a/docs/src/recipes/centrality.asciidoc b/docs/src/recipes/centrality.asciidoc
index cbce418..f6fba30 100644
--- a/docs/src/recipes/centrality.asciidoc
+++ b/docs/src/recipes/centrality.asciidoc
@@ -67,43 +67,48 @@ image:betweeness-example.png[width=600]
 
 [gremlin-groovy ]
 ----
-g.addV('name','a').as('a').
-  addV('name','b').as('b').
-  addV('name','c').as('c').
-  addV('name','d').as('d').
-  addV('name','e').as('e').
+g.addV(id,'A').as('a').
+  addV(id,'B').as('b').
+  addV(id,'C').as('c').
+  addV(id,'D').as('d').
+  addV(id,'E').as('e').
+  addV(id,'F').as('f').
   addE('next').from('a').to('b').
   addE('next').from('b').to('c').
-  addE('next').from('c').to('d').
-  addE('next').from('d').to('e').iterate()
-g.withSack(0).V().store("x").repeat(both().simplePath()).emit().path(). <1>
-  group().by(project("a","b").by(limit(local, 1)).                      <2>
-                              by(tail(local, 1))).
-          by(order().by(count(local))).                                 <3>
-          select(values).as("shortestPaths").                           <4>
-          select("x").unfold().as("v").                                 <5>
-          select("shortestPaths").                                      <6>
-            map(unfold().filter(unfold().where(eq("v"))).count()).      <7>
-            sack(sum).sack().as("betweeness").                          <8>
-          select("v","betweeness")
+  addE('next').from('b').to('d').
+  addE('next').from('c').to('e').
+  addE('next').from('d').to('e').
+  addE('next').from('e').to('f').iterate()
+g.V().as("v").                                                                  <1>
+  repeat(both().simplePath().as("v")).emit().                                   <2>
+  filter(project("x","y","z").by(select(first, "v")).                           <3>
+                              by(select(last, "v")).
+                              by(select(all, "v").count(local)).as("triple").
+         coalesce(select("x","y").as("a").                                      <4>
+                    select("triples").unfold().as("t").
+                    select("x","y").where(eq("a")).
+                    select("t"),
+                  store("triples")).                                            <5>
+         select("z").as("length").
+         select("triple").select("z").where(eq("length"))).                     <6>
+  select(all, "v").unfold().                                                    <7>
+  groupCount().next()                                                           <8>
 ----
 
-<1> Defines a Gremlin link:http://tinkerpop.apache.org/docs/x.y.z/reference/#sack-step[sack] with a value of zero,
-which represents the initial betweeness score for each vertex, and traverses on both incoming and outgoing edges
-avoiding <<cycle-detection, cyclic paths>>.
-<2> Group each path by the first and last vertex.
-<3> Reduce the list of paths to the shortest path between the first and last vertex by ordering on their lengths.
-<4> Recall that at this point, there is a `Map` keyed by first and last vertex and with a value of just the shortest
-path. Extract the shortest path with `select(values)`, since that's the only portion required for the remainder of
-the traversal.
-<5> The "x" key contains the list of vertices stored from step 1 - unfold that list into "v" for later use. This step
-will unwrap the vertex that is stored in the `Traverser` as
-link:http://tinkerpop.apache.org/javadocs/x.y.z/full/org/apache/tinkerpop/gremlin/process/traversal/step/util/BulkSet.html[BulkSet]
-so that it can be used directly in the `Traversal`.
-<6> Iterate the set of shortest paths. At this point, it is worth noting that the traversal is iterating each vertex
-in "v" and for each vertex in "v" it is iterating each `Path` in "shortestpaths".
-<7> For each path, transform it to a count of the number of times that "v" from step 5 is encountered.
-<8> Sum the counts for each vertex using `sack()`, normalize the value and label it as the "betweeness" to be the score.
+<1> Starting from each vertex in the graph...
+<2> ...traverse on both - incoming and outgoing - edges, avoiding <<cycle-detection, cyclic paths>>.
+<3> Create a triple consisting of the first vertex, the last vertex and the length of the path between them.
+<4> Determine whether a path between those two vertices was already found.
+<5> If this is the first path between the two vertices, store the triple in an internal collection named "triples".
+<6> Keep only those paths between a pair of vertices that have the same length as the first path that was found between them.
+<7> Select all shortest paths and unfold them.
+<8> Count the number of occurrences of each vertex, which is ultimately its betweeness score.
+
+WARNING: Since the betweeness centrality algorithm requires the shortest path between any pair of vertices in the graph,
+its practical applications are very limited. It's recommended to use this algorithm only on small subgraphs (graphs like
+the link:http://tinkerpop.apache.org/docs/current/reference/#grateful-dead[Grateful Dead graph] with only 808 vertices
+and 8049 edges already require a massive amount of compute resources to determine the shortest paths between all vertex
+pairs).
 
 [[closeness-centrality]]
 Closeness Centrality
@@ -114,28 +119,36 @@ other reachable vertices in the graph. The following examples use the modern toy
 
 [gremlin-groovy,modern]
 ----
-g.withSack(1f).V().repeat(both().simplePath()).emit().path().                    <1>
-  group().by(project("a","b").by(limit(local, 1)).                               <2>
-                              by(tail(local, 1))).
-          by(order().by(count(local))).                                          <3>
-  select(values).unfold().                                                       <4>
-  project("v","length").
-    by(limit(local, 1)).                                                         <5>
-    by(count(local).sack(div).sack()).                                           <6>
-  group().by(select("v")).by(select("length").sum())                             <7>
+g = TinkerFactory.createModern().traversal()
+g.withSack(1f).V().as("v").                                                     <1>
+  repeat(both().simplePath().as("v")).emit().                                   <2>
+  filter(project("x","y","z").by(select(first, "v")).                           <3>
+                              by(select(last, "v")).
+                              by(select(all, "v").count(local)).as("triple").
+         coalesce(select("x","y").as("a").                                      <4>
+                    select("triples").unfold().as("t").
+                    select("x","y").where(eq("a")).
+                    select("t"),
+                  store("triples")).                                            <5>
+         select("z").as("length").
+         select("triple").select("z").where(eq("length"))).                     <6>
+  group().by(select(first, "v")).                                               <7>
+          by(select(all, "v").count(local).sack(div).sack().sum()).next()
 ----
 
-<1> Defines a Gremlin link:http://tinkerpop.apache.org/docs/x.y.z/reference/#sack-step[sack] with a value of one,
-and traverses on both incoming and outgoing edges avoiding <<cycle-detection, cyclic paths>>.
-<2> Group each path by the first and last vertex.
-<3> Reduce the list of paths to the shortest path between the first and last vertex by ordering on their lengths.
-<4> Recall that at this point, there is a `Map` keyed by first and last vertex and with a value of just the shortest
-path. Extract the shortest path with `select(values)`, since that's the only portion required for the remainder of
-the traversal.
-<5> The first `by()` modulator for `project()` extracts the first vertex in the path.
-<6> The second `by()` modulator for `project()` extracts the path length and divides that distance by the value of
-the `sack()` which was initialized to 1 at the start of the traversal.
-<7> Group the resulting `Map` objects on "v" and sum their lengths to get the centrality score for each.
+<1> Defines a Gremlin link:http://tinkerpop.apache.org/docs/x.y.z/reference/#sack-step[sack] with a value of one.
+<2> Traverses on both - incoming and outgoing - edges, avoiding <<cycle-detection, cyclic paths>>.
+<3> Create a triple consisting of the first vertex, the last vertex and the length of the path between them.
+<4> Determine whether a path between those two vertices was already found.
+<5> If this is the first path between the two vertices, store the triple in an internal collection named "triples".
+<6> Keep only those paths between a pair of vertices that have the same length as the first path that was found between them.
+<7> For each vertex divide 1 by the product of the lengths of all shortest paths that start with this particular vertex.
+
+WARNING: Since the closeness centrality algorithm requires the shortest path between any pair of vertices in the graph,
+its practical applications are very limited. It's recommended to use this algorithm only on small subgraphs (graphs like
+the link:http://tinkerpop.apache.org/docs/current/reference/#grateful-dead[Grateful Dead graph] with only 808 vertices
+and 8049 edges already require a massive amount of compute resources to determine the shortest paths between all vertex
+pairs).
 
 [[eigenvector-centrality]]
 Eigenvector Centrality
@@ -165,4 +178,4 @@ link:http://tinkerpop.apache.org/docs/current/reference/#timelimit-step[time lim
 traversal from taking longer than one hundred milliseconds to execute (the previous example takes considerably longer
 than that). While the answer provided with the `timeLimit()` is not the absolute ranking, it does provide a relative
 ranking that closely matches the absolute one. The use of `timeLimit()` in certain algorithms (e.g. recommendations)
-can shorten the time required to get a reasonable and usable result.
\ No newline at end of file
+can shorten the time required to get a reasonable and usable result.

[03/13] tinkerpop git commit: Removed a PathProcessor.ID constraint from ComputerVerificationStrategy. Moreover, sampling and ordering is more efficient as the projected data is co-located with the traverser in the new ProjectedTraverser wrapper. Going t

[dk...@apache.org]

Removed a PathProcessor.ID constraint from ComputerVerificationStrategy. Moreover, sampling and ordering is more efficient as the projected data is co-located with the traverser in the new ProjectedTraverser wrapper. Going to leave it at this for tp32/... Moving forward, we can make it so we don't need to DetachFactory.detach(true) for CollectingBarrierStep by maintaining 'future data.' Its complicated and I don't want to introduce potential bugs.


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

Branch: refs/heads/centrality-recipes
Commit: b2f0c57df6fd9191904213622ae718a0790d7a03
Parents: 5045f67
Author: Marko A. Rodriguez <ok...@gmail.com>
Authored: Wed Jan 18 11:07:32 2017 -0700
Committer: Marko A. Rodriguez <ok...@gmail.com>
Committed: Wed Jan 18 11:07:32 2017 -0700

----------------------------------------------------------------------
 .../traversal/step/filter/SampleGlobalStep.java | 19 ++++++++++++--
 .../traversal/step/map/OrderGlobalStep.java     | 27 +++++---------------
 .../step/util/CollectingBarrierStep.java        | 24 ++++++++++-------
 .../ComputerVerificationStrategy.java           |  8 ------
 .../traversal/traverser/ProjectedTraverser.java | 16 +++++++-----
 .../gremlin/util/function/MultiComparator.java  | 14 +++++++---
 6 files changed, 60 insertions(+), 48 deletions(-)
----------------------------------------------------------------------


http://git-wip-us.apache.org/repos/asf/tinkerpop/blob/b2f0c57d/gremlin-core/src/main/java/org/apache/tinkerpop/gremlin/process/traversal/step/filter/SampleGlobalStep.java
----------------------------------------------------------------------
diff --git a/gremlin-core/src/main/java/org/apache/tinkerpop/gremlin/process/traversal/step/filter/SampleGlobalStep.java b/gremlin-core/src/main/java/org/apache/tinkerpop/gremlin/process/traversal/step/filter/SampleGlobalStep.java
index 0a4da58..2b2cf20 100644
--- a/gremlin-core/src/main/java/org/apache/tinkerpop/gremlin/process/traversal/step/filter/SampleGlobalStep.java
+++ b/gremlin-core/src/main/java/org/apache/tinkerpop/gremlin/process/traversal/step/filter/SampleGlobalStep.java
@@ -24,6 +24,7 @@ import org.apache.tinkerpop.gremlin.process.traversal.lambda.ConstantTraversal;
 import org.apache.tinkerpop.gremlin.process.traversal.step.ByModulating;
 import org.apache.tinkerpop.gremlin.process.traversal.step.TraversalParent;
 import org.apache.tinkerpop.gremlin.process.traversal.step.util.CollectingBarrierStep;
+import org.apache.tinkerpop.gremlin.process.traversal.traverser.ProjectedTraverser;
 import org.apache.tinkerpop.gremlin.process.traversal.traverser.TraverserRequirement;
 import org.apache.tinkerpop.gremlin.process.traversal.traverser.util.TraverserSet;
 import org.apache.tinkerpop.gremlin.process.traversal.util.TraversalUtil;
@@ -64,6 +65,15 @@ public final class SampleGlobalStep<S> extends CollectingBarrierStep<S> implemen
     }
 
     @Override
+    public void processAllStarts() {
+        if (this.starts.hasNext()) {
+            while (this.starts.hasNext()) {
+                this.traverserSet.add(this.createProjectedTraverser(this.starts.next()));
+            }
+        }
+    }
+
+    @Override
     public void barrierConsumer(final TraverserSet<S> traverserSet) {
         // return the entire traverser set if the set is smaller than the amount to sample
         if (traverserSet.bulkSize() <= this.amountToSample)
@@ -71,7 +81,7 @@ public final class SampleGlobalStep<S> extends CollectingBarrierStep<S> implemen
         //////////////// else sample the set
         double totalWeight = 0.0d;
         for (final Traverser.Admin<S> s : traverserSet) {
-            totalWeight = totalWeight + TraversalUtil.apply(s, this.probabilityTraversal).doubleValue() * s.bulk();
+            totalWeight = totalWeight + (((ProjectedTraverser<S, Number>) s).getProjections().get(0).doubleValue() * s.bulk());
         }
         ///////
         final TraverserSet<S> sampledSet = new TraverserSet<>();
@@ -82,7 +92,7 @@ public final class SampleGlobalStep<S> extends CollectingBarrierStep<S> implemen
             for (final Traverser.Admin<S> s : traverserSet) {
                 long sampleBulk = sampledSet.contains(s) ? sampledSet.get(s).bulk() : 0;
                 if (sampleBulk < s.bulk()) {
-                    final double currentWeight = TraversalUtil.apply(s, this.probabilityTraversal).doubleValue();
+                    final double currentWeight = ((ProjectedTraverser<S, Number>) s).getProjections().get(0).doubleValue();
                     for (int i = 0; i < (s.bulk() - sampleBulk); i++) {
                         runningWeight = runningWeight + currentWeight;
                         if (RANDOM.nextDouble() <= ((runningWeight / totalWeight))) {
@@ -104,6 +114,11 @@ public final class SampleGlobalStep<S> extends CollectingBarrierStep<S> implemen
         traverserSet.addAll(sampledSet);
     }
 
+
+    private final ProjectedTraverser<S, Number> createProjectedTraverser(final Traverser.Admin<S> traverser) {
+        return new ProjectedTraverser<>(traverser, Collections.singletonList(TraversalUtil.apply(traverser, this.probabilityTraversal)));
+    }
+
     @Override
     public Set<TraverserRequirement> getRequirements() {
         return this.getSelfAndChildRequirements(TraverserRequirement.BULK);

http://git-wip-us.apache.org/repos/asf/tinkerpop/blob/b2f0c57d/gremlin-core/src/main/java/org/apache/tinkerpop/gremlin/process/traversal/step/map/OrderGlobalStep.java
----------------------------------------------------------------------
diff --git a/gremlin-core/src/main/java/org/apache/tinkerpop/gremlin/process/traversal/step/map/OrderGlobalStep.java b/gremlin-core/src/main/java/org/apache/tinkerpop/gremlin/process/traversal/step/map/OrderGlobalStep.java
index 9c071f1..55d8650 100644
--- a/gremlin-core/src/main/java/org/apache/tinkerpop/gremlin/process/traversal/step/map/OrderGlobalStep.java
+++ b/gremlin-core/src/main/java/org/apache/tinkerpop/gremlin/process/traversal/step/map/OrderGlobalStep.java
@@ -73,22 +73,11 @@ public final class OrderGlobalStep<S, C extends Comparable> extends CollectingBa
             this.multiComparator = this.createMultiComparator();
         if (this.starts.hasNext()) {
             while (this.starts.hasNext()) {
-                this.traverserSet.add(this.createOrderedTraverser(this.starts.next()));
+                this.traverserSet.add(this.createProjectedTraverser(this.starts.next()));
             }
-            this.barrierConsumer(this.traverserSet);
         }
     }
 
-    @Override
-    public Traverser.Admin<S> processNextStart() {
-        if (!this.traverserSet.isEmpty()) {
-            return this.traverserSet.remove();
-        } else if (this.starts.hasNext()) {
-            this.processAllStarts();
-        }
-        return ((ProjectedTraverser) this.traverserSet.remove()).getInternal();
-    }
-
     public void setLimit(final long limit) {
         this.limit = limit;
     }
@@ -162,18 +151,18 @@ public final class OrderGlobalStep<S, C extends Comparable> extends CollectingBa
     public MemoryComputeKey<TraverserSet<S>> getMemoryComputeKey() {
         if (null == this.multiComparator)
             this.multiComparator = this.createMultiComparator();
-        return MemoryComputeKey.of(this.getId(), new OrderBiOperator<>(this.limit, this.isShuffle, this.multiComparator), false, true);
+        return MemoryComputeKey.of(this.getId(), new OrderBiOperator<>(this.limit, this.multiComparator), false, true);
     }
 
-    private ProjectedTraverser<S> createOrderedTraverser(final Traverser.Admin<S> traverser) {
+    private final ProjectedTraverser<S,Object> createProjectedTraverser(final Traverser.Admin<S> traverser) {
         final List<Object> projections = new ArrayList<>(this.comparators.size());
         for (final Pair<Traversal.Admin<S, C>, Comparator<C>> pair : this.comparators) {
             projections.add(TraversalUtil.apply(traverser, pair.getValue0()));
         }
-        return new ProjectedTraverser<S>(traverser, projections);
+        return new ProjectedTraverser<>(traverser, projections);
     }
 
-    private MultiComparator<C> createMultiComparator() {
+    private final MultiComparator<C> createMultiComparator() {
         final List<Comparator<C>> list = new ArrayList<>(this.comparators.size());
         for (final Pair<Traversal.Admin<S, C>, Comparator<C>> pair : this.comparators) {
             list.add(pair.getValue1());
@@ -186,16 +175,14 @@ public final class OrderGlobalStep<S, C extends Comparable> extends CollectingBa
     public static final class OrderBiOperator<S> implements BinaryOperator<TraverserSet<S>>, Serializable {
 
         private long limit;
-        private boolean isShuffle;
         private MultiComparator comparator;
 
         private OrderBiOperator() {
             // for serializers that need a no-arg constructor
         }
 
-        public OrderBiOperator(final long limit, final boolean isShuffle, final MultiComparator multiComparator) {
+        public OrderBiOperator(final long limit, final MultiComparator multiComparator) {
             this.limit = limit;
-            this.isShuffle = isShuffle;
             this.comparator = multiComparator;
         }
 
@@ -203,7 +190,7 @@ public final class OrderGlobalStep<S, C extends Comparable> extends CollectingBa
         public TraverserSet<S> apply(final TraverserSet<S> setA, final TraverserSet<S> setB) {
             setA.addAll(setB);
             if (Long.MAX_VALUE != this.limit && setA.bulkSize() > this.limit) {
-                if (this.isShuffle)
+                if (this.comparator.isShuffle())
                     setA.shuffle();
                 else
                     setA.sort(this.comparator);

http://git-wip-us.apache.org/repos/asf/tinkerpop/blob/b2f0c57d/gremlin-core/src/main/java/org/apache/tinkerpop/gremlin/process/traversal/step/util/CollectingBarrierStep.java
----------------------------------------------------------------------
diff --git a/gremlin-core/src/main/java/org/apache/tinkerpop/gremlin/process/traversal/step/util/CollectingBarrierStep.java b/gremlin-core/src/main/java/org/apache/tinkerpop/gremlin/process/traversal/step/util/CollectingBarrierStep.java
index b0cce80..f99201d 100644
--- a/gremlin-core/src/main/java/org/apache/tinkerpop/gremlin/process/traversal/step/util/CollectingBarrierStep.java
+++ b/gremlin-core/src/main/java/org/apache/tinkerpop/gremlin/process/traversal/step/util/CollectingBarrierStep.java
@@ -23,11 +23,13 @@ import org.apache.tinkerpop.gremlin.process.traversal.Operator;
 import org.apache.tinkerpop.gremlin.process.traversal.Traversal;
 import org.apache.tinkerpop.gremlin.process.traversal.Traverser;
 import org.apache.tinkerpop.gremlin.process.traversal.step.Barrier;
+import org.apache.tinkerpop.gremlin.process.traversal.traverser.ProjectedTraverser;
 import org.apache.tinkerpop.gremlin.process.traversal.traverser.TraverserRequirement;
 import org.apache.tinkerpop.gremlin.process.traversal.traverser.util.TraverserSet;
 import org.apache.tinkerpop.gremlin.process.traversal.util.FastNoSuchElementException;
 import org.apache.tinkerpop.gremlin.structure.util.StringFactory;
 import org.apache.tinkerpop.gremlin.structure.util.detached.DetachedFactory;
+import org.apache.tinkerpop.gremlin.util.iterator.IteratorUtils;
 
 import java.util.Collections;
 import java.util.NoSuchElementException;
@@ -40,7 +42,8 @@ import java.util.function.BinaryOperator;
 public abstract class CollectingBarrierStep<S> extends AbstractStep<S, S> implements Barrier<TraverserSet<S>> {
 
     protected TraverserSet<S> traverserSet = new TraverserSet<>();
-    protected int maxBarrierSize;
+    private int maxBarrierSize;
+    private boolean barrierConsumed = false;
 
     public CollectingBarrierStep(final Traversal.Admin traversal) {
         this(traversal, Integer.MAX_VALUE);
@@ -68,7 +71,6 @@ public abstract class CollectingBarrierStep<S> extends AbstractStep<S, S> implem
                     this.traverserSet.add(this.starts.next());
                 }
             }
-            this.barrierConsumer(this.traverserSet);
         }
     }
 
@@ -85,11 +87,10 @@ public abstract class CollectingBarrierStep<S> extends AbstractStep<S, S> implem
             throw FastNoSuchElementException.instance();
         else {
             final TraverserSet<S> temp = new TraverserSet<>();
-            this.traverserSet.iterator().forEachRemaining(t -> {
+            IteratorUtils.removeOnNext(this.traverserSet.iterator()).forEachRemaining(t -> {
                 DetachedFactory.detach(t, true); // this should be dynamic
                 temp.add(t);
             });
-            this.traverserSet.clear();
             return temp;
         }
     }
@@ -98,23 +99,28 @@ public abstract class CollectingBarrierStep<S> extends AbstractStep<S, S> implem
     public void addBarrier(final TraverserSet<S> barrier) {
         this.traverserSet = barrier;
         this.traverserSet.forEach(traverser -> traverser.setSideEffects(this.getTraversal().getSideEffects()));
-        this.barrierConsumer(this.traverserSet);
+        this.barrierConsumed = false;
     }
 
     @Override
     public Traverser.Admin<S> processNextStart() {
-        if (!this.traverserSet.isEmpty()) {
-            return this.traverserSet.remove();
-        } else if (this.starts.hasNext()) {
+        if (this.traverserSet.isEmpty() && this.starts.hasNext()) {
             this.processAllStarts();
+            this.barrierConsumed = false;
+        }
+        //
+        if (!this.barrierConsumed) {
+            this.barrierConsumer(this.traverserSet);
+            this.barrierConsumed = true;
         }
-        return this.traverserSet.remove();
+        return ProjectedTraverser.tryUnwrap(this.traverserSet.remove());
     }
 
     @Override
     public CollectingBarrierStep<S> clone() {
         final CollectingBarrierStep<S> clone = (CollectingBarrierStep<S>) super.clone();
         clone.traverserSet = new TraverserSet<>();
+        clone.barrierConsumed = false;
         return clone;
     }
 

http://git-wip-us.apache.org/repos/asf/tinkerpop/blob/b2f0c57d/gremlin-core/src/main/java/org/apache/tinkerpop/gremlin/process/traversal/strategy/verification/ComputerVerificationStrategy.java
----------------------------------------------------------------------
diff --git a/gremlin-core/src/main/java/org/apache/tinkerpop/gremlin/process/traversal/strategy/verification/ComputerVerificationStrategy.java b/gremlin-core/src/main/java/org/apache/tinkerpop/gremlin/process/traversal/strategy/verification/ComputerVerificationStrategy.java
index 5777adb..ef9b95c 100644
--- a/gremlin-core/src/main/java/org/apache/tinkerpop/gremlin/process/traversal/strategy/verification/ComputerVerificationStrategy.java
+++ b/gremlin-core/src/main/java/org/apache/tinkerpop/gremlin/process/traversal/strategy/verification/ComputerVerificationStrategy.java
@@ -28,11 +28,9 @@ import org.apache.tinkerpop.gremlin.process.traversal.step.GraphComputing;
 import org.apache.tinkerpop.gremlin.process.traversal.step.Mutating;
 import org.apache.tinkerpop.gremlin.process.traversal.step.PathProcessor;
 import org.apache.tinkerpop.gremlin.process.traversal.step.TraversalParent;
-import org.apache.tinkerpop.gremlin.process.traversal.step.filter.SampleGlobalStep;
 import org.apache.tinkerpop.gremlin.process.traversal.step.map.GraphStep;
 import org.apache.tinkerpop.gremlin.process.traversal.step.sideEffect.InjectStep;
 import org.apache.tinkerpop.gremlin.process.traversal.step.sideEffect.SubgraphStep;
-import org.apache.tinkerpop.gremlin.process.traversal.step.util.CollectingBarrierStep;
 import org.apache.tinkerpop.gremlin.process.traversal.step.util.EmptyStep;
 import org.apache.tinkerpop.gremlin.process.traversal.step.util.ProfileStep;
 import org.apache.tinkerpop.gremlin.process.traversal.strategy.AbstractTraversalStrategy;
@@ -87,12 +85,6 @@ public final class ComputerVerificationStrategy extends AbstractTraversalStrateg
                     throw new VerificationException("Local traversals may not traverse past the local star-graph on GraphComputer: " + traversalOptional.get(), traversal);
             }
 
-            // sample step use can only operate on the element and its properties (no incidences)
-            if (step instanceof SampleGlobalStep) {
-                if (((TraversalParent) step).getLocalChildren().stream().filter(t -> !TraversalHelper.isLocalProperties(t)).findAny().isPresent())
-                    throw new VerificationException("The following barrier step can not process the incident edges of a vertex on GraphComputer: " + step, traversal);
-            }
-
             // this is a problem because sideEffect.merge() is transient on the OLAP reduction
             if (TraversalHelper.getRootTraversal(traversal).getTraverserRequirements().contains(TraverserRequirement.ONE_BULK))
                 throw new VerificationException("One bulk is currently not supported on GraphComputer: " + step, traversal);

http://git-wip-us.apache.org/repos/asf/tinkerpop/blob/b2f0c57d/gremlin-core/src/main/java/org/apache/tinkerpop/gremlin/process/traversal/traverser/ProjectedTraverser.java
----------------------------------------------------------------------
diff --git a/gremlin-core/src/main/java/org/apache/tinkerpop/gremlin/process/traversal/traverser/ProjectedTraverser.java b/gremlin-core/src/main/java/org/apache/tinkerpop/gremlin/process/traversal/traverser/ProjectedTraverser.java
index 67e723a..5cecdc4 100644
--- a/gremlin-core/src/main/java/org/apache/tinkerpop/gremlin/process/traversal/traverser/ProjectedTraverser.java
+++ b/gremlin-core/src/main/java/org/apache/tinkerpop/gremlin/process/traversal/traverser/ProjectedTraverser.java
@@ -32,16 +32,16 @@ import java.util.function.Function;
 /**
  * @author Marko A. Rodriguez (http://markorodriguez.com)
  */
-public final class ProjectedTraverser<T> implements Traverser.Admin<T> {
+public final class ProjectedTraverser<T, P> implements Traverser.Admin<T> {
 
     private Traverser.Admin<T> internal;
-    private List<Object> projections;
+    private List<P> projections;
 
     private ProjectedTraverser() {
         // for serialization
     }
 
-    public ProjectedTraverser(final Traverser.Admin<T> internal, final List<Object> projections) {
+    public ProjectedTraverser(final Traverser.Admin<T> internal, final List<P> projections) {
         this.internal = internal;
         this.projections = projections;
     }
@@ -51,7 +51,7 @@ public final class ProjectedTraverser<T> implements Traverser.Admin<T> {
         return this.internal;
     }
 
-    public List<Object> getProjections() {
+    public List<P> getProjections() {
         return this.projections;
     }
 
@@ -187,13 +187,17 @@ public final class ProjectedTraverser<T> implements Traverser.Admin<T> {
     }
 
     @Override
-    public ProjectedTraverser<T> clone() {
+    public ProjectedTraverser<T, P> clone() {
         try {
-            final ProjectedTraverser<T> clone = (ProjectedTraverser<T>) super.clone();
+            final ProjectedTraverser<T, P> clone = (ProjectedTraverser<T, P>) super.clone();
             clone.internal = (Traverser.Admin<T>) this.internal.clone();
             return clone;
         } catch (final CloneNotSupportedException e) {
             throw new IllegalStateException(e.getMessage(), e);
         }
     }
+
+    public static <T> Traverser.Admin<T> tryUnwrap(final Traverser.Admin<T> traverser) {
+        return traverser instanceof ProjectedTraverser ? ((ProjectedTraverser) traverser).getInternal() : traverser;
+    }
 }
\ No newline at end of file

http://git-wip-us.apache.org/repos/asf/tinkerpop/blob/b2f0c57d/gremlin-core/src/main/java/org/apache/tinkerpop/gremlin/util/function/MultiComparator.java
----------------------------------------------------------------------
diff --git a/gremlin-core/src/main/java/org/apache/tinkerpop/gremlin/util/function/MultiComparator.java b/gremlin-core/src/main/java/org/apache/tinkerpop/gremlin/util/function/MultiComparator.java
index 427aa3d..b7176ab 100644
--- a/gremlin-core/src/main/java/org/apache/tinkerpop/gremlin/util/function/MultiComparator.java
+++ b/gremlin-core/src/main/java/org/apache/tinkerpop/gremlin/util/function/MultiComparator.java
@@ -32,9 +32,11 @@ import java.util.List;
 public final class MultiComparator<C> implements Comparator<C>, Serializable {
 
     private final List<Comparator> comparators;
+    private final boolean isShuffle;
 
     public MultiComparator(final List<Comparator<C>> comparators) {
         this.comparators = (List) comparators;
+        this.isShuffle = !this.comparators.isEmpty() && Order.shuffle == this.comparators.get(this.comparators.size() - 1);
     }
 
     @Override
@@ -43,14 +45,20 @@ public final class MultiComparator<C> implements Comparator<C>, Serializable {
             return Order.incr.compare(objectA, objectB);
         } else {
             for (int i = 0; i < this.comparators.size(); i++) {
-                final int comparison = this.comparators.get(i).compare(this.getObject(objectA, i), this.getObject(objectB, i));
-                if (comparison != 0)
-                    return comparison;
+                if (Order.shuffle != this.comparators.get(i)) {
+                    final int comparison = this.comparators.get(i).compare(this.getObject(objectA, i), this.getObject(objectB, i));
+                    if (comparison != 0)
+                        return comparison;
+                }
             }
             return 0;
         }
     }
 
+    public boolean isShuffle() {
+        return this.isShuffle;
+    }
+
     private final Object getObject(final C object, final int index) {
         if (object instanceof ProjectedTraverser)
             return ((ProjectedTraverser) object).getProjections().get(index);

[02/13] tinkerpop git commit: We now have ProjectedTraveser which is a Traverser with List