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 <[email protected]> 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
