[
https://issues.apache.org/jira/browse/FLINK-2926?page=com.atlassian.jira.plugin.system.issuetabpanels:comment-tabpanel&focusedCommentId=15266205#comment-15266205
]
Vasia Kalavri commented on FLINK-2926:
--------------------------------------
Hi [~mliesenberg],
thank you for design document. If I understand correctly, the algorithm
requires a nested iteration, right?
Inside each round, we need to run 2 pregel steps (forward and backward
propagation) and a graph decomposition step. Currently, this is not easy to
express in Flink. Our Pregel abstraction does not support multiple phases and
does not have a master computation like Giraph does. We will probably need to
create a custom delta iteration and handle the different phases with
aggregators. Would you like to give it a try and sketch what this delta
iteration would look like?
> 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.0
> Reporter: Andra Lungu
> Assignee: Martin Liesenberg
> Priority: Minor
> Labels: requires-design-doc
>
> 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)
