flink-issues mailing list archives

Site index · List index
Message view « Date » · « Thread »
Top « Date » · « Thread »
From "ASF GitHub Bot (JIRA)" <j...@apache.org>
Subject [jira] [Commented] (FLINK-2714) Port the Flink DataSet Triangle Count example to the Gelly library
Date Sat, 10 Oct 2015 11:59:05 GMT

    [ https://issues.apache.org/jira/browse/FLINK-2714?page=com.atlassian.jira.plugin.system.issuetabpanels:comment-tabpanel&focusedCommentId=14951799#comment-14951799
] 

ASF GitHub Bot commented on FLINK-2714:
---------------------------------------

Github user ssaumitra commented on a diff in the pull request:

    https://github.com/apache/flink/pull/1250#discussion_r41696647
  
    --- Diff: flink-libraries/flink-gelly/src/main/java/org/apache/flink/graph/library/TriangleCounter.java
---
    @@ -0,0 +1,339 @@
    +/*
    + * 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.common.functions.FlatMapFunction;
    +import org.apache.flink.api.common.functions.JoinFunction;
    +import org.apache.flink.api.common.functions.GroupReduceFunction;
    +import org.apache.flink.api.common.operators.Order;
    +import org.apache.flink.api.java.DataSet;
    +import org.apache.flink.api.java.functions.FunctionAnnotation;
    +import org.apache.flink.api.java.tuple.Tuple3;
    +import org.apache.flink.api.java.tuple.Tuple4;
    +import org.apache.flink.graph.Edge;
    +import org.apache.flink.graph.Graph;
    +import org.apache.flink.graph.GraphAlgorithm;
    +import org.apache.flink.types.NullValue;
    +import org.apache.flink.util.Collector;
    +
    +import java.util.ArrayList;
    +import java.util.Iterator;
    +import java.util.List;
    +
    +
    +/**
    + * This function returns number of triangles present in the input graph.
    + * A triangle consists of three edges that connect three vertices with each other.
    + * <p>
    + * <p>
    + * The basic algorithm works as follows:
    + * It groups all edges that share a common vertex and builds triads, i.e., triples of
vertices
    + * that are connected by two edges. Finally, all triads are filtered for which no third
edge exists
    + * that closes the triangle.
    + * <p>
    + * <p>
    + * For a group of <i>n</i> edges that share a common vertex, the number of
built triads is quadratic <i>((n*(n-1))/2)</i>.
    + * Therefore, an optimization of the algorithm is to group edges on the vertex with the
smaller output degree to
    + * reduce the number of triads.
    + * This implementation extends the basic algorithm by computing output degrees of edge
vertices and
    + * grouping on edges on the vertex with the smaller degree.
    + */
    +
    +public class TriangleCounter<K extends Comparable<K>, VV, EV> implements
GraphAlgorithm<K, VV, EV, DataSet<Integer>> {
    +	@Override
    +	public DataSet<Integer> run(Graph<K, VV, EV> input) throws Exception {
    +
    +		DataSet<Edge<K, EV>> edges = input.getEdges();
    +
    +		// annotate edges with degrees
    +		DataSet<EdgeWithDegrees<K>> edgesWithDegrees = edges.flatMap(new EdgeDuplicator<K,
EV>())
    +				.groupBy(0).sortGroup(1, Order.ASCENDING).reduceGroup(new DegreeCounter<K, EV>())
    +				.groupBy(EdgeWithDegrees.V1, EdgeWithDegrees.V2).reduce(new DegreeJoiner<K>());
    +
    +		// project edges by degrees
    +		DataSet<Edge<K, NullValue>> edgesByDegree = edgesWithDegrees.map(new EdgeByDegreeProjector<K>());
    +		// project edges by vertex id
    +		DataSet<Edge<K, NullValue>> edgesById = edgesByDegree.map(new EdgeByIdProjector<K>());
    +
    +		DataSet<Integer> triangles = edgesByDegree
    +				// build triads
    +				.groupBy(EdgeWithDegrees.V1).sortGroup(EdgeWithDegrees.V2, Order.ASCENDING)
    +				.reduceGroup(new TriadBuilder())
    +				// filter triads
    +				.join(edgesById).where(Triad.V2, Triad.V3).equalTo(0, 1).with(new TriadFilter<K>());
    --- End diff --
    
    Just FYI, vertices of Triad and edgesWithDegrees are referred with V1 and V2. And those
of edges are referred with indices 0 and 1. 
    IMHO, org.apache.flink.graph.Edge can also have static variables V1, V2 so that group
operators are more readable.


> Port the Flink DataSet Triangle Count example to the Gelly library
> ------------------------------------------------------------------
>
>                 Key: FLINK-2714
>                 URL: https://issues.apache.org/jira/browse/FLINK-2714
>             Project: Flink
>          Issue Type: Task
>          Components: Gelly
>    Affects Versions: 0.10
>         Environment: 
>            Reporter: Andra Lungu
>            Assignee: Saumitra Shahapure
>            Priority: Trivial
>              Labels: newbie, starter
>
> Currently, the Gelly library contains two methods for counting the number of triangles
in a graph: a vertex-centric version and a gather-apply-scatter version. 
> This issue proposes the addition of a third library method based on this Flink example:
> https://github.com/apache/flink/blob/master/flink-examples/flink-java-examples/src/main/java/org/apache/flink/examples/java/graph/EnumTrianglesOpt.java
> The only modification needed is an extra reduce step that takes the enumerated triangles
produced and yields a number. 



--
This message was sent by Atlassian JIRA
(v6.3.4#6332)

Mime
View raw message