Andra Lungu created FLINK-2926:
----------------------------------
Summary: 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
Priority: 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
(v6.3.4#6332)
