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:29:54 UTC
[incubator-hugegraph-computer] branch improve_trianglecount_cc updated (67c927e3 -> b90db763)
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
discard 67c927e3 improve TriangleCount and ClusteringCoefficient
new b90db763 improve TriangleCount and ClusteringCoefficient
This update added new revisions after undoing existing revisions.
That is to say, some revisions that were in the old version of the
branch are not in the new version. This situation occurs
when a user --force pushes a change and generates a repository
containing something like this:
* -- * -- B -- O -- O -- O (67c927e3)
\
N -- N -- N refs/heads/improve_trianglecount_cc (b90db763)
You should already have received notification emails for all of the O
revisions, and so the following emails describe only the N revisions
from the common base, B.
Any revisions marked "omit" are not gone; other references still
refer to them. Any revisions marked "discard" are gone forever.
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.
Summary of changes:
.../baidu/hugegraph/computer/core/graph/value/ListValue.java | 12 ++++++++----
1 file changed, 8 insertions(+), 4 deletions(-)
[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 b90db763dee4df4f1f5fb0a84fd2e2d01c6a8580
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 | 2 +-
7 files changed, 51 insertions(+), 96 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..230fee92 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,7 +37,6 @@ 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>> {