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 2017/09/22 14:50:07 UTC

[10/11] tinkerpop git commit: added the new PageRankVertexProgram code to the reference documentation as PageRank serves as our reference program.

added the new PageRankVertexProgram code to the reference documentation as PageRank serves as our reference program.


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

Branch: refs/heads/master
Commit: 94ffe73e778a3eacfd96ec9a38cf8f54f06de256
Parents: dacabbe
Author: Marko A. Rodriguez <ok...@gmail.com>
Authored: Thu Sep 21 09:51:35 2017 -0600
Committer: Marko A. Rodriguez <ok...@gmail.com>
Committed: Thu Sep 21 09:51:35 2017 -0600

----------------------------------------------------------------------
 docs/src/reference/the-graphcomputer.asciidoc | 97 +++++++++++++++-------
 1 file changed, 66 insertions(+), 31 deletions(-)
----------------------------------------------------------------------


http://git-wip-us.apache.org/repos/asf/tinkerpop/blob/94ffe73e/docs/src/reference/the-graphcomputer.asciidoc
----------------------------------------------------------------------
diff --git a/docs/src/reference/the-graphcomputer.asciidoc b/docs/src/reference/the-graphcomputer.asciidoc
index b03c891..278e8bc 100644
--- a/docs/src/reference/the-graphcomputer.asciidoc
+++ b/docs/src/reference/the-graphcomputer.asciidoc
@@ -186,26 +186,30 @@ methods of a `VertexProgram`, the PageRankVertexProgram code is analyzed below.
 
 [source,java]
 ----
