You are viewing a plain text version of this content. The canonical link for it is here.
Posted to commits@tinkerpop.apache.org by ok...@apache.org on 2016/02/19 17:26:54 UTC
[23/27] incubator-tinkerpop git commit: added the concept of
initialRank to PageRankVertexProgram. The initialRank of a vertex is
determined by a Traversal. What is sweet,
in the context of multi-OLAP traversals --- g.V().has('name', 'marko
added the concept of initialRank to PageRankVertexProgram. The initialRank of a vertex is determined by a Traversal<Vertex,Double>. What is sweet, in the context of multi-OLAP traversals --- g.V().has('name','marko').pageRank(), the initialRank is determined by HaltedTraversersCountTraversal which simply determines the size of the HALTED_TRAVERSERS at that vertex. Thus, marko gets an initial rank of 1 and every other vertex 0. Created a CRAZY long, complex PageRankTest traversal to validate the behavior.
Project: http://git-wip-us.apache.org/repos/asf/incubator-tinkerpop/repo
Commit: http://git-wip-us.apache.org/repos/asf/incubator-tinkerpop/commit/cb4df815
Tree: http://git-wip-us.apache.org/repos/asf/incubator-tinkerpop/tree/cb4df815
Diff: http://git-wip-us.apache.org/repos/asf/incubator-tinkerpop/diff/cb4df815
Branch: refs/heads/master
Commit: cb4df815a2ba8a78bb3e50234c79ba497c07521f
Parents: 0192240
Author: Marko A. Rodriguez <ok...@gmail.com>
Authored: Thu Feb 18 11:43:58 2016 -0700
Committer: Marko A. Rodriguez <ok...@gmail.com>
Committed: Thu Feb 18 11:43:58 2016 -0700
----------------------------------------------------------------------
.../ranking/pagerank/PageRankVertexProgram.java | 28 +++++-----
.../lambda/HaltedTraversersCountTraversal.java | 56 ++++++++++++++++++++
.../step/map/PageRankVertexProgramStep.java | 9 ++--
.../traversal/step/map/VertexProgramStep.java | 11 ++++
.../step/map/GroovyPageRankTest.groovy | 6 +++
.../traversal/step/map/PageRankTest.java | 27 ++++++++++
6 files changed, 121 insertions(+), 16 deletions(-)
----------------------------------------------------------------------
http://git-wip-us.apache.org/repos/asf/incubator-tinkerpop/blob/cb4df815/gremlin-core/src/main/java/org/apache/tinkerpop/gremlin/process/computer/ranking/pagerank/PageRankVertexProgram.java
----------------------------------------------------------------------
diff --git a/gremlin-core/src/main/java/org/apache/tinkerpop/gremlin/process/computer/ranking/pagerank/PageRankVertexProgram.java b/gremlin-core/src/main/java/org/apache/tinkerpop/gremlin/process/computer/ranking/pagerank/PageRankVertexProgram.java
index 9a3d54d..cb64a3c 100644
--- a/gremlin-core/src/main/java/org/apache/tinkerpop/gremlin/process/computer/ranking/pagerank/PageRankVertexProgram.java
+++ b/gremlin-core/src/main/java/org/apache/tinkerpop/gremlin/process/computer/ranking/pagerank/PageRankVertexProgram.java
@@ -58,12 +58,12 @@ public class PageRankVertexProgram extends StaticVertexProgram<Double> {
private static final String ALPHA = "gremlin.pageRankVertexProgram.alpha";
private static final String TOTAL_ITERATIONS = "gremlin.pageRankVertexProgram.totalIterations";
private static final String EDGE_TRAVERSAL = "gremlin.pageRankVertexProgram.edgeTraversal";
- private static final String VERTEX_TRAVERSAL = "gremlin.pageRankVertexProgram.vertexTraversal";
+ private static final String INITIAL_RANK_TRAVERSAL = "gremlin.pageRankVertexProgram.initialRankTraversal";
private MessageScope.Local<Double> incidentMessageScope = MessageScope.Local.of(__::outE);
private MessageScope.Local<Double> countMessageScope = MessageScope.Local.of(new MessageScope.Local.ReverseTraversalSupplier(this.incidentMessageScope));
private PureTraversal<Vertex, Edge> edgeTraversal = null;
- private PureTraversal<Vertex, Vertex> vertexTraversal = null;
+ private PureTraversal<Vertex, ? extends Number> initialRankTraversal = null;
private double vertexCountAsDouble = 1.0d;
private double alpha = 0.85d;
private int totalIterations = 30;
@@ -76,8 +76,8 @@ public class PageRankVertexProgram extends StaticVertexProgram<Double> {
@Override
public void loadState(final Graph graph, final Configuration configuration) {
- if (configuration.containsKey(VERTEX_TRAVERSAL))
- this.vertexTraversal = PureTraversal.loadState(configuration, VERTEX_TRAVERSAL, graph);
+ if (configuration.containsKey(INITIAL_RANK_TRAVERSAL))
+ this.initialRankTraversal = PureTraversal.loadState(configuration, INITIAL_RANK_TRAVERSAL, graph);
if (configuration.containsKey(EDGE_TRAVERSAL)) {
this.edgeTraversal = PureTraversal.loadState(configuration, EDGE_TRAVERSAL, graph);
this.incidentMessageScope = MessageScope.Local.of(() -> this.edgeTraversal.get().clone());
@@ -99,8 +99,8 @@ public class PageRankVertexProgram extends StaticVertexProgram<Double> {
configuration.setProperty(PROPERTY, this.property);
if (null != this.edgeTraversal)
this.edgeTraversal.storeState(configuration, EDGE_TRAVERSAL);
- if (null != this.vertexTraversal)
- this.vertexTraversal.storeState(configuration, VERTEX_TRAVERSAL);
+ if (null != this.initialRankTraversal)
+ this.initialRankTraversal.storeState(configuration, INITIAL_RANK_TRAVERSAL);
}
@Override
@@ -140,18 +140,20 @@ public class PageRankVertexProgram extends StaticVertexProgram<Double> {
if (memory.isInitialIteration()) {
messenger.sendMessage(this.countMessageScope, 1.0d);
} else if (1 == memory.getIteration()) {
- double initialPageRank = 1.0d / this.vertexCountAsDouble;
+ double initialPageRank = null == this.initialRankTraversal ?
+ 1.0d :
+ TraversalUtil.apply(vertex, this.initialRankTraversal.get()).doubleValue() / this.vertexCountAsDouble;
double edgeCount = IteratorUtils.reduce(messenger.receiveMessages(), 0.0d, (a, b) -> a + b);
vertex.property(VertexProperty.Cardinality.single, this.property, initialPageRank);
vertex.property(VertexProperty.Cardinality.single, EDGE_COUNT, edgeCount);
- messenger.sendMessage(this.incidentMessageScope, initialPageRank / edgeCount);
+ if (!this.terminate(memory)) // don't send messages if this is the last iteration
+ messenger.sendMessage(this.incidentMessageScope, initialPageRank / edgeCount);
} else {
- if (2 == memory.getIteration() && null != this.vertexTraversal && !TraversalUtil.test(vertex, this.vertexTraversal.get()))
- return;
double newPageRank = IteratorUtils.reduce(messenger.receiveMessages(), 0.0d, (a, b) -> a + b);
newPageRank = (this.alpha * newPageRank) + ((1.0d - this.alpha) / this.vertexCountAsDouble);
vertex.property(VertexProperty.Cardinality.single, this.property, newPageRank);
- messenger.sendMessage(this.incidentMessageScope, newPageRank / vertex.<Double>value(EDGE_COUNT));
+ if (!this.terminate(memory)) // don't send messages if this is the last iteration
+ messenger.sendMessage(this.incidentMessageScope, newPageRank / vertex.<Double>value(EDGE_COUNT));
}
}
@@ -202,8 +204,8 @@ public class PageRankVertexProgram extends StaticVertexProgram<Double> {
return this;
}
- public Builder vertices(final Traversal.Admin<Vertex, Vertex> vertexTraversal) {
- PureTraversal.storeState(this.configuration, VERTEX_TRAVERSAL, vertexTraversal);
+ public Builder initialRank(final Traversal.Admin<Vertex, ? extends Number> initialRankTraversal) {
+ PureTraversal.storeState(this.configuration, INITIAL_RANK_TRAVERSAL, initialRankTraversal);
return this;
}
http://git-wip-us.apache.org/repos/asf/incubator-tinkerpop/blob/cb4df815/gremlin-core/src/main/java/org/apache/tinkerpop/gremlin/process/computer/traversal/lambda/HaltedTraversersCountTraversal.java
----------------------------------------------------------------------
diff --git a/gremlin-core/src/main/java/org/apache/tinkerpop/gremlin/process/computer/traversal/lambda/HaltedTraversersCountTraversal.java b/gremlin-core/src/main/java/org/apache/tinkerpop/gremlin/process/computer/traversal/lambda/HaltedTraversersCountTraversal.java
new file mode 100644
index 0000000..b09cd7d
--- /dev/null
+++ b/gremlin-core/src/main/java/org/apache/tinkerpop/gremlin/process/computer/traversal/lambda/HaltedTraversersCountTraversal.java
@@ -0,0 +1,56 @@
+/*
+ * Licensed to the Apache Software Foundation (ASF) under one
+ * or more contributor license agreements. See the NOTICE file
+ * distributed with this work for additional information
+ * regarding copyright ownership. The ASF licenses this file
+ * to you under the Apache License, Version 2.0 (the
+ * "License"); you may not use this file except in compliance
+ * with the License. You may obtain a copy of the License at
+ *
+ * http://www.apache.org/licenses/LICENSE-2.0
+ *
+ * Unless required by applicable law or agreed to in writing,
+ * software distributed under the License is distributed on an
+ * "AS IS" BASIS, WITHOUT WARRANTIES OR CONDITIONS OF ANY
+ * KIND, either express or implied. See the License for the
+ * specific language governing permissions and limitations
+ * under the License.
+ */
+
+package org.apache.tinkerpop.gremlin.process.computer.traversal.lambda;
+
+import org.apache.tinkerpop.gremlin.process.computer.traversal.TraversalVertexProgram;
+import org.apache.tinkerpop.gremlin.process.traversal.Traverser;
+import org.apache.tinkerpop.gremlin.process.traversal.lambda.AbstractLambdaTraversal;
+import org.apache.tinkerpop.gremlin.process.traversal.traverser.util.TraverserSet;
+import org.apache.tinkerpop.gremlin.structure.Vertex;
+import org.apache.tinkerpop.gremlin.structure.VertexProperty;
+
+/**
+ * @author Marko A. Rodriguez (http://markorodriguez.com)
+ */
+public final class HaltedTraversersCountTraversal extends AbstractLambdaTraversal<Vertex, Long> {
+
+ private Long count;
+
+ @Override
+ public Long next() {
+ return count;
+ }
+
+ @Override
+ public void addStart(final Traverser<Vertex> start) {
+ final VertexProperty<TraverserSet<Object>> property = start.get().<TraverserSet<Object>>property(TraversalVertexProgram.HALTED_TRAVERSERS);
+ this.count = property.isPresent() ? property.value().bulkSize() : 0l;
+ }
+
+ @Override
+ public String toString() {
+ return "count(" + TraversalVertexProgram.HALTED_TRAVERSERS + ')';
+ }
+
+ @Override
+ public int hashCode() {
+ return this.getClass().hashCode();
+ }
+}
http://git-wip-us.apache.org/repos/asf/incubator-tinkerpop/blob/cb4df815/gremlin-core/src/main/java/org/apache/tinkerpop/gremlin/process/computer/traversal/step/map/PageRankVertexProgramStep.java
----------------------------------------------------------------------
diff --git a/gremlin-core/src/main/java/org/apache/tinkerpop/gremlin/process/computer/traversal/step/map/PageRankVertexProgramStep.java b/gremlin-core/src/main/java/org/apache/tinkerpop/gremlin/process/computer/traversal/step/map/PageRankVertexProgramStep.java
index a5d1669..bbbe968 100644
--- a/gremlin-core/src/main/java/org/apache/tinkerpop/gremlin/process/computer/traversal/step/map/PageRankVertexProgramStep.java
+++ b/gremlin-core/src/main/java/org/apache/tinkerpop/gremlin/process/computer/traversal/step/map/PageRankVertexProgramStep.java
@@ -21,6 +21,7 @@ package org.apache.tinkerpop.gremlin.process.computer.traversal.step.map;
import org.apache.tinkerpop.gremlin.process.computer.GraphComputer;
import org.apache.tinkerpop.gremlin.process.computer.ranking.pagerank.PageRankVertexProgram;
+import org.apache.tinkerpop.gremlin.process.computer.traversal.lambda.HaltedTraversersCountTraversal;
import org.apache.tinkerpop.gremlin.process.traversal.Traversal;
import org.apache.tinkerpop.gremlin.process.traversal.TraversalStrategies;
import org.apache.tinkerpop.gremlin.process.traversal.dsl.graph.__;
@@ -92,12 +93,14 @@ public final class PageRankVertexProgramStep extends VertexProgramStep implement
public PageRankVertexProgram generateProgram(final Graph graph) {
final Traversal.Admin<Vertex, Edge> detachedTraversal = this.edgeTraversal.getPure();
detachedTraversal.setStrategies(TraversalStrategies.GlobalCache.getStrategies(graph.getClass()));
- return PageRankVertexProgram.build()
+ final PageRankVertexProgram.Builder builder = PageRankVertexProgram.build()
.property(this.pageRankProperty)
.iterations(this.times + 1)
.alpha(this.alpha)
- .edges(detachedTraversal)
- .create(graph);
+ .edges(detachedTraversal);
+ if (this.previousTraversalVertexProgram())
+ builder.initialRank(new HaltedTraversersCountTraversal());
+ return builder.create(graph);
}
@Override
http://git-wip-us.apache.org/repos/asf/incubator-tinkerpop/blob/cb4df815/gremlin-core/src/main/java/org/apache/tinkerpop/gremlin/process/computer/traversal/step/map/VertexProgramStep.java
----------------------------------------------------------------------
diff --git a/gremlin-core/src/main/java/org/apache/tinkerpop/gremlin/process/computer/traversal/step/map/VertexProgramStep.java b/gremlin-core/src/main/java/org/apache/tinkerpop/gremlin/process/computer/traversal/step/map/VertexProgramStep.java
index a85f5b1..7398710 100644
--- a/gremlin-core/src/main/java/org/apache/tinkerpop/gremlin/process/computer/traversal/step/map/VertexProgramStep.java
+++ b/gremlin-core/src/main/java/org/apache/tinkerpop/gremlin/process/computer/traversal/step/map/VertexProgramStep.java
@@ -21,6 +21,7 @@ package org.apache.tinkerpop.gremlin.process.computer.traversal.step.map;
import org.apache.tinkerpop.gremlin.process.computer.ComputerResult;
import org.apache.tinkerpop.gremlin.process.computer.traversal.step.VertexComputing;
+import org.apache.tinkerpop.gremlin.process.traversal.Step;
import org.apache.tinkerpop.gremlin.process.traversal.Traversal;
import org.apache.tinkerpop.gremlin.process.traversal.Traverser;
import org.apache.tinkerpop.gremlin.process.traversal.step.util.AbstractStep;
@@ -57,4 +58,14 @@ public abstract class VertexProgramStep extends AbstractStep<ComputerResult, Com
throw new IllegalStateException(e.getMessage(), e);
}
}
+
+ protected boolean previousTraversalVertexProgram() {
+ Step<?, ?> currentStep = this;
+ while (!(currentStep instanceof EmptyStep)) {
+ if (currentStep instanceof TraversalVertexProgramStep)
+ return true;
+ currentStep = currentStep.getPreviousStep();
+ }
+ return false;
+ }
}
http://git-wip-us.apache.org/repos/asf/incubator-tinkerpop/blob/cb4df815/gremlin-groovy-test/src/main/groovy/org/apache/tinkerpop/gremlin/process/traversal/step/map/GroovyPageRankTest.groovy
----------------------------------------------------------------------
diff --git a/gremlin-groovy-test/src/main/groovy/org/apache/tinkerpop/gremlin/process/traversal/step/map/GroovyPageRankTest.groovy b/gremlin-groovy-test/src/main/groovy/org/apache/tinkerpop/gremlin/process/traversal/step/map/GroovyPageRankTest.groovy
index 22ffb0c..b3b3da5 100644
--- a/gremlin-groovy-test/src/main/groovy/org/apache/tinkerpop/gremlin/process/traversal/step/map/GroovyPageRankTest.groovy
+++ b/gremlin-groovy-test/src/main/groovy/org/apache/tinkerpop/gremlin/process/traversal/step/map/GroovyPageRankTest.groovy
@@ -20,6 +20,7 @@
package org.apache.tinkerpop.gremlin.process.traversal.step.map
import org.apache.tinkerpop.gremlin.process.traversal.Traversal
+import org.apache.tinkerpop.gremlin.process.traversal.dsl.graph.__
import org.apache.tinkerpop.gremlin.process.traversal.util.ScriptTraversal
import org.apache.tinkerpop.gremlin.structure.Vertex
@@ -59,5 +60,10 @@ public abstract class GroovyPageRankTest {
public Traversal<Vertex, Map<String, Object>> get_g_V_pageRank_byXpageRankX_asXaX_outXknowsX_pageRank_asXbX_selectXa_bX() {
new ScriptTraversal<>(g, "gremlin-groovy", "g.V.pageRank.by('pageRank').as('a').out('knows').values('pageRank').as('b').select('a', 'b')")
}
+
+ @Override
+ public Traversal<Vertex, Map<String, List<Object>>> get_g_V_hasLabelXsoftwareX_hasXname_rippleX_pageRankX1X_byXinEXcreatedXX_timesX1X_byXpriorsX_inXcreatedX_unionXboth__identityX_valueMapXname_priorsX() {
+ new ScriptTraversal<>(g, "gremlin-groovy", "g.V().hasLabel('software').has('name', 'ripple').pageRank(1.0).by(inE('created')).times(1).by('priors').in('created').union(identity(),both()).valueMap('name', 'priors')")
+ }
}
}
http://git-wip-us.apache.org/repos/asf/incubator-tinkerpop/blob/cb4df815/gremlin-test/src/main/java/org/apache/tinkerpop/gremlin/process/traversal/step/map/PageRankTest.java
----------------------------------------------------------------------
diff --git a/gremlin-test/src/main/java/org/apache/tinkerpop/gremlin/process/traversal/step/map/PageRankTest.java b/gremlin-test/src/main/java/org/apache/tinkerpop/gremlin/process/traversal/step/map/PageRankTest.java
index d29230b..3ae98d9 100644
--- a/gremlin-test/src/main/java/org/apache/tinkerpop/gremlin/process/traversal/step/map/PageRankTest.java
+++ b/gremlin-test/src/main/java/org/apache/tinkerpop/gremlin/process/traversal/step/map/PageRankTest.java
@@ -37,6 +37,7 @@ import static org.apache.tinkerpop.gremlin.LoadGraphWith.GraphData.MODERN;
import static org.junit.Assert.assertEquals;
import static org.junit.Assert.assertFalse;
import static org.junit.Assert.assertTrue;
+import static org.junit.Assert.fail;
/**
* @author Marko A. Rodriguez (http://markorodriguez.com)
@@ -56,6 +57,8 @@ public abstract class PageRankTest extends AbstractGremlinProcessTest {
public abstract Traversal<Vertex, Map<String, Object>> get_g_V_pageRank_byXpageRankX_asXaX_outXknowsX_pageRank_asXbX_selectXa_bX();
+ public abstract Traversal<Vertex, Map<String, List<Object>>> get_g_V_hasLabelXsoftwareX_hasXname_rippleX_pageRankX1X_byXinEXcreatedXX_timesX1X_byXpriorsX_inXcreatedX_unionXboth__identityX_valueMapXname_priorsX();
+
@Test
@LoadGraphWith(MODERN)
public void g_V_pageRank() {
@@ -159,6 +162,25 @@ public abstract class PageRankTest extends AbstractGremlinProcessTest {
assertEquals(2, counter);
}
+ @Test
+ @LoadGraphWith(MODERN)
+ public void g_V_hasLabelXsoftwareX_hasXname_rippleX_pageRankX1X_byXinEXcreatedXX_timesX1X_byXpriorsX_inXcreatedX_unionXboth__identityX_valueMapXname_priorsX() {
+ final Traversal<Vertex, Map<String, List<Object>>> traversal = get_g_V_hasLabelXsoftwareX_hasXname_rippleX_pageRankX1X_byXinEXcreatedXX_timesX1X_byXpriorsX_inXcreatedX_unionXboth__identityX_valueMapXname_priorsX();
+ printTraversalForm(traversal);
+ int counter = 0;
+ while (traversal.hasNext()) {
+ final Map<String, List<Object>> map = traversal.next();
+ assertEquals(2, map.size());
+ String name = (String) map.get("name").get(0);
+ double pageRank = (Double) map.get("priors").get(0);
+ assertEquals(name.equals("josh") ? 1.0d : 0.0d, pageRank, 0.0001d);
+ if (name.equals("peter") || name.equals("vadas"))
+ fail("Peter or Vadas should not have been accessed");
+ counter++;
+ }
+ assertEquals(4, counter);
+ }
+
public static class Traversals extends PageRankTest {
@Override
@@ -190,5 +212,10 @@ public abstract class PageRankTest extends AbstractGremlinProcessTest {
public Traversal<Vertex, Map<String, Object>> get_g_V_pageRank_byXpageRankX_asXaX_outXknowsX_pageRank_asXbX_selectXa_bX() {
return g.V().pageRank().by("pageRank").as("a").out("knows").values("pageRank").as("b").select("a", "b");
}
+
+ @Override
+ public Traversal<Vertex, Map<String, List<Object>>> get_g_V_hasLabelXsoftwareX_hasXname_rippleX_pageRankX1X_byXinEXcreatedXX_timesX1X_byXpriorsX_inXcreatedX_unionXboth__identityX_valueMapXname_priorsX() {
+ return g.V().hasLabel("software").has("name", "ripple").pageRank(1.0).by(__.inE("created")).times(1).by("priors").in("created").union(__.both(), __.identity()).valueMap("name", "priors");
+ }
}
}