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 8e5296612892269e2a0bcde9cee351c32d388a61 Author: Jermy Li <[email protected]> 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();