-public class PageRankVertexProgram implements VertexProgram<Double> {  <1>
+public class PageRankVertexProgram implements VertexProgram<Double> { <1>
 
     public static final String PAGE_RANK = "gremlin.pageRankVertexProgram.pageRank";
     private static final String EDGE_COUNT = "gremlin.pageRankVertexProgram.edgeCount";
     private static final String PROPERTY = "gremlin.pageRankVertexProgram.property";
     private static final String VERTEX_COUNT = "gremlin.pageRankVertexProgram.vertexCount";
     private static final String ALPHA = "gremlin.pageRankVertexProgram.alpha";
-    private static final String TOTAL_ITERATIONS = "gremlin.pageRankVertexProgram.totalIterations";
+    private static final String EPSILON = "gremlin.pageRankVertexProgram.epsilon";
+    private static final String MAX_ITERATIONS = "gremlin.pageRankVertexProgram.maxIterations";
     private static final String EDGE_TRAVERSAL = "gremlin.pageRankVertexProgram.edgeTraversal";
     private static final String INITIAL_RANK_TRAVERSAL = "gremlin.pageRankVertexProgram.initialRankTraversal";
+    private static final String TELEPORTATION_ENERGY = "gremlin.pageRankVertexProgram.teleportationEnergy";
+    private static final String CONVERGENCE_ERROR = "gremlin.pageRankVertexProgram.convergenceError";
 
     private MessageScope.Local<Double> incidentMessageScope = MessageScope.Local.of(__::outE); <2>
     private MessageScope.Local<Double> countMessageScope = MessageScope.Local.of(new MessageScope.Local.ReverseTraversalSupplier(this.incidentMessageScope));
     private PureTraversal<Vertex, Edge> edgeTraversal = null;
     private PureTraversal<Vertex, ? extends Number> initialRankTraversal = null;
-    private double vertexCountAsDouble = 1.0d;
     private double alpha = 0.85d;
-    private int totalIterations = 30;
+    private double epsilon = 0.00001d;
+    private int maxIterations = 20;
     private String property = PAGE_RANK; <3>
     private Set<VertexComputeKey> vertexComputeKeys;
+    private Set<MemoryComputeKey> memoryComputeKeys;
 
     private PageRankVertexProgram() {
 
@@ -220,20 +224,26 @@ public class PageRankVertexProgram implements VertexProgram<Double> {  <1>
             this.incidentMessageScope = MessageScope.Local.of(() -> this.edgeTraversal.get().clone());
             this.countMessageScope = MessageScope.Local.of(new MessageScope.Local.ReverseTraversalSupplier(this.incidentMessageScope));
         }
-        this.vertexCountAsDouble = configuration.getDouble(VERTEX_COUNT, 1.0d);
-        this.alpha = configuration.getDouble(ALPHA, 0.85d);
-        this.totalIterations = configuration.getInt(TOTAL_ITERATIONS, 30);
+        this.alpha = configuration.getDouble(ALPHA, this.alpha);
+        this.epsilon = configuration.getDouble(EPSILON, this.epsilon);
+        this.maxIterations = configuration.getInt(MAX_ITERATIONS, 20);
         this.property = configuration.getString(PROPERTY, PAGE_RANK);
-        this.vertexComputeKeys = new HashSet<>(Arrays.asList(VertexComputeKey.of(this.property, false), VertexComputeKey.of(EDGE_COUNT, true))); <5>
+        this.vertexComputeKeys = new HashSet<>(Arrays.asList(
+                VertexComputeKey.of(this.property, false),
+                VertexComputeKey.of(EDGE_COUNT, true))); <5>
+        this.memoryComputeKeys = new HashSet<>(Arrays.asList(
+                MemoryComputeKey.of(TELEPORTATION_ENERGY, Operator.sum, true, true),
+                MemoryComputeKey.of(VERTEX_COUNT, Operator.sum, true, true),
+                MemoryComputeKey.of(CONVERGENCE_ERROR, Operator.sum, false, true)));
     }
 
     @Override
     public void storeState(final Configuration configuration) {
         VertexProgram.super.storeState(configuration);
-        configuration.setProperty(VERTEX_COUNT, this.vertexCountAsDouble);
         configuration.setProperty(ALPHA, this.alpha);
-        configuration.setProperty(TOTAL_ITERATIONS, this.totalIterations);
+        configuration.setProperty(EPSILON, this.epsilon);
         configuration.setProperty(PROPERTY, this.property);
+        configuration.setProperty(MAX_ITERATIONS, this.maxIterations);
         if (null != this.edgeTraversal)
             this.edgeTraversal.storeState(configuration, EDGE_TRAVERSAL);
         if (null != this.initialRankTraversal)
@@ -251,7 +261,7 @@ public class PageRankVertexProgram implements VertexProgram<Double> {  <1>
     }
 
     @Override
-    public Set<VertexComputeKey> getVertexComputeKeys() {   <6>
+    public Set<VertexComputeKey> getVertexComputeKeys() { <6>
         return this.vertexComputeKeys;
     }
 
@@ -261,6 +271,11 @@ public class PageRankVertexProgram implements VertexProgram<Double> {  <1>
     }
 
     @Override
+    public Set<MemoryComputeKey> getMemoryComputeKeys() {
+        return this.memoryComputeKeys;
+    }
+
+    @Override
     public Set<MessageScope> getMessageScopes(final Memory memory) {
         final Set<MessageScope> set = new HashSet<>();
         set.add(memory.isInitialIteration() ? this.countMessageScope : this.incidentMessageScope);
@@ -281,39 +296,59 @@ public class PageRankVertexProgram implements VertexProgram<Double> {  <1>
 
     @Override
     public void setup(final Memory memory) {
-
+        memory.set(TELEPORTATION_ENERGY, null == this.initialRankTraversal ? 1.0d : 0.0d);
+        memory.set(VERTEX_COUNT, 0.0d);
+        memory.set(CONVERGENCE_ERROR, 1.0d);
     }
 
     @Override
     public void execute(final Vertex vertex, Messenger<Double> messenger, final Memory memory) { <7>
         if (memory.isInitialIteration()) {
-            messenger.sendMessage(this.countMessageScope, 1.0d); <8>
-        } else if (1 == memory.getIteration()) {
-            double initialPageRank = (null == this.initialRankTraversal ?
-                    1.0d :
-                    TraversalUtil.apply(vertex, this.initialRankTraversal.get()).doubleValue()) / this.vertexCountAsDouble;  <9>
-            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);
-            if (!this.terminate(memory)) // don't send messages if this is the last iteration
-                messenger.sendMessage(this.incidentMessageScope, initialPageRank / edgeCount);
+            messenger.sendMessage(this.countMessageScope, 1.0d);  <8>
+            memory.add(VERTEX_COUNT, 1.0d);
         } else {
-            double newPageRank = IteratorUtils.reduce(messenger.receiveMessages(), 0.0d, (a, b) -> a + b); <10>
-            newPageRank = (this.alpha * newPageRank) + ((1.0d - this.alpha) / this.vertexCountAsDouble);
-            vertex.property(VertexProperty.Cardinality.single, this.property, newPageRank);
-            if (!this.terminate(memory)) // don't send messages if this is the last iteration
-                messenger.sendMessage(this.incidentMessageScope, newPageRank / vertex.<Double>value(EDGE_COUNT));
+            final double vertexCount = memory.<Double>get(VERTEX_COUNT);
+            final double edgeCount;
+            double pageRank;
+            if (1 == memory.getIteration()) {
+                edgeCount = IteratorUtils.reduce(messenger.receiveMessages(), 0.0d, (a, b) -> a + b);
+                vertex.property(VertexProperty.Cardinality.single, EDGE_COUNT, edgeCount);
+                pageRank = null == this.initialRankTraversal ?
+                        0.0d :
+                        TraversalUtil.apply(vertex, this.initialRankTraversal.get()).doubleValue(); <9>
+            } else {
+                edgeCount = vertex.value(EDGE_COUNT);
+                pageRank = IteratorUtils.reduce(messenger.receiveMessages(), 0.0d, (a, b) -> a + b); <10>
+            }
+            //////////////////////////
+            final double teleporationEnergy = memory.get(TELEPORTATION_ENERGY);
+            if (teleporationEnergy > 0.0d) {
+                final double localTerminalEnergy = teleporationEnergy / vertexCount;
+                pageRank = pageRank + localTerminalEnergy;
+                memory.add(TELEPORTATION_ENERGY, -localTerminalEnergy);
+            }
+            final double previousPageRank = vertex.<Double>property(this.property).orElse(0.0d);
+            memory.add(CONVERGENCE_ERROR, Math.abs(pageRank - previousPageRank));
+            vertex.property(VertexProperty.Cardinality.single, this.property, pageRank);
+            memory.add(TELEPORTATION_ENERGY, (1.0d - this.alpha) * pageRank);
+            pageRank = this.alpha * pageRank;
+            if (edgeCount > 0.0d)
+                messenger.sendMessage(this.incidentMessageScope, pageRank / edgeCount);
+            else
+                memory.add(TELEPORTATION_ENERGY, pageRank);
         }
     }
 
     @Override
-    public boolean terminate(final Memory memory) {
-        return memory.getIteration() >= this.totalIterations;  <11>
+    public boolean terminate(final Memory memory) { <11>
+        boolean terminate = memory.<Double>get(CONVERGENCE_ERROR) < this.epsilon || memory.getIteration() >= this.maxIterations;
+        memory.set(CONVERGENCE_ERROR, 0.0d);
+        return terminate;
     }
 
     @Override
     public String toString() {
-        return StringFactory.vertexProgramString(this, "alpha=" + this.alpha + ", iterations=" + this.totalIterations);
+        return StringFactory.vertexProgramString(this, "alpha=" + this.alpha + ", epsilon=" + this.epsilon + ", iterations=" + this.maxIterations);
     }
 }
 ----
@@ -328,7 +363,7 @@ public class PageRankVertexProgram implements VertexProgram<Double> {  <1>
 <8> In order to determine how to distribute the energy to neighbors, a "1"-count is used to determine how many incident vertices exist for the `MessageScope`.
 <9> Initially, each vertex is provided an equal amount of energy represented as a double.
 <10> Energy is aggregated, computed on according to the PageRank algorithm, and then disseminated according to the defined `MessageScope.Local`.
-<11> The computation is terminated after a pre-defined number of iterations.
+<11> The computation is terminated after epsilon-convergence is met or a pre-defined number of iterations have taken place.
 
 The above `PageRankVertexProgram` is used as follows.