[
https://issues.apache.org/jira/browse/FLINK-2926?page=com.atlassian.jira.plugin.system.issuetabpanels:comment-tabpanel&focusedCommentId=17329567#comment-17329567
]
Flink Jira Bot commented on FLINK-2926:
---------------------------------------
This issue is assigned but has not received an update in 7 days so it has been
labeled "stale-assigned". If you are still working on the issue, please give an
update and remove the label. If you are no longer working on the issue, please
unassign so someone else may work on it. In 7 days the issue will be
automatically unassigned.
> 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: Library / Graph Processing (Gelly)
> Affects Versions: 0.10.0
> Reporter: Andra Lungu
> Assignee: Martin Liesenberg
> Priority: Minor
> Labels: algorithm, requires-design-doc, stale-assigned,
> stale-minor
>
> 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.3.4#803005)
