totalIterations is now maxIterations. If the espilon convergence is not met after maxIterations, PageRank terminates. However, if convergence occurs before maxIterations, then PageRank terminates (prior to maxIterations). Given that PageRank is monotonic, this is exactly what you would want.
Project: http://git-wip-us.apache.org/repos/asf/tinkerpop/repo Commit: http://git-wip-us.apache.org/repos/asf/tinkerpop/commit/f926dac0 Tree: http://git-wip-us.apache.org/repos/asf/tinkerpop/tree/f926dac0 Diff: http://git-wip-us.apache.org/repos/asf/tinkerpop/diff/f926dac0 Branch: refs/heads/master Commit: f926dac0b74658c2b88ec79bf088a3339f5b9572 Parents: 735af78 Author: Marko A. Rodriguez <okramma...@gmail.com> Authored: Wed Sep 20 08:38:26 2017 -0600 Committer: Marko A. Rodriguez <okramma...@gmail.com> Committed: Wed Sep 20 08:38:26 2017 -0600 ---------------------------------------------------------------------- CHANGELOG.asciidoc | 3 ++- .../ranking/pagerank/PageRankVertexProgram.java | 18 +++++++----------- .../step/map/PageRankVertexProgramStep.java | 2 +- .../pagerank/PageRankVertexProgramTest.java | 3 ++- 4 files changed, 12 insertions(+), 14 deletions(-) ---------------------------------------------------------------------- http://git-wip-us.apache.org/repos/asf/tinkerpop/blob/f926dac0/CHANGELOG.asciidoc ---------------------------------------------------------------------- diff --git a/CHANGELOG.asciidoc b/CHANGELOG.asciidoc index 87899ce..0367fd6 100644 --- a/CHANGELOG.asciidoc +++ b/CHANGELOG.asciidoc @@ -28,7 +28,8 @@ TinkerPop 3.3.1 (Release Date: NOT OFFICIALLY RELEASED YET) This release also includes changes from <<release-3-2-7, 3.2.7>>. -* Added support for epsilon-based convergence in `PageRankVertexProgram` (no longer manually capped by iterations). +* `PageRankVertexProgram` supports `maxIterations` but will break out early if epsilon-based convergence occurs. +* Added support for epsilon-based convergence in `PageRankVertexProgram`. * Fixed two major bugs in how PageRank was being calculated in `PageRankVertexProgram`. * Added `Io.requiresVersion(Object)` to allow graph providers a way to check the `Io` type and version being constructed. * Defaulted `IoCore.gryo()` and `IoCore.graphson()` to both use their 3.0 formats which means that `Graph.io()` will use those by default. http://git-wip-us.apache.org/repos/asf/tinkerpop/blob/f926dac0/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 28f3e4b..217060e 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 @@ -59,7 +59,7 @@ public class PageRankVertexProgram implements VertexProgram<Double> { private static final String VERTEX_COUNT = "gremlin.pageRankVertexProgram.vertexCount"; private static final String ALPHA = "gremlin.pageRankVertexProgram.alpha"; private static final String EPSILON = "gremlin.pageRankVertexProgram.epsilon"; - private static final String TOTAL_ITERATIONS = "gremlin.pageRankVertexProgram.totalIterations"; + 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"; @@ -71,7 +71,7 @@ public class PageRankVertexProgram implements VertexProgram<Double> { private PureTraversal<Vertex, ? extends Number> initialRankTraversal = null; private double alpha = 0.85d; private double epsilon = 0.00001d; - private int totalIterations = -1; + private int maxIterations = 20; private String property = PAGE_RANK; private Set<VertexComputeKey> vertexComputeKeys; private Set<MemoryComputeKey> memoryComputeKeys; @@ -91,7 +91,7 @@ public class PageRankVertexProgram implements VertexProgram<Double> { } this.alpha = configuration.getDouble(ALPHA, this.alpha); this.epsilon = configuration.getDouble(EPSILON, this.epsilon); - this.totalIterations = configuration.getInt(TOTAL_ITERATIONS, -1); + 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), @@ -108,7 +108,7 @@ public class PageRankVertexProgram implements VertexProgram<Double> { configuration.setProperty(ALPHA, this.alpha); configuration.setProperty(EPSILON, this.epsilon); configuration.setProperty(PROPERTY, this.property); - configuration.setProperty(TOTAL_ITERATIONS, this.totalIterations); + configuration.setProperty(MAX_ITERATIONS, this.maxIterations); if (null != this.edgeTraversal) this.edgeTraversal.storeState(configuration, EDGE_TRAVERSAL); if (null != this.initialRankTraversal) @@ -208,16 +208,12 @@ public class PageRankVertexProgram implements VertexProgram<Double> { public boolean terminate(final Memory memory) { // System.out.println(memory.<Double>get(CONVERGENCE_ERROR)); memory.set(CONVERGENCE_ERROR, 0.0d); - return -1 == this.totalIterations ? - memory.<Double>get(CONVERGENCE_ERROR) < this.epsilon : - memory.getIteration() >= this.totalIterations; + return memory.<Double>get(CONVERGENCE_ERROR) < this.epsilon || memory.getIteration() >= this.maxIterations; } @Override public String toString() { - return -1 == this.totalIterations ? - StringFactory.vertexProgramString(this, "alpha=" + this.alpha + ", epsilon=" + this.epsilon) : - StringFactory.vertexProgramString(this, "alpha=" + this.alpha + ", iterations=" + this.totalIterations); + return StringFactory.vertexProgramString(this, "alpha=" + this.alpha + ", epsilon=" + this.epsilon + ", iterations=" + this.maxIterations); } ////////////////////////////// @@ -233,7 +229,7 @@ public class PageRankVertexProgram implements VertexProgram<Double> { } public Builder iterations(final int iterations) { - this.configuration.setProperty(TOTAL_ITERATIONS, iterations); + this.configuration.setProperty(MAX_ITERATIONS, iterations); return this; } http://git-wip-us.apache.org/repos/asf/tinkerpop/blob/f926dac0/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 d67faf3..2f67aeb 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 @@ -47,7 +47,7 @@ public final class PageRankVertexProgramStep extends VertexProgramStep implement private PureTraversal<Vertex, Edge> edgeTraversal; private String pageRankProperty = PageRankVertexProgram.PAGE_RANK; - private int times = -2; + private int times = 20; private final double alpha; public PageRankVertexProgramStep(final Traversal.Admin traversal, final double alpha) { http://git-wip-us.apache.org/repos/asf/tinkerpop/blob/f926dac0/gremlin-test/src/main/java/org/apache/tinkerpop/gremlin/process/computer/ranking/pagerank/PageRankVertexProgramTest.java ---------------------------------------------------------------------- diff --git a/gremlin-test/src/main/java/org/apache/tinkerpop/gremlin/process/computer/ranking/pagerank/PageRankVertexProgramTest.java b/gremlin-test/src/main/java/org/apache/tinkerpop/gremlin/process/computer/ranking/pagerank/PageRankVertexProgramTest.java index 459c688..6fb3cb7 100644 --- a/gremlin-test/src/main/java/org/apache/tinkerpop/gremlin/process/computer/ranking/pagerank/PageRankVertexProgramTest.java +++ b/gremlin-test/src/main/java/org/apache/tinkerpop/gremlin/process/computer/ranking/pagerank/PageRankVertexProgramTest.java @@ -38,7 +38,8 @@ public class PageRankVertexProgramTest extends AbstractGremlinProcessTest { @LoadGraphWith(MODERN) public void shouldExecutePageRank() throws Exception { if (graphProvider.getGraphComputer(graph).features().supportsResultGraphPersistCombination(GraphComputer.ResultGraph.NEW, GraphComputer.Persist.VERTEX_PROPERTIES)) { - final ComputerResult result = graph.compute(graphProvider.getGraphComputer(graph).getClass()).program(PageRankVertexProgram.build().iterations(30).create(graph)).submit().get(); + final ComputerResult result = graph.compute(graphProvider.getGraphComputer(graph).getClass()). + program(PageRankVertexProgram.build().epsilon(0.0d).iterations(30).create(graph)).submit().get(); // by using epsilon 0.0, we guarantee iterations 30 result.graph().traversal().V().forEachRemaining(v -> { assertEquals(3, v.keys().size()); // name, age/lang, pageRank assertTrue(v.keys().contains("name"));
