[ https://issues.apache.org/jira/browse/FLINK-2926?page=com.atlassian.jira.plugin.system.issuetabpanels:all-tabpanel ]
Flink Jira Bot updated FLINK-2926: ---------------------------------- Labels: algorithm requires-design-doc stale-minor (was: algorithm requires-design-doc) > 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-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)