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 7c665f388d4e049433e23c140ff17ce2f0e90d53 Author: Jermy Li <[email protected]> AuthorDate: Wed Aug 19 12:58:50 2020 +0800 add with_boundary parameter for betweeness (#42) * improve betweeness by remove boundary vertex of path Change-Id: I76924daf8d9da113ab7a1aeac536c6080eccb296 * add with_boundary parameter for betweeness also fix lpa count comms with limit Change-Id: Iaf675cd87a8dc0b5ef75476144bc8141f2dd4385 --- .../hugegraph/job/algorithm/AbstractAlgorithm.java | 11 +++++++ .../job/algorithm/cent/AbstractCentAlgorithm.java | 35 ++++++++++++++++++++++ .../cent/BetweenessCentralityAlgorithm.java | 23 ++++++++++++-- .../job/algorithm/comm/LouvainTraverser.java | 11 ------- .../hugegraph/job/algorithm/comm/LpaAlgorithm.java | 6 ++-- 5 files changed, 69 insertions(+), 17 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 ffe55e8f6..064b1e344 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 @@ -23,6 +23,7 @@ import java.util.HashMap; import java.util.Iterator; import java.util.Map; import java.util.Map.Entry; +import java.util.NoSuchElementException; import java.util.Set; import java.util.concurrent.Callable; import java.util.concurrent.ExecutorService; @@ -454,6 +455,16 @@ public abstract class AbstractAlgorithm implements Algorithm { } } + protected <V extends Number> Number tryNext(GraphTraversal<?, V> iter) { + return this.execute(iter, () -> { + try { + return iter.next(); + } catch (NoSuchElementException e) { + return 0; + } + }); + } + protected void commitIfNeeded() { // commit if needed Transaction tx = this.graph().tx(); diff --git a/hugegraph-core/src/main/java/com/baidu/hugegraph/job/algorithm/cent/AbstractCentAlgorithm.java b/hugegraph-core/src/main/java/com/baidu/hugegraph/job/algorithm/cent/AbstractCentAlgorithm.java index 19da8e968..fd8453fff 100644 --- a/hugegraph-core/src/main/java/com/baidu/hugegraph/job/algorithm/cent/AbstractCentAlgorithm.java +++ b/hugegraph-core/src/main/java/com/baidu/hugegraph/job/algorithm/cent/AbstractCentAlgorithm.java @@ -19,7 +19,9 @@ package com.baidu.hugegraph.job.algorithm.cent; +import java.util.Collections; import java.util.HashMap; +import java.util.Iterator; import java.util.List; import java.util.Map; @@ -32,15 +34,21 @@ import org.apache.tinkerpop.gremlin.process.traversal.dsl.graph.__; import org.apache.tinkerpop.gremlin.structure.Column; import org.apache.tinkerpop.gremlin.structure.Direction; import org.apache.tinkerpop.gremlin.structure.Vertex; +import org.slf4j.Logger; import com.baidu.hugegraph.backend.id.Id; +import com.baidu.hugegraph.iterator.MapperIterator; import com.baidu.hugegraph.job.UserJob; import com.baidu.hugegraph.job.algorithm.AbstractAlgorithm; import com.baidu.hugegraph.structure.HugeElement; +import com.baidu.hugegraph.structure.HugeVertex; import com.baidu.hugegraph.type.define.Directions; +import com.baidu.hugegraph.util.Log; public abstract class AbstractCentAlgorithm extends AbstractAlgorithm { + private static final Logger LOG = Log.logger(AbstractCentAlgorithm.class); + @Override public String category() { return CATEGORY_CENT; @@ -161,6 +169,33 @@ public abstract class AbstractCentAlgorithm extends AbstractAlgorithm { }); } + protected GraphTraversal<Vertex, Id> substractPath( + GraphTraversal<Vertex, Vertex> t, + boolean withBoundary) { + // t.select(Pop.all, "v").unfold().id() + return t.select(Pop.all, "v").flatMap(it -> { + List<?> path = (List<?>) it.get(); + if (withBoundary) { + @SuppressWarnings("unchecked") + Iterator<HugeVertex> items = (Iterator<HugeVertex>) + path.iterator(); + return new MapperIterator<>(items, v -> v.id()); + } + int len = path.size(); + if (len < 3) { + return Collections.emptyIterator(); + } + + LOG.debug("CentAlgorithm substract path: {}", path); + path.remove(path.size() -1); + path.remove(0); + @SuppressWarnings("unchecked") + Iterator<HugeVertex> items = (Iterator<HugeVertex>) + path.iterator(); + return new MapperIterator<>(items, v -> v.id()); + }); + } + protected GraphTraversal<Vertex, ?> topN(GraphTraversal<Vertex, ?> t, long topN) { if (topN > 0L || topN == NO_LIMIT) { diff --git a/hugegraph-core/src/main/java/com/baidu/hugegraph/job/algorithm/cent/BetweenessCentralityAlgorithm.java b/hugegraph-core/src/main/java/com/baidu/hugegraph/job/algorithm/cent/BetweenessCentralityAlgorithm.java index 465c6f96c..968f636ba 100644 --- a/hugegraph-core/src/main/java/com/baidu/hugegraph/job/algorithm/cent/BetweenessCentralityAlgorithm.java +++ b/hugegraph-core/src/main/java/com/baidu/hugegraph/job/algorithm/cent/BetweenessCentralityAlgorithm.java @@ -22,21 +22,29 @@ package com.baidu.hugegraph.job.algorithm.cent; import java.util.Map; import org.apache.tinkerpop.gremlin.process.traversal.P; -import org.apache.tinkerpop.gremlin.process.traversal.Pop; import org.apache.tinkerpop.gremlin.process.traversal.dsl.graph.GraphTraversal; import org.apache.tinkerpop.gremlin.process.traversal.dsl.graph.__; import org.apache.tinkerpop.gremlin.structure.Vertex; import com.baidu.hugegraph.job.UserJob; import com.baidu.hugegraph.type.define.Directions; +import com.baidu.hugegraph.util.ParameterUtil; public class BetweenessCentralityAlgorithm extends AbstractCentAlgorithm { + public static final String KEY_WITH_BOUNDARY = "with_boundary"; + @Override public String name() { return "betweeness_centrality"; } + @Override + public void checkParameters(Map<String, Object> parameters) { + super.checkParameters(parameters); + withBoundary(parameters); + } + @Override public Object call(UserJob<Object> job, Map<String, Object> parameters) { try (Traverser traverser = new Traverser(job)) { @@ -45,6 +53,7 @@ public class BetweenessCentralityAlgorithm extends AbstractCentAlgorithm { depth(parameters), degree(parameters), sample(parameters), + withBoundary(parameters), sourceLabel(parameters), sourceSample(parameters), sourceCLabel(parameters), @@ -52,6 +61,13 @@ public class BetweenessCentralityAlgorithm extends AbstractCentAlgorithm { } } + protected static boolean withBoundary(Map<String, Object> parameters) { + if (!parameters.containsKey(KEY_WITH_BOUNDARY)) { + return false; + } + return ParameterUtil.parameterBoolean(parameters, KEY_WITH_BOUNDARY); + } + private static class Traverser extends AbstractCentAlgorithm.Traverser { public Traverser(UserJob<Object> job) { @@ -63,6 +79,7 @@ public class BetweenessCentralityAlgorithm extends AbstractCentAlgorithm { int depth, long degree, long sample, + boolean withBoundary, String sourceLabel, long sourceSample, String sourceCLabel, @@ -79,8 +96,8 @@ public class BetweenessCentralityAlgorithm extends AbstractCentAlgorithm { t = t.emit().until(__.loops().is(P.gte(depth))); t = filterNonShortestPath(t, false); - GraphTraversal<Vertex, ?> tg = t.select(Pop.all, "v") - .unfold().id().groupCount(); + GraphTraversal<Vertex, ?> tg = this.substractPath(t, withBoundary) + .groupCount(); GraphTraversal<Vertex, ?> tLimit = topN(tg, topN); return this.execute(tLimit, () -> tLimit.next()); 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 c6cd24fab..42ac3e990 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 @@ -28,7 +28,6 @@ import java.util.Iterator; import java.util.List; import java.util.Map; import java.util.Map.Entry; -import java.util.NoSuchElementException; import java.util.Objects; import java.util.Set; import java.util.concurrent.ConcurrentHashMap; @@ -649,16 +648,6 @@ public class LouvainTraverser extends AlgoTraverser { return q; } - private <V extends Number> Number tryNext(GraphTraversal<?, V> iter) { - return this.execute(iter, () -> { - try { - return iter.next(); - } catch (NoSuchElementException e) { - return 0; - } - }); - } - public Collection<Object> showCommunity(String community) { final String C_PASS0 = labelOfPassN(0); Collection<Object> comms = Arrays.asList(community); diff --git a/hugegraph-core/src/main/java/com/baidu/hugegraph/job/algorithm/comm/LpaAlgorithm.java b/hugegraph-core/src/main/java/com/baidu/hugegraph/job/algorithm/comm/LpaAlgorithm.java index 8b54241fe..973e93f7b 100644 --- a/hugegraph-core/src/main/java/com/baidu/hugegraph/job/algorithm/comm/LpaAlgorithm.java +++ b/hugegraph-core/src/main/java/com/baidu/hugegraph/job/algorithm/comm/LpaAlgorithm.java @@ -117,9 +117,9 @@ public class LpaAlgorithm extends AbstractCommAlgorithm { } } - long communities = this.graph().traversal().V().limit(100000L) - .groupCount().by(C_LABEL) - .count(Scope.local).next(); + Number communities = tryNext(this.graph().traversal().V() + .groupCount().by(C_LABEL) + .count(Scope.local)); return ImmutableMap.of("iteration_times", times, "last_precision", changedPercent, "times", maxTimes,
