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:23 UTC
[incubator-hugegraph] 20/33: add skipi_isolated param for louvain (#37)
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 148d6250dc5c8d76a5856c1b25a771ab463d63dc
Author: Jermy Li <li...@baidu.com>
AuthorDate: Fri Aug 14 18:02:11 2020 +0800
add skipi_isolated param for louvain (#37)
Change-Id: Ib24ede9c20bb2c23a3f06fe72c53be2342295fd4
---
.../baidu/hugegraph/job/algorithm/AbstractAlgorithm.java | 1 +
.../hugegraph/job/algorithm/comm/LouvainAlgorithm.java | 11 ++++++++++-
.../hugegraph/job/algorithm/comm/LouvainTraverser.java | 13 ++++++++++---
3 files changed, 21 insertions(+), 4 deletions(-)
diff --git a/hugegraph-core/src/main/java/com/baidu/hugegraph/job/algorithm/AbstractAlgorithm.java b/hugegraph-core/src/main/java/com/baidu/hugegraph/job/algorithm/AbstractAlgorithm.java
index 0d9c79a9f..ffe55e8f6 100644
--- a/hugegraph-core/src/main/java/com/baidu/hugegraph/job/algorithm/AbstractAlgorithm.java
+++ b/hugegraph-core/src/main/java/com/baidu/hugegraph/job/algorithm/AbstractAlgorithm.java
@@ -88,6 +88,7 @@ public abstract class AbstractAlgorithm implements Algorithm {
public static final String KEY_PRECISION = "precision";
public static final String KEY_SHOW_MOD= "show_modularity";
public static final String KEY_SHOW_COMM = "show_community";
+ public static final String KEY_SKIP_ISOLATED = "skip_isolated";
public static final String KEY_CLEAR = "clear";
public static final String KEY_CAPACITY = "capacity";
public static final String KEY_LIMIT = "limit";
diff --git a/hugegraph-core/src/main/java/com/baidu/hugegraph/job/algorithm/comm/LouvainAlgorithm.java b/hugegraph-core/src/main/java/com/baidu/hugegraph/job/algorithm/comm/LouvainAlgorithm.java
index ab6e0f214..3b3b0a6b8 100644
--- a/hugegraph-core/src/main/java/com/baidu/hugegraph/job/algorithm/comm/LouvainAlgorithm.java
+++ b/hugegraph-core/src/main/java/com/baidu/hugegraph/job/algorithm/comm/LouvainAlgorithm.java
@@ -44,6 +44,7 @@ public class LouvainAlgorithm extends AbstractCommAlgorithm {
sourceCLabel(parameters);
showModularity(parameters);
showCommunity(parameters);
+ skipIsolated(parameters);
clearPass(parameters);
workers(parameters);
}
@@ -53,6 +54,7 @@ public class LouvainAlgorithm extends AbstractCommAlgorithm {
String label = sourceLabel(parameters);
String clabel = sourceCLabel(parameters);
long degree = degree(parameters);
+ boolean skipIsolated = skipIsolated(parameters);
int workers = workers(parameters);
Long clearPass = clearPass(parameters);
@@ -61,7 +63,7 @@ public class LouvainAlgorithm extends AbstractCommAlgorithm {
try (LouvainTraverser traverser = new LouvainTraverser(
job, workers, degree,
- label, clabel)) {
+ label, clabel, skipIsolated)) {
if (clearPass != null) {
return traverser.clearPass(clearPass.intValue());
} else if (modPass != null) {
@@ -96,4 +98,11 @@ public class LouvainAlgorithm extends AbstractCommAlgorithm {
HugeTraverser.checkNonNegative(pass, KEY_SHOW_MOD);
return pass;
}
+
+ protected static boolean skipIsolated(Map<String, Object> parameters) {
+ if (!parameters.containsKey(KEY_SKIP_ISOLATED)) {
+ return true;
+ }
+ return ParameterUtil.parameterBoolean(parameters, KEY_SKIP_ISOLATED);
+ }
}
diff --git a/hugegraph-core/src/main/java/com/baidu/hugegraph/job/algorithm/comm/LouvainTraverser.java b/hugegraph-core/src/main/java/com/baidu/hugegraph/job/algorithm/comm/LouvainTraverser.java
index 3a8a83f53..c6cd24fab 100644
--- a/hugegraph-core/src/main/java/com/baidu/hugegraph/job/algorithm/comm/LouvainTraverser.java
+++ b/hugegraph-core/src/main/java/com/baidu/hugegraph/job/algorithm/comm/LouvainTraverser.java
@@ -78,18 +78,22 @@ public class LouvainTraverser extends AlgoTraverser {
private final String sourceLabel;
private final String sourceCLabel;
private final long degree;
+ private final boolean skipIsolated;
+
private final Cache cache;
private long m;
private String passLabel;
public LouvainTraverser(UserJob<Object> job, int workers, long degree,
- String sourceLabel, String sourceCLabel) {
+ String sourceLabel, String sourceCLabel,
+ boolean skipIsolated) {
super(job, LouvainAlgorithm.ALGO_NAME, workers);
this.g = this.graph().traversal();
this.sourceLabel = sourceLabel;
this.sourceCLabel = sourceCLabel;
this.degree = degree;
+ this.skipIsolated = skipIsolated;
this.m = 1L;
this.passLabel = "";
@@ -355,6 +359,9 @@ public class LouvainTraverser extends AlgoTraverser {
private boolean moveCommunity(Vertex v, int pass) {
// move vertex to neighbor community if needed
List<Edge> nbs = neighbors((Id) v.id());
+ if (this.skipIsolated && pass == 0 && nbs.isEmpty()) {
+ return false;
+ }
Community c = communityOfVertex(v, nbs);
double ki = kinOfVertex(v) + weightOfVertex(v, nbs);
// update community of v if △Q changed
@@ -448,7 +455,7 @@ public class LouvainTraverser extends AlgoTraverser {
LOG.info("Merge community for pass {}", pass);
// merge each community as a vertex
Collection<Pair<Community, Set<Id>>> comms = this.cache.communities();
- assert this.allMembersExist(comms, pass - 1);
+ assert this.skipIsolated || this.allMembersExist(comms, pass - 1);
this.cache.resetVertexWeight();
Consumers<Pair<Community, Set<Id>>> consumers = new Consumers<>(
@@ -479,7 +486,7 @@ public class LouvainTraverser extends AlgoTraverser {
}
this.graph().tx().commit();
- assert this.allMembersExist(pass);
+ assert this.skipIsolated || this.allMembersExist(pass);
// reset communities
this.cache.reset();