[ https://issues.apache.org/jira/browse/FLINK-2570?page=com.atlassian.jira.plugin.system.issuetabpanels:comment-tabpanel&focusedCommentId=14711345#comment-14711345 ]
ASF GitHub Bot commented on FLINK-2570: --------------------------------------- Github user vasia commented on a diff in the pull request: https://github.com/apache/flink/pull/1054#discussion_r37869769 --- Diff: flink-staging/flink-gelly/src/main/java/org/apache/flink/graph/library/GSATriangleCount.java --- @@ -0,0 +1,187 @@ +/* + * 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 org.apache.flink.graph.library; + + +import org.apache.flink.api.common.functions.MapFunction; +import org.apache.flink.api.common.functions.ReduceFunction; +import org.apache.flink.api.java.DataSet; +import org.apache.flink.api.java.ExecutionEnvironment; +import org.apache.flink.api.java.tuple.Tuple1; +import org.apache.flink.api.java.tuple.Tuple2; +import org.apache.flink.graph.GraphAlgorithm; +import org.apache.flink.graph.ReduceNeighborsFunction; +import org.apache.flink.graph.Vertex; +import org.apache.flink.graph.Edge; +import org.apache.flink.graph.Triplet; +import org.apache.flink.graph.EdgeDirection; +import org.apache.flink.graph.Graph; +import org.apache.flink.types.NullValue; + +import java.util.TreeMap; + +/** + * Triangle Count Algorithm. + * + * This algorithm operates in three phases. First, vertices select neighbors with id greater than theirs + * and send messages to them. Each received message is then propagated to neighbors with higher id. + * Finally, if a node encounters the target id in the list of received messages, it increments the number + * of triangles found. + * + * This implementation is non - iterative. The total number of triangles can be determined by performing + * a single pass through the graph. + */ +public class GSATriangleCount implements + GraphAlgorithm<Long, NullValue, NullValue, DataSet<Tuple1<Integer>>> { + + @Override + public DataSet<Tuple1<Integer>> run(Graph<Long, NullValue, NullValue> input) throws Exception { + + ExecutionEnvironment env = input.getContext(); + + // order the edges so that src is always higher than trg + DataSet<Edge<Long, NullValue>> edges = input.getEdges() + .map(new OrderEdges()).distinct(); --- End diff -- this call to `distinct()` here means that basically if you have 2 edges a->b and b->a in the input, and they are both part of a triangle, then you only count it once? > Add a Triangle Count Library Method > ----------------------------------- > > Key: FLINK-2570 > URL: https://issues.apache.org/jira/browse/FLINK-2570 > Project: Flink > Issue Type: Task > Components: Gelly > Affects Versions: 0.10 > Reporter: Andra Lungu > Assignee: Andra Lungu > Priority: Minor > > The Gather-Sum-Apply-Scatter version of this algorithm receives an undirected > graph as input and outputs the total number of triangles formed by the > graph's edges. > The implementation consists of three phases: > 1). Select neighbours with id greater than the current vertex id. > Gather: no-op > Sum: create a set out of these neighbours > Apply: attach the computed values to the vertices > 2). Propagate each received value to neighbours with higher id (again using > GSA) > 3). Compute the number of Triangles by verifying if the final vertex contains > the sender's id in its list. -- This message was sent by Atlassian JIRA (v6.3.4#6332)