javeme commented on code in PR #108: URL: https://github.com/apache/incubator-hugegraph-computer/pull/108#discussion_r1011928222
########## computer-algorithm/src/main/java/com/baidu/hugegraph/computer/algorithm/community/cc/ClusteringCoefficient.java: ########## @@ -0,0 +1,145 @@ +/* + * Copyright 2017 HugeGraph Authors + * + * Licensed to the Apache Software Foundation (ASF) under one or more + * contributor license agreements. See the NOTICE file distributed with this + * work for additional information regarding copyright ownership. The ASF + * licenses this file to You under the Apache License, Version 2.0 (the + * "License"); you may not use this file except in compliance with the License. + * You may obtain a copy of the License at + * + * http://www.apache.org/licenses/LICENSE-2.0 + * + * Unless required by applicable law or agreed to in writing, software + * distributed under the License is distributed on an "AS IS" BASIS, WITHOUT + * WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. See the + * License for the specific language governing permissions and limitations + * under the License. + */ + +package com.baidu.hugegraph.computer.algorithm.community.cc; + + Review Comment: 2 blank lines ########## computer-algorithm/src/main/java/com/baidu/hugegraph/computer/algorithm/community/cc/ClusteringCoefficient.java: ########## @@ -0,0 +1,145 @@ +/* + * Copyright 2017 HugeGraph Authors + * + * Licensed to the Apache Software Foundation (ASF) under one or more + * contributor license agreements. See the NOTICE file distributed with this + * work for additional information regarding copyright ownership. The ASF + * licenses this file to You under the Apache License, Version 2.0 (the + * "License"); you may not use this file except in compliance with the License. + * You may obtain a copy of the License at + * + * http://www.apache.org/licenses/LICENSE-2.0 + * + * Unless required by applicable law or agreed to in writing, software + * distributed under the License is distributed on an "AS IS" BASIS, WITHOUT + * WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. See the + * License for the specific language governing permissions and limitations + * under the License. + */ + +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.TriangleCountValue; +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; + +/** + * ClusteringCoefficient(CC) algorithm could calculate local & the whole graph: + * 1. local cc: get triangles & degree for current vertex, calculate them + * 2. whole cc have 2 ways to get the result: (NOT SUPPORTED NOW) + * - sum all open & closed triangles in graph, and calculate the result + * - sum all local cc for each vertex, and use avg as the whole graph result + * <p> + * And we have 2 ways to count local cc: + * 1. if we already saved the triangles in each vertex, we can calculate only + * in superstep0/compute0 to get the result + * 2. if we want recount the triangles result, we can choose: + * - copy code from TriangleCount, then add extra logic + * - reuse code in TriangleCount (need solve compatible problem - TODO) + * <p> + * The formula of local CC is: C(v) = 2T / Dv(Dv - 1) + * v represents one vertex, T represents the triangles of current vertex, + * D represents the degree of current vertex + */ +public class ClusteringCoefficient implements Computation<IdList> { + + @Override + public String name() { + return "clustering_coefficient"; + } + + @Override + public String category() { + return "community"; + } + + @Override + public void init(Config config) { + // Reuse triangle count later + } + + @Override + public void compute0(ComputationContext context, Vertex vertex) { + IdList selfId = new IdList(); + selfId.add(vertex.id()); + + context.sendMessageToAllEdgesIf(vertex, selfId, (ids, targetId) -> { + return !ids.get(0).equals(targetId); + }); + vertex.value(new TriangleCountValue()); + } + + @Override + public void compute(ComputationContext context, Vertex vertex, Iterator<IdList> messages) { + Integer count = this.triangleCount(context, vertex, messages); + if (count != null) { + ((TriangleCountValue) vertex.value()).count(count); + vertex.inactivate(); + } + } + + private Integer triangleCount(ComputationContext context, Vertex vertex, + Iterator<IdList> messages) { + IdList neighbors = ((TriangleCountValue) 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); + } + } + // Save degree to vertex value here (optional) Review Comment: // TODO: Save xx ########## computer-algorithm/src/main/java/com/baidu/hugegraph/computer/algorithm/community/cc/ClusteringCoefficientValue.java: ########## @@ -0,0 +1,93 @@ +/* + * Copyright 2017 HugeGraph Authors + * + * Licensed to the Apache Software Foundation (ASF) under one or more + * contributor license agreements. See the NOTICE file distributed with this + * work for additional information regarding copyright ownership. The ASF + * licenses this file to You under the Apache License, Version 2.0 (the + * "License"); you may not use this file except in compliance with the License. + * You may obtain a copy of the License at + * + * http://www.apache.org/licenses/LICENSE-2.0 + * + * Unless required by applicable law or agreed to in writing, software + * distributed under the License is distributed on an "AS IS" BASIS, WITHOUT + * WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. See the + * License for the specific language governing permissions and limitations + * under the License. + */ + +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.IntValue; +import com.baidu.hugegraph.computer.core.graph.value.Value; +import com.baidu.hugegraph.computer.core.io.RandomAccessInput; +import com.baidu.hugegraph.computer.core.io.RandomAccessOutput; + +/** + * We should reuse triangle Review Comment: can improve the comment? ########## computer-algorithm/src/main/java/com/baidu/hugegraph/computer/algorithm/community/cc/ClusteringCoefficientValue.java: ########## @@ -0,0 +1,93 @@ +/* + * Copyright 2017 HugeGraph Authors + * + * Licensed to the Apache Software Foundation (ASF) under one or more + * contributor license agreements. See the NOTICE file distributed with this + * work for additional information regarding copyright ownership. The ASF + * licenses this file to You under the Apache License, Version 2.0 (the + * "License"); you may not use this file except in compliance with the License. + * You may obtain a copy of the License at + * + * http://www.apache.org/licenses/LICENSE-2.0 + * + * Unless required by applicable law or agreed to in writing, software + * distributed under the License is distributed on an "AS IS" BASIS, WITHOUT + * WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. See the + * License for the specific language governing permissions and limitations + * under the License. + */ + +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.IntValue; +import com.baidu.hugegraph.computer.core.graph.value.Value; +import com.baidu.hugegraph.computer.core.io.RandomAccessInput; +import com.baidu.hugegraph.computer.core.io.RandomAccessOutput; + +/** + * We should reuse triangle + */ +public class ClusteringCoefficientValue implements Value.CustomizeValue<Integer> { + private IdList idList; + private IntValue count; + private final IntValue degree; + + public ClusteringCoefficientValue() { + this.idList = new IdList(); + this.count = new IntValue(); + this.degree = new IntValue(); + } + + public IdList idList() { + return this.idList; + } + + public long count() { + return this.count.value(); + } + + public void count(Integer count) { + this.count.value(count); + } + + public int degree() { + return this.degree.value(); + } + + public void degree(Integer degree) { + this.degree.value(degree); + } + + @Override + public ClusteringCoefficientValue copy() { + ClusteringCoefficientValue ccValue = new ClusteringCoefficientValue(); + ccValue.idList = this.idList.copy(); + ccValue.count = this.count.copy(); + return ccValue; + } + + @Override + public Integer value() { + return this.count.value(); + } + + @Override + public void read(RandomAccessInput in) throws IOException { + this.idList.read(in); + this.count.read(in); + } + + @Override + public void write(RandomAccessOutput out) throws IOException { + this.idList.write(out); + this.count.write(out); + } + + @Override + public String toString() { + return "count" + this.count; Review Comment: just `return this.count.toString()`? ########## computer-algorithm/src/main/java/com/baidu/hugegraph/computer/algorithm/community/cc/ClusteringCoefficientValue.java: ########## @@ -0,0 +1,93 @@ +/* + * Copyright 2017 HugeGraph Authors + * + * Licensed to the Apache Software Foundation (ASF) under one or more + * contributor license agreements. See the NOTICE file distributed with this + * work for additional information regarding copyright ownership. The ASF + * licenses this file to You under the Apache License, Version 2.0 (the + * "License"); you may not use this file except in compliance with the License. + * You may obtain a copy of the License at + * + * http://www.apache.org/licenses/LICENSE-2.0 + * + * Unless required by applicable law or agreed to in writing, software + * distributed under the License is distributed on an "AS IS" BASIS, WITHOUT + * WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. See the + * License for the specific language governing permissions and limitations + * under the License. + */ + +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.IntValue; +import com.baidu.hugegraph.computer.core.graph.value.Value; +import com.baidu.hugegraph.computer.core.io.RandomAccessInput; +import com.baidu.hugegraph.computer.core.io.RandomAccessOutput; + +/** + * We should reuse triangle + */ +public class ClusteringCoefficientValue implements Value.CustomizeValue<Integer> { + private IdList idList; Review Comment: expect a blank line ########## computer-algorithm/src/main/java/com/baidu/hugegraph/computer/algorithm/community/cc/ClusteringCoefficientOutput.java: ########## @@ -0,0 +1,64 @@ +/* + * Copyright 2017 HugeGraph Authors + * + * Licensed to the Apache Software Foundation (ASF) under one or more + * contributor license agreements. See the NOTICE file distributed with this + * work for additional information regarding copyright ownership. The ASF + * licenses this file to You under the Apache License, Version 2.0 (the + * "License"); you may not use this file except in compliance with the License. + * You may obtain a copy of the License at + * + * http://www.apache.org/licenses/LICENSE-2.0 + * + * Unless required by applicable law or agreed to in writing, software + * distributed under the License is distributed on an "AS IS" BASIS, WITHOUT + * WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. See the + * License for the specific language governing permissions and limitations + * under the License. + */ + +package com.baidu.hugegraph.computer.algorithm.community.cc; + +import com.baidu.hugegraph.computer.algorithm.community.trianglecount.TriangleCountValue; +import com.baidu.hugegraph.computer.core.graph.vertex.Vertex; +import com.baidu.hugegraph.computer.core.output.hg.HugeGraphOutput; +import com.baidu.hugegraph.structure.constant.WriteType; + +/** + * Offer 2 ways to output: write-back + hdfs-file(TODO) + */ +public class ClusteringCoefficientOutput extends HugeGraphOutput<Float> { + + @Override + public String name() { + return "clustering_coefficient"; + } + + @Override + public void prepareSchema() { + this.client().schema().propertyKey(this.name()) + .asFloat() + .writeType(WriteType.OLAP_RANGE) + .ifNotExist() + .create(); + } + + @Override + protected com.baidu.hugegraph.structure.graph.Vertex constructHugeVertex(Vertex vertex) { + com.baidu.hugegraph.structure.graph.Vertex hugeVertex = + new com.baidu.hugegraph.structure.graph.Vertex(null); + hugeVertex.id(vertex.id().asObject()); + float triangle = ((TriangleCountValue) vertex.value()).count(); + int degree = ((TriangleCountValue) vertex.value()).idList().size(); + hugeVertex.property(this.name(), 2 * triangle / degree / (degree - 1)); + return hugeVertex; + } + + /* TODO: enhance it Review Comment: unused code? -- This is an automated message from the Apache Git Service. To respond to the message, please log on to GitHub and use the URL above to go to the specific comment. To unsubscribe, e-mail: [email protected] For queries about this service, please contact Infrastructure at: [email protected]
