You are viewing a plain text version of this content. The canonical link for it is here.
Posted to issues@flink.apache.org by "Martijn Visser (Jira)" <ji...@apache.org> on 2022/10/19 11:50:00 UTC
[jira] [Closed] (FLINK-2926) Add a Strongly Connected Components Library Method
[ https://issues.apache.org/jira/browse/FLINK-2926?page=com.atlassian.jira.plugin.system.issuetabpanels:all-tabpanel ]
Martijn Visser closed FLINK-2926.
---------------------------------
Resolution: Won't Fix
Gelly has been removed, see FLINK-29668
> Add a Strongly Connected Components Library Method
> --------------------------------------------------
>
> Key: FLINK-2926
> URL: https://issues.apache.org/jira/browse/FLINK-2926
> Project: Flink
> Issue Type: New Feature
> Components: Library / Graph Processing (Gelly)
> Affects Versions: 0.10.0
> Reporter: Andra Lungu
> Assignee: Martin Liesenberg
> Priority: Not a Priority
> Labels: algorithm, requires-design-doc, stale-assigned
>
> 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
(v8.20.10#820010)