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:09 UTC
[incubator-hugegraph] 06/33: add direction and label parameter for centrality algorithms (#13)
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 bc9822d7bbf997edff466ad26e89155949b2cdb1
Author: Jermy Li <li...@baidu.com>
AuthorDate: Wed Apr 15 16:02:44 2020 +0800
add direction and label parameter for centrality algorithms (#13)
Change-Id: I20b72ea0da673359e2bd21888010290efca81441
---
.../hugegraph/job/algorithm/AbstractAlgorithm.java | 10 ++++-
.../job/algorithm/cent/AbstractCentAlgorithm.java | 25 +++++++++++--
.../cent/BetweenessCentralityAlgorithm.java | 12 ++++--
.../cent/ClosenessCentralityAlgorithm.java | 12 ++++--
.../algorithm/cent/DegreeCentralityAlgorithm.java | 43 ++++++++++++++++------
.../cent/EigenvectorCentralityAlgorithm.java | 12 ++++--
6 files changed, 89 insertions(+), 25 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 e77473668..248a92bdb 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
@@ -49,6 +49,7 @@ import com.baidu.hugegraph.type.HugeType;
import com.baidu.hugegraph.type.define.Directions;
import com.baidu.hugegraph.type.define.HugeKeys;
import com.baidu.hugegraph.util.Bytes;
+import com.baidu.hugegraph.util.CollectionUtil;
import com.baidu.hugegraph.util.E;
import com.baidu.hugegraph.util.JsonUtil;
@@ -119,6 +120,9 @@ public abstract class AbstractAlgorithm implements Algorithm {
}
protected static Directions direction(Map<String, Object> parameters) {
+ if (!parameters.containsKey(KEY_DIRECTION)) {
+ return Directions.BOTH;
+ }
Object direction = parameter(parameters, KEY_DIRECTION);
return parseDirection(direction);
}
@@ -437,7 +441,11 @@ public abstract class AbstractAlgorithm implements Algorithm {
}
public Set<Map.Entry<K, MutableLong>> entrySet() {
- this.shrinkIfNeeded(this.topN);
+ if (this.tops.size() <= this.topN) {
+ this.tops = CollectionUtil.sortByValue(this.tops, false);
+ } else {
+ this.shrinkIfNeeded(this.topN);
+ }
return this.tops.entrySet();
}
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 c36743176..fb0c33d50 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
@@ -27,12 +27,14 @@ import org.apache.commons.lang3.tuple.Pair;
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.Direction;
import org.apache.tinkerpop.gremlin.structure.Vertex;
import com.baidu.hugegraph.backend.id.Id;
import com.baidu.hugegraph.job.Job;
import com.baidu.hugegraph.job.algorithm.AbstractAlgorithm;
import com.baidu.hugegraph.structure.HugeElement;
+import com.baidu.hugegraph.type.define.Directions;
public abstract class AbstractCentAlgorithm extends AbstractAlgorithm {
@@ -46,6 +48,8 @@ public abstract class AbstractCentAlgorithm extends AbstractAlgorithm {
depth(parameters);
degree(parameters);
sample(parameters);
+ direction(parameters);
+ edgeLabel(parameters);
sourceSample(parameters);
sourceLabel(parameters);
sourceCLabel(parameters);
@@ -83,9 +87,11 @@ public abstract class AbstractCentAlgorithm extends AbstractAlgorithm {
}
protected GraphTraversal<Vertex, Vertex> constructPath(
- GraphTraversal<Vertex, Vertex> t, long degree,
- long sample, String sourceLabel, String sourceCLabel) {
- GraphTraversal<?, Vertex> unit = constructPathUnit(degree, sample,
+ GraphTraversal<Vertex, Vertex> t, Directions dir,
+ String label, long degree, long sample,
+ String sourceLabel, String sourceCLabel) {
+ GraphTraversal<?, Vertex> unit = constructPathUnit(dir, label,
+ degree, sample,
sourceLabel,
sourceCLabel);
t = t.as("v").repeat(__.local(unit).simplePath().as("v"));
@@ -94,10 +100,21 @@ public abstract class AbstractCentAlgorithm extends AbstractAlgorithm {
}
protected GraphTraversal<Vertex, Vertex> constructPathUnit(
+ Directions dir, String label,
long degree, long sample,
String sourceLabel,
String sourceCLabel) {
- GraphTraversal<Vertex, Vertex> unit = __.both();
+ if (dir == null) {
+ dir = Directions.BOTH;
+ }
+ Direction direction = dir.direction();
+
+ String[] labels = {};
+ if (label != null) {
+ labels = new String[]{label};
+ }
+
+ GraphTraversal<Vertex, Vertex> unit = __.to(direction, labels);
if (sourceLabel != null) {
unit = unit.hasLabel(sourceLabel);
}
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 9a72d2f62..12e3acba0 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
@@ -31,6 +31,7 @@ import org.apache.tinkerpop.gremlin.structure.Column;
import org.apache.tinkerpop.gremlin.structure.Vertex;
import com.baidu.hugegraph.job.Job;
+import com.baidu.hugegraph.type.define.Directions;
public class BetweenessCentralityAlgorithm extends AbstractCentAlgorithm {
@@ -42,7 +43,9 @@ public class BetweenessCentralityAlgorithm extends AbstractCentAlgorithm {
@Override
public Object call(Job<Object> job, Map<String, Object> parameters) {
Traverser traverser = new Traverser(job);
- return traverser.betweenessCentrality(depth(parameters),
+ return traverser.betweenessCentrality(direction(parameters),
+ edgeLabel(parameters),
+ depth(parameters),
degree(parameters),
sample(parameters),
sourceLabel(parameters),
@@ -57,7 +60,9 @@ public class BetweenessCentralityAlgorithm extends AbstractCentAlgorithm {
super(job);
}
- public Object betweenessCentrality(int depth,
+ public Object betweenessCentrality(Directions direction,
+ String label,
+ int depth,
long degree,
long sample,
String sourceLabel,
@@ -71,7 +76,8 @@ public class BetweenessCentralityAlgorithm extends AbstractCentAlgorithm {
GraphTraversal<Vertex, Vertex> t = constructSource(sourceLabel,
sourceSample,
sourceCLabel);
- t = constructPath(t, degree, sample, sourceLabel, sourceCLabel);
+ t = constructPath(t, direction, label, degree, sample,
+ sourceLabel, sourceCLabel);
t = t.emit().until(__.loops().is(P.gte(depth)));
t = filterNonShortestPath(t);
diff --git a/hugegraph-core/src/main/java/com/baidu/hugegraph/job/algorithm/cent/ClosenessCentralityAlgorithm.java b/hugegraph-core/src/main/java/com/baidu/hugegraph/job/algorithm/cent/ClosenessCentralityAlgorithm.java
index 96e9709fe..cb64bd8bc 100644
--- a/hugegraph-core/src/main/java/com/baidu/hugegraph/job/algorithm/cent/ClosenessCentralityAlgorithm.java
+++ b/hugegraph-core/src/main/java/com/baidu/hugegraph/job/algorithm/cent/ClosenessCentralityAlgorithm.java
@@ -32,6 +32,7 @@ import org.apache.tinkerpop.gremlin.structure.Column;
import org.apache.tinkerpop.gremlin.structure.Vertex;
import com.baidu.hugegraph.job.Job;
+import com.baidu.hugegraph.type.define.Directions;
public class ClosenessCentralityAlgorithm extends AbstractCentAlgorithm {
@@ -51,7 +52,9 @@ public class ClosenessCentralityAlgorithm extends AbstractCentAlgorithm {
@Override
public Object call(Job<Object> job, Map<String, Object> parameters) {
Traverser traverser = new Traverser(job);
- return traverser.closenessCentrality(depth(parameters),
+ return traverser.closenessCentrality(direction(parameters),
+ edgeLabel(parameters),
+ depth(parameters),
degree(parameters),
sample(parameters),
sourceLabel(parameters),
@@ -66,7 +69,9 @@ public class ClosenessCentralityAlgorithm extends AbstractCentAlgorithm {
super(job);
}
- public Object closenessCentrality(int depth,
+ public Object closenessCentrality(Directions direction,
+ String label,
+ int depth,
long degree,
long sample,
String sourceLabel,
@@ -80,7 +85,8 @@ public class ClosenessCentralityAlgorithm extends AbstractCentAlgorithm {
GraphTraversal<Vertex, Vertex> t = constructSource(sourceLabel,
sourceSample,
sourceCLabel);
- t = constructPath(t, degree, sample, sourceLabel, sourceCLabel);
+ t = constructPath(t, direction, label, degree, sample,
+ sourceLabel, sourceCLabel);
t = t.emit().until(__.loops().is(P.gte(depth)));
t = filterNonShortestPath(t);
diff --git a/hugegraph-core/src/main/java/com/baidu/hugegraph/job/algorithm/cent/DegreeCentralityAlgorithm.java b/hugegraph-core/src/main/java/com/baidu/hugegraph/job/algorithm/cent/DegreeCentralityAlgorithm.java
index 5f6781b21..a19c09822 100644
--- a/hugegraph-core/src/main/java/com/baidu/hugegraph/job/algorithm/cent/DegreeCentralityAlgorithm.java
+++ b/hugegraph-core/src/main/java/com/baidu/hugegraph/job/algorithm/cent/DegreeCentralityAlgorithm.java
@@ -22,9 +22,9 @@ package com.baidu.hugegraph.job.algorithm.cent;
import java.util.Iterator;
import java.util.Map;
-import org.apache.tinkerpop.gremlin.process.traversal.dsl.graph.GraphTraversalSource;
import org.apache.tinkerpop.gremlin.structure.Edge;
import org.apache.tinkerpop.gremlin.structure.Vertex;
+import org.apache.tinkerpop.gremlin.util.iterator.IteratorUtils;
import com.baidu.hugegraph.backend.id.Id;
import com.baidu.hugegraph.job.Job;
@@ -41,6 +41,7 @@ public class DegreeCentralityAlgorithm extends AbstractCentAlgorithm {
@Override
public void checkParameters(Map<String, Object> parameters) {
direction(parameters);
+ edgeLabel(parameters);
top(parameters);
}
@@ -48,6 +49,7 @@ public class DegreeCentralityAlgorithm extends AbstractCentAlgorithm {
public Object call(Job<Object> job, Map<String, Object> parameters) {
Traverser traverser = new Traverser(job);
return traverser.degreeCentrality(direction(parameters),
+ edgeLabel(parameters),
top(parameters));
}
@@ -57,9 +59,11 @@ public class DegreeCentralityAlgorithm extends AbstractCentAlgorithm {
super(job);
}
- public Object degreeCentrality(Directions direction, long topN) {
+ public Object degreeCentrality(Directions direction,
+ String label,
+ long topN) {
if (direction == null || direction == Directions.BOTH) {
- return degreeCentrality(topN);
+ return degreeCentrality(label, topN);
}
assert direction == Directions.OUT || direction == Directions.IN;
assert topN >= 0L;
@@ -69,6 +73,7 @@ public class DegreeCentralityAlgorithm extends AbstractCentAlgorithm {
JsonMap degrees = new JsonMap();
TopMap<Id> tops = new TopMap<>(topN);
Id vertex = null;
+ Id labelId = this.getEdgeLabelId(label);
long degree = 0L;
long total = 0L;
@@ -77,12 +82,20 @@ public class DegreeCentralityAlgorithm extends AbstractCentAlgorithm {
HugeEdge edge = (HugeEdge) edges.next();
this.updateProgress(++total);
+ Id schemaLabel = edge.schemaLabel().id();
+ if (labelId != null && !labelId.equals(schemaLabel)) {
+ continue;
+ }
+
Id source = edge.ownerVertex().id();
if (source.equals(vertex)) {
+ // edges belong to same source vertex
degree++;
continue;
}
+
if (vertex != null) {
+ // next vertex found
if (topN <= 0L) {
degrees.append(vertex, degree);
} else {
@@ -107,25 +120,26 @@ public class DegreeCentralityAlgorithm extends AbstractCentAlgorithm {
return degrees.asJson();
}
- protected Object degreeCentrality(long topN) {
+ protected Object degreeCentrality(String label, long topN) {
assert topN >= 0L;
long total = 0L;
JsonMap degrees = new JsonMap();
TopMap<Id> tops = new TopMap<>(topN);
- GraphTraversalSource traversal = this.graph().traversal();
Iterator<Vertex> vertices = this.vertices();
degrees.startObject();
while (vertices.hasNext()) {
- Vertex source = vertices.next();
+ Id source = (Id) vertices.next().id();
this.updateProgress(++total);
- Long degree = traversal.V(source).bothE().count().next();
- if (topN <= 0L) {
- degrees.append(source.id(), degree);
- } else {
- tops.put((Id) source.id(), degree);
+ long degree = this.degree(source, label);
+ if (degree > 0L) {
+ if (topN <= 0L) {
+ degrees.append(source, degree);
+ } else {
+ tops.put(source, degree);
+ }
}
}
@@ -136,5 +150,12 @@ public class DegreeCentralityAlgorithm extends AbstractCentAlgorithm {
return degrees.asJson();
}
+
+ private long degree(Id source, String label) {
+ Id labelId = this.getEdgeLabelId(label);
+ Iterator<Edge> edges = this.edgesOfVertex(source, Directions.BOTH,
+ labelId, NO_LIMIT);
+ return IteratorUtils.count(edges);
+ }
}
}
diff --git a/hugegraph-core/src/main/java/com/baidu/hugegraph/job/algorithm/cent/EigenvectorCentralityAlgorithm.java b/hugegraph-core/src/main/java/com/baidu/hugegraph/job/algorithm/cent/EigenvectorCentralityAlgorithm.java
index d87fc7931..ce47417c4 100644
--- a/hugegraph-core/src/main/java/com/baidu/hugegraph/job/algorithm/cent/EigenvectorCentralityAlgorithm.java
+++ b/hugegraph-core/src/main/java/com/baidu/hugegraph/job/algorithm/cent/EigenvectorCentralityAlgorithm.java
@@ -30,6 +30,7 @@ import org.apache.tinkerpop.gremlin.structure.T;
import org.apache.tinkerpop.gremlin.structure.Vertex;
import com.baidu.hugegraph.job.Job;
+import com.baidu.hugegraph.type.define.Directions;
public class EigenvectorCentralityAlgorithm extends AbstractCentAlgorithm {
@@ -44,7 +45,9 @@ public class EigenvectorCentralityAlgorithm extends AbstractCentAlgorithm {
@Override
public Object call(Job<Object> job, Map<String, Object> parameters) {
Traverser traverser = new Traverser(job);
- return traverser.eigenvectorCentrality(depth(parameters),
+ return traverser.eigenvectorCentrality(direction(parameters),
+ edgeLabel(parameters),
+ depth(parameters),
degree(parameters),
sample(parameters),
sourceLabel(parameters),
@@ -59,7 +62,9 @@ public class EigenvectorCentralityAlgorithm extends AbstractCentAlgorithm {
super(job);
}
- public Object eigenvectorCentrality(int depth,
+ public Object eigenvectorCentrality(Directions direction,
+ String label,
+ int depth,
long degree,
long sample,
String sourceLabel,
@@ -83,7 +88,8 @@ public class EigenvectorCentralityAlgorithm extends AbstractCentAlgorithm {
GraphTraversal<Vertex, Vertex> t = constructSource(sourceLabel,
sourceSample,
sourceCLabel);
- GraphTraversal<?, Vertex> unit = constructPathUnit(degree, sample,
+ GraphTraversal<?, Vertex> unit = constructPathUnit(direction, label,
+ degree, sample,
sourceLabel,
sourceCLabel);
t = t.repeat(__.groupCount("m").by(T.id)