You are viewing a plain text version of this content. The canonical link for it is here.
Posted to commits@hugegraph.apache.org by zh...@apache.org on 2022/11/26 06:28:16 UTC
[incubator-hugegraph-computer] branch improve_trianglecount_cc created (now 67c927e3)
This is an automated email from the ASF dual-hosted git repository.
zhaocong pushed a change to branch improve_trianglecount_cc
in repository https://gitbox.apache.org/repos/asf/incubator-hugegraph-computer.git
at 67c927e3 improve TriangleCount and ClusteringCoefficient
This branch includes the following new commits:
new 67c927e3 improve TriangleCount and ClusteringCoefficient
The 1 revisions listed above as "new" are entirely new to this
repository and will be described in separate emails. The revisions
listed as "add" were already present in the repository and have only
been added to this reference.
[incubator-hugegraph-computer] 01/01: improve TriangleCount and ClusteringCoefficient
Posted by zh...@apache.org.
This is an automated email from the ASF dual-hosted git repository.
zhaocong pushed a commit to branch improve_trianglecount_cc
in repository https://gitbox.apache.org/repos/asf/incubator-hugegraph-computer.git
commit 67c927e33c27f8ac331cead4215b68640bdb3e8a
Author: coderzc <zh...@apache.org>
AuthorDate: Sat Nov 26 14:28:04 2022 +0800
improve TriangleCount and ClusteringCoefficient
---
.../community/cc/ClusteringCoefficient.java | 64 +---------------------
.../community/cc/ClusteringCoefficientOutput.java | 2 +-
.../community/cc/ClusteringCoefficientValue.java | 16 +++---
.../community/trianglecount/TriangleCount.java | 40 ++++++++------
.../trianglecount/TriangleCountValue.java | 18 +++---
.../hugegraph/computer/core/graph/value/IdSet.java | 5 ++
.../computer/core/graph/value/ListValue.java | 14 ++---
7 files changed, 55 insertions(+), 104 deletions(-)
diff --git a/computer-algorithm/src/main/java/com/baidu/hugegraph/computer/algorithm/community/cc/ClusteringCoefficient.java b/computer-algorithm/src/main/java/com/baidu/hugegraph/computer/algorithm/community/cc/ClusteringCoefficient.java
index 6269349f..24813294 100644
--- a/computer-algorithm/src/main/java/com/baidu/hugegraph/computer/algorithm/community/cc/ClusteringCoefficient.java
+++ b/computer-algorithm/src/main/java/com/baidu/hugegraph/computer/algorithm/community/cc/ClusteringCoefficient.java
@@ -19,17 +19,12 @@
package com.baidu.hugegraph.computer.algorithm.community.cc;
-import java.util.HashSet;
import java.util.Iterator;
-import java.util.Set;
+import com.baidu.hugegraph.computer.algorithm.community.trianglecount.TriangleCount;
import com.baidu.hugegraph.computer.core.config.Config;
-import com.baidu.hugegraph.computer.core.graph.edge.Edge;
-import com.baidu.hugegraph.computer.core.graph.edge.Edges;
-import com.baidu.hugegraph.computer.core.graph.id.Id;
import com.baidu.hugegraph.computer.core.graph.value.IdList;
import com.baidu.hugegraph.computer.core.graph.vertex.Vertex;
-import com.baidu.hugegraph.computer.core.worker.Computation;
import com.baidu.hugegraph.computer.core.worker.ComputationContext;
/**
@@ -50,7 +45,7 @@ import com.baidu.hugegraph.computer.core.worker.ComputationContext;
* v represents one vertex, T represents the triangles of current vertex,
* D represents the degree of current vertex
*/
-public class ClusteringCoefficient implements Computation<IdList> {
+public class ClusteringCoefficient extends TriangleCount {
@Override
public String name() {
@@ -80,63 +75,10 @@ public class ClusteringCoefficient implements Computation<IdList> {
@Override
public void compute(ComputationContext context, Vertex vertex, Iterator<IdList> messages) {
- Integer count = this.triangleCount(context, vertex, messages);
+ Integer count = super.triangleCount(context, vertex, messages);
if (count != null) {
((ClusteringCoefficientValue) vertex.value()).count(count);
vertex.inactivate();
}
}
-
- private Integer triangleCount(ComputationContext context, Vertex vertex,
- Iterator<IdList> messages) {
- IdList neighbors = ((ClusteringCoefficientValue) vertex.value()).idList();
-
- if (context.superstep() == 1) {
- // Collect outgoing neighbors
- Set<Id> outNeighbors = getOutNeighbors(vertex);
- neighbors.addAll(outNeighbors);
-
- // Collect incoming neighbors
- while (messages.hasNext()) {
- IdList idList = messages.next();
- assert idList.size() == 1;
- Id inId = idList.get(0);
- if (!outNeighbors.contains(inId)) {
- neighbors.add(inId);
- }
- }
- // TODO: Save degree to vertex value here (optional)
- // Send all neighbors to neighbors
- for (Id targetId : neighbors.values()) {
- context.sendMessage(targetId, neighbors);
- }
- } else if (context.superstep() == 2) {
- int count = 0;
-
- Set<Id> allNeighbors = new HashSet<>(neighbors.values());
- while (messages.hasNext()) {
- IdList twoDegreeNeighbors = messages.next();
- for (Id twoDegreeNeighbor : twoDegreeNeighbors.values()) {
- if (allNeighbors.contains(twoDegreeNeighbor)) {
- count++;
- }
- }
- }
-
- return count >> 1;
- }
- return null;
- }
-
- private static Set<Id> getOutNeighbors(Vertex vertex) {
- Set<Id> outNeighbors = new HashSet<>();
- Edges edges = vertex.edges();
- for (Edge edge : edges) {
- Id targetId = edge.targetId();
- if (!vertex.id().equals(targetId)) {
- outNeighbors.add(targetId);
- }
- }
- return outNeighbors;
- }
}
diff --git a/computer-algorithm/src/main/java/com/baidu/hugegraph/computer/algorithm/community/cc/ClusteringCoefficientOutput.java b/computer-algorithm/src/main/java/com/baidu/hugegraph/computer/algorithm/community/cc/ClusteringCoefficientOutput.java
index 3f1c68b2..0d7ed78f 100644
--- a/computer-algorithm/src/main/java/com/baidu/hugegraph/computer/algorithm/community/cc/ClusteringCoefficientOutput.java
+++ b/computer-algorithm/src/main/java/com/baidu/hugegraph/computer/algorithm/community/cc/ClusteringCoefficientOutput.java
@@ -49,7 +49,7 @@ public class ClusteringCoefficientOutput extends HugeGraphOutput<Float> {
new org.apache.hugegraph.structure.graph.Vertex(null);
hugeVertex.id(vertex.id().asObject());
float triangle = ((ClusteringCoefficientValue) vertex.value()).count();
- int degree = ((ClusteringCoefficientValue) vertex.value()).idList().size();
+ int degree = ((ClusteringCoefficientValue) vertex.value()).idSet().value().size();
hugeVertex.property(this.name(), 2 * triangle / degree / (degree - 1));
return hugeVertex;
}
diff --git a/computer-algorithm/src/main/java/com/baidu/hugegraph/computer/algorithm/community/cc/ClusteringCoefficientValue.java b/computer-algorithm/src/main/java/com/baidu/hugegraph/computer/algorithm/community/cc/ClusteringCoefficientValue.java
index 6892afd1..ee1e0577 100644
--- a/computer-algorithm/src/main/java/com/baidu/hugegraph/computer/algorithm/community/cc/ClusteringCoefficientValue.java
+++ b/computer-algorithm/src/main/java/com/baidu/hugegraph/computer/algorithm/community/cc/ClusteringCoefficientValue.java
@@ -21,7 +21,7 @@ package com.baidu.hugegraph.computer.algorithm.community.cc;
import java.io.IOException;
-import com.baidu.hugegraph.computer.core.graph.value.IdList;
+import com.baidu.hugegraph.computer.core.graph.value.IdSet;
import com.baidu.hugegraph.computer.core.graph.value.IntValue;
import com.baidu.hugegraph.computer.core.graph.value.Value;
import com.baidu.hugegraph.computer.core.io.RandomAccessInput;
@@ -32,18 +32,18 @@ import com.baidu.hugegraph.computer.core.io.RandomAccessOutput;
*/
public class ClusteringCoefficientValue implements Value.CustomizeValue<Integer> {
- private IdList idList;
+ private IdSet idSet;
private IntValue count;
private final IntValue degree;
public ClusteringCoefficientValue() {
- this.idList = new IdList();
+ this.idSet = new IdSet();
this.count = new IntValue();
this.degree = new IntValue();
}
- public IdList idList() {
- return this.idList;
+ public IdSet idSet() {
+ return this.idSet;
}
public long count() {
@@ -65,7 +65,7 @@ public class ClusteringCoefficientValue implements Value.CustomizeValue<Integer>
@Override
public ClusteringCoefficientValue copy() {
ClusteringCoefficientValue ccValue = new ClusteringCoefficientValue();
- ccValue.idList = this.idList.copy();
+ ccValue.idSet = this.idSet.copy();
ccValue.count = this.count.copy();
return ccValue;
}
@@ -77,13 +77,13 @@ public class ClusteringCoefficientValue implements Value.CustomizeValue<Integer>
@Override
public void read(RandomAccessInput in) throws IOException {
- this.idList.read(in);
+ this.idSet.read(in);
this.count.read(in);
}
@Override
public void write(RandomAccessOutput out) throws IOException {
- this.idList.write(out);
+ this.idSet.write(out);
this.count.write(out);
}
diff --git a/computer-algorithm/src/main/java/com/baidu/hugegraph/computer/algorithm/community/trianglecount/TriangleCount.java b/computer-algorithm/src/main/java/com/baidu/hugegraph/computer/algorithm/community/trianglecount/TriangleCount.java
index 7d3d0222..df0195f2 100644
--- a/computer-algorithm/src/main/java/com/baidu/hugegraph/computer/algorithm/community/trianglecount/TriangleCount.java
+++ b/computer-algorithm/src/main/java/com/baidu/hugegraph/computer/algorithm/community/trianglecount/TriangleCount.java
@@ -19,15 +19,17 @@
package com.baidu.hugegraph.computer.algorithm.community.trianglecount;
-
import java.util.HashSet;
import java.util.Iterator;
import java.util.Set;
+import org.apache.commons.lang3.tuple.Pair;
+
import com.baidu.hugegraph.computer.core.graph.edge.Edge;
import com.baidu.hugegraph.computer.core.graph.edge.Edges;
import com.baidu.hugegraph.computer.core.graph.id.Id;
import com.baidu.hugegraph.computer.core.graph.value.IdList;
+import com.baidu.hugegraph.computer.core.graph.value.IdSet;
import com.baidu.hugegraph.computer.core.graph.vertex.Vertex;
import com.baidu.hugegraph.computer.core.worker.Computation;
import com.baidu.hugegraph.computer.core.worker.ComputationContext;
@@ -46,11 +48,11 @@ public class TriangleCount implements Computation<IdList> {
@Override
public void compute0(ComputationContext context, Vertex vertex) {
- IdList selfId = new IdList();
+ IdSet selfId = new IdSet();
selfId.add(vertex.id());
context.sendMessageToAllEdgesIf(vertex, selfId, (ids, targetId) -> {
- return !ids.get(0).equals(targetId);
+ return !vertex.id().equals(targetId);
});
vertex.value(new TriangleCountValue());
}
@@ -65,56 +67,62 @@ public class TriangleCount implements Computation<IdList> {
}
}
- private Integer triangleCount(ComputationContext context, Vertex vertex,
- Iterator<IdList> messages) {
- IdList neighbors = ((TriangleCountValue) vertex.value()).idList();
+ protected Integer triangleCount(ComputationContext context, Vertex vertex,
+ Iterator<IdList> messages) {
+ IdSet neighbors = ((TriangleCountValue) vertex.value()).idSet();
if (context.superstep() == 1) {
// Collect outgoing neighbors
- Set<Id> outNeighbors = getOutNeighbors(vertex);
- neighbors.addAll(outNeighbors);
+ Pair<Set<Id>, Set<Id>> outNeighbors = getOutNeighbors(vertex);
+ Set<Id> allOutNeighbors = outNeighbors.getLeft();
+ Set<Id> lessSelfOutNeighbors = outNeighbors.getRight();
// Collect incoming neighbors
while (messages.hasNext()) {
IdList idList = messages.next();
assert idList.size() == 1;
Id inId = idList.get(0);
- if (!outNeighbors.contains(inId)) {
- neighbors.add(inId);
+ allOutNeighbors.add(inId);
+ if (inId.compareTo(vertex.id()) < 0) {
+ lessSelfOutNeighbors.add(inId);
}
}
+ neighbors.addAll(lessSelfOutNeighbors);
// Send all neighbors to neighbors
- for (Id targetId : neighbors.values()) {
+ for (Id targetId : allOutNeighbors) {
context.sendMessage(targetId, neighbors);
}
} else if (context.superstep() == 2) {
int count = 0;
- Set<Id> allNeighbors = new HashSet<>(neighbors.values());
while (messages.hasNext()) {
IdList twoDegreeNeighbors = messages.next();
for (Id twoDegreeNeighbor : twoDegreeNeighbors.values()) {
- if (allNeighbors.contains(twoDegreeNeighbor)) {
+ if (neighbors.contains(twoDegreeNeighbor)) {
count++;
}
}
}
- return count >> 1;
+ return count;
}
return null;
}
- private static Set<Id> getOutNeighbors(Vertex vertex) {
+ private static Pair<Set<Id>, Set<Id>> getOutNeighbors(Vertex vertex) {
Set<Id> outNeighbors = new HashSet<>();
+ Set<Id> lessSelfOutNeighbors = new HashSet<>();
Edges edges = vertex.edges();
for (Edge edge : edges) {
Id targetId = edge.targetId();
if (!vertex.id().equals(targetId)) {
outNeighbors.add(targetId);
+ if (targetId.compareTo(vertex.id()) < 0) {
+ lessSelfOutNeighbors.add(targetId);
+ }
}
}
- return outNeighbors;
+ return Pair.of(outNeighbors, lessSelfOutNeighbors);
}
}
diff --git a/computer-algorithm/src/main/java/com/baidu/hugegraph/computer/algorithm/community/trianglecount/TriangleCountValue.java b/computer-algorithm/src/main/java/com/baidu/hugegraph/computer/algorithm/community/trianglecount/TriangleCountValue.java
index 91f1d0e4..d31260fa 100644
--- a/computer-algorithm/src/main/java/com/baidu/hugegraph/computer/algorithm/community/trianglecount/TriangleCountValue.java
+++ b/computer-algorithm/src/main/java/com/baidu/hugegraph/computer/algorithm/community/trianglecount/TriangleCountValue.java
@@ -23,7 +23,7 @@ import java.io.IOException;
import org.apache.commons.lang3.builder.ToStringBuilder;
-import com.baidu.hugegraph.computer.core.graph.value.IdList;
+import com.baidu.hugegraph.computer.core.graph.value.IdSet;
import com.baidu.hugegraph.computer.core.graph.value.IntValue;
import com.baidu.hugegraph.computer.core.graph.value.Value.CustomizeValue;
import com.baidu.hugegraph.computer.core.io.RandomAccessInput;
@@ -31,16 +31,16 @@ import com.baidu.hugegraph.computer.core.io.RandomAccessOutput;
public class TriangleCountValue implements CustomizeValue<Integer> {
- private IdList idList;
+ private IdSet idSet;
private IntValue count;
public TriangleCountValue() {
- this.idList = new IdList();
+ this.idSet = new IdSet();
this.count = new IntValue();
}
- public IdList idList() {
- return this.idList;
+ public IdSet idSet() {
+ return this.idSet;
}
public long count() {
@@ -54,26 +54,26 @@ public class TriangleCountValue implements CustomizeValue<Integer> {
@Override
public TriangleCountValue copy() {
TriangleCountValue triangleCountValue = new TriangleCountValue();
- triangleCountValue.idList = this.idList.copy();
+ triangleCountValue.idSet = this.idSet.copy();
triangleCountValue.count = this.count.copy();
return triangleCountValue;
}
@Override
public void read(RandomAccessInput in) throws IOException {
- this.idList.read(in);
+ this.idSet.read(in);
this.count.read(in);
}
@Override
public void write(RandomAccessOutput out) throws IOException {
- this.idList.write(out);
+ this.idSet.write(out);
this.count.write(out);
}
@Override
public String toString() {
- return new ToStringBuilder(this).append("idList", this.idList)
+ return new ToStringBuilder(this).append("idSet", this.idSet)
.append("count", this.count).toString();
}
diff --git a/computer-api/src/main/java/com/baidu/hugegraph/computer/core/graph/value/IdSet.java b/computer-api/src/main/java/com/baidu/hugegraph/computer/core/graph/value/IdSet.java
index 469979dc..acf704ad 100644
--- a/computer-api/src/main/java/com/baidu/hugegraph/computer/core/graph/value/IdSet.java
+++ b/computer-api/src/main/java/com/baidu/hugegraph/computer/core/graph/value/IdSet.java
@@ -20,6 +20,7 @@
package com.baidu.hugegraph.computer.core.graph.value;
import java.io.IOException;
+import java.util.Collection;
import java.util.Collections;
import java.util.Set;
@@ -48,6 +49,10 @@ public class IdSet implements Tvalue<Set<Id>> {
this.values.addAll(other.values);
}
+ public void addAll(Collection<Id> other) {
+ this.values.addAll(other);
+ }
+
public boolean contains(Id id) {
return this.values.contains(id);
}
diff --git a/computer-api/src/main/java/com/baidu/hugegraph/computer/core/graph/value/ListValue.java b/computer-api/src/main/java/com/baidu/hugegraph/computer/core/graph/value/ListValue.java
index 1b78dc74..73b641fb 100644
--- a/computer-api/src/main/java/com/baidu/hugegraph/computer/core/graph/value/ListValue.java
+++ b/computer-api/src/main/java/com/baidu/hugegraph/computer/core/graph/value/ListValue.java
@@ -29,6 +29,7 @@ import java.util.NoSuchElementException;
import org.apache.commons.collections.CollectionUtils;
import org.apache.commons.collections.ListUtils;
+import org.apache.hugegraph.util.E;
import com.baidu.hugegraph.computer.core.common.ComputerContext;
import com.baidu.hugegraph.computer.core.common.SerialEnum;
@@ -36,9 +37,8 @@ import com.baidu.hugegraph.computer.core.graph.GraphFactory;
import com.baidu.hugegraph.computer.core.graph.value.Value.Tvalue;
import com.baidu.hugegraph.computer.core.io.RandomAccessInput;
import com.baidu.hugegraph.computer.core.io.RandomAccessOutput;
-import org.apache.hugegraph.util.E;
-public class ListValue<T extends Tvalue<?>> implements Tvalue<List<Object>> {
+public class ListValue<T extends Tvalue<?>> implements Tvalue<List<T>> {
private final GraphFactory graphFactory;
private ValueType elemType;
@@ -106,7 +106,7 @@ public class ListValue<T extends Tvalue<?>> implements Tvalue<List<Object>> {
}
public List<T> values() {
- return Collections.unmodifiableList(this.values);
+ return value();
}
public int size() {
@@ -114,12 +114,8 @@ public class ListValue<T extends Tvalue<?>> implements Tvalue<List<Object>> {
}
@Override
- public List<Object> value() {
- List<Object> list = new ArrayList<>(this.values.size());
- for (T value : this.values) {
- list.add(value.value());
- }
- return list;
+ public List<T> value() {
+ return Collections.unmodifiableList(this.values);
}
@Override