flink-issues mailing list archives

Site index · List index
Message view « Date » · « Thread »
Top « Date » · « Thread »
From "Martin Liesenberg (JIRA)" <j...@apache.org>
Subject [jira] [Commented] (FLINK-2926) Add a Strongly Connected Components Library Method
Date Fri, 30 Oct 2015 12:34:27 GMT

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

Martin Liesenberg commented on FLINK-2926:
------------------------------------------

https://docs.google.com/document/d/10kwRoSjStCHpa8dr3vlwcOBTgyzT_X_b9E0OfGyY1Pg/edit?usp=sharing

A first draft based on what's in the ticket and the papers. Structured as proposed in the
contribution guide. Let me know what you think. :)


One thing is not quite clear to me yet: how do I express a termination criterion based on
a property of the graph and not in term of number of iterations. 

> Add a Strongly Connected Components Library Method
> --------------------------------------------------
>
>                 Key: FLINK-2926
>                 URL: https://issues.apache.org/jira/browse/FLINK-2926
>             Project: Flink
>          Issue Type: Task
>          Components: Gelly
>    Affects Versions: 0.10
>            Reporter: Andra Lungu
>            Assignee: Martin Liesenberg
>            Priority: Minor
>              Labels: requires-design-doc
>
> This algorithm operates in four main steps: 
> 1). Form the transposed graph (each vertex sends its id to its out neighbors which form
a transposedNeighbors set)
> 2). Trimming: every vertex which has only incoming or outgoing edges sets colorID to
its own value and becomes inactive. 
> 3). Forward traversal: 
>                    Start phase: propagate id to out neighbors 
>                    Rest phase: update the colorID with the minimum value seen until convergence
> 4). Backward traversal: 
>                      Start: if the vertex id is equal to its color id propagate the value
to transposedNeighbors
>                      Rest: each vertex that receives a message equal to its colorId will
propagate its colorId to the transposed graph and becomes inactive. 
> More info in section 3.1 of this paper: http://ilpubs.stanford.edu:8090/1077/3/p535-salihoglu.pdf
> or in section 6 of this paper: http://www.vldb.org/pvldb/vol7/p1821-yan.pdf  



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

Mime
View raw message