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)