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:25 UTC
[incubator-hugegraph] 22/33: add with_boundary parameter for betweeness (#42)
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 4caf2612163fbea82854739cc4be3732098043c0
Author: Jermy Li <li...@baidu.com>
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,