This is an automated email from the ASF dual-hosted git repository. jin pushed a commit to branch olap-algo in repository https://gitbox.apache.org/repos/asf/incubator-hugegraph.git
commit 8eac98a1284fb3352e87a658a74e372adeb02c6d Author: houzhizhen <[email protected]> AuthorDate: Thu Oct 15 16:31:02 2020 +0800 performance improvement: the meetNode is invoked only when node.distance is parent.distance() + 1 (#69) --- .../baidu/hugegraph/job/algorithm/BfsTraverser.java | 18 +++++++++++------- .../cent/BetweennessCentralityAlgorithmV2.java | 2 +- .../algorithm/cent/StressCentralityAlgorithmV2.java | 2 +- 3 files changed, 13 insertions(+), 9 deletions(-) diff --git a/hugegraph-core/src/main/java/com/baidu/hugegraph/job/algorithm/BfsTraverser.java b/hugegraph-core/src/main/java/com/baidu/hugegraph/job/algorithm/BfsTraverser.java index 034887f27..3b0920855 100644 --- a/hugegraph-core/src/main/java/com/baidu/hugegraph/job/algorithm/BfsTraverser.java +++ b/hugegraph-core/src/main/java/com/baidu/hugegraph/job/algorithm/BfsTraverser.java @@ -78,8 +78,10 @@ public abstract class BfsTraverser<T extends BfsTraverser.Node> localNodes.put(target, targetNode); traversingVertices.addLast(target); } - this.meetNode(target, targetNode, source, - sourceNode, firstTime); + if (targetNode.distance() == sourceNode.distance() + 1) { + this.meetNode(target, targetNode, source, + sourceNode, firstTime); + } } } return localNodes; @@ -96,6 +98,10 @@ public abstract class BfsTraverser<T extends BfsTraverser.Node> protected abstract T createNode(T parentNode); + /** + * This method is invoked when currentVertex.distance() equals + * parentVertex.distance() + 1. + */ protected abstract void meetNode(Id currentVertex, T currentNode, Id parentVertex, T parentNode, boolean firstTime); @@ -136,11 +142,9 @@ public abstract class BfsTraverser<T extends BfsTraverser.Node> this.parents = newParents; } - public void addParentNodeIfNeeded(Node node, Id parentId) { - if (this.distance == node.distance + 1) { - this.pathCount += node.pathCount; - this.addParent(parentId); - } + public void addParentNode(Node node, Id parentId) { + this.pathCount += node.pathCount; + this.addParent(parentId); } protected int pathCount() { diff --git a/hugegraph-core/src/main/java/com/baidu/hugegraph/job/algorithm/cent/BetweennessCentralityAlgorithmV2.java b/hugegraph-core/src/main/java/com/baidu/hugegraph/job/algorithm/cent/BetweennessCentralityAlgorithmV2.java index 1391021a2..0cb2fef32 100644 --- a/hugegraph-core/src/main/java/com/baidu/hugegraph/job/algorithm/cent/BetweennessCentralityAlgorithmV2.java +++ b/hugegraph-core/src/main/java/com/baidu/hugegraph/job/algorithm/cent/BetweennessCentralityAlgorithmV2.java @@ -116,7 +116,7 @@ public class BetweennessCentralityAlgorithmV2 extends AbstractCentAlgorithm { protected void meetNode(Id currentVertex, BetweennessNode currentNode, Id parentVertex, BetweennessNode parentNode, boolean firstTime) { - currentNode.addParentNodeIfNeeded(parentNode, parentVertex); + currentNode.addParentNode(parentNode, parentVertex); } @Override diff --git a/hugegraph-core/src/main/java/com/baidu/hugegraph/job/algorithm/cent/StressCentralityAlgorithmV2.java b/hugegraph-core/src/main/java/com/baidu/hugegraph/job/algorithm/cent/StressCentralityAlgorithmV2.java index b01486b7e..bbce4d7ad 100644 --- a/hugegraph-core/src/main/java/com/baidu/hugegraph/job/algorithm/cent/StressCentralityAlgorithmV2.java +++ b/hugegraph-core/src/main/java/com/baidu/hugegraph/job/algorithm/cent/StressCentralityAlgorithmV2.java @@ -119,7 +119,7 @@ public class StressCentralityAlgorithmV2 extends AbstractCentAlgorithm { protected void meetNode(Id currentVertex, StressNode currentNode, Id parentVertex, StressNode parentNode, boolean firstTime) { - currentNode.addParentNodeIfNeeded(parentNode, parentVertex); + currentNode.addParentNode(parentNode, parentVertex); } @Override
