You are viewing a plain text version of this content. The canonical link for it is here.
Posted to commits@hugegraph.apache.org by ji...@apache.org on 2022/11/09 10:25:32 UTC
[incubator-hugegraph] 29/33: performance improvement: the meetNode is invoked only when node.distance is parent.distance() + 1 (#69)
This is an automated email from the ASF dual-hosted git repository.
jin pushed a commit to branch master
in repository https://gitbox.apache.org/repos/asf/incubator-hugegraph.git
commit f63f056034e4ba1662251cc49298b40c60a21507
Author: houzhizhen <ho...@163.com>
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