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 d6ad2bcc710e72f4106c4ffd7d74bdd768896383 Author: Jermy Li <[email protected]> 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)
