[jira] [Commented] (FLINK-2926) Add a Strongly Connected Components Library Method

[Flink Jira Bot (Jira)]

[ 
https://issues.apache.org/jira/browse/FLINK-2926?page=com.atlassian.jira.plugin.system.issuetabpanels:comment-tabpanel=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)

[jira] [Commented] (FLINK-2926) Add a Strongly Connected Components Library Method

[Flink Jira Bot (Jira)]

[ 
https://issues.apache.org/jira/browse/FLINK-2926?page=com.atlassian.jira.plugin.system.issuetabpanels:comment-tabpanel=17321747#comment-17321747
 ] 

Flink Jira Bot commented on FLINK-2926:
---

This issue and all of its Sub-Tasks have not been updated for 180 days. So, it 
has been labeled "stale-minor". If you are still affected by this bug or are 
still interested in this issue, please give an update and remove the label. In 
7 days the issue will be closed automatically.

> 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)

[jira] [Commented] (FLINK-2926) Add a Strongly Connected Components Library Method

[Martin Liesenberg (JIRA)]

[ 
https://issues.apache.org/jira/browse/FLINK-2926?page=com.atlassian.jira.plugin.system.issuetabpanels:comment-tabpanel=15276811#comment-15276811
 ] 

Martin Liesenberg commented on FLINK-2926:
--

the issue is FLINK-3888

> 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)

[jira] [Commented] (FLINK-2926) Add a Strongly Connected Components Library Method

[Vasia Kalavri (JIRA)]

[ 
https://issues.apache.org/jira/browse/FLINK-2926?page=com.atlassian.jira.plugin.system.issuetabpanels:comment-tabpanel=15273933#comment-15273933
 ] 

Vasia Kalavri commented on FLINK-2926:
--

Hi [~mliesenberg],
delta iteration by default finishes when the workset is empty, but I don't see 
why it couldn't support a custom convergence criterion also. I thought this 
method was there already. In fact the [iterations 
guide|https://ci.apache.org/projects/flink/flink-docs-master/apis/batch/iterations.html]
 states that the delta iteration supports "Custom aggregator convergence" so 
that's weird. Can you please open an issue for that? Thanks!

> 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)

[jira] [Commented] (FLINK-2926) Add a Strongly Connected Components Library Method

[Martin Liesenberg (JIRA)]

[ 
https://issues.apache.org/jira/browse/FLINK-2926?page=com.atlassian.jira.plugin.system.issuetabpanels:comment-tabpanel=15272129#comment-15272129
 ] 

Martin Liesenberg commented on FLINK-2926:
--

Is that because there is the assumption that the deltaiteration is done when 
the workset is empty?

> 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)

[jira] [Commented] (FLINK-2926) Add a Strongly Connected Components Library Method

[Martin Liesenberg (JIRA)]

[ 
https://issues.apache.org/jira/browse/FLINK-2926?page=com.atlassian.jira.plugin.system.issuetabpanels:comment-tabpanel=15272119#comment-15272119
 ] 

Martin Liesenberg commented on FLINK-2926:
--

hey [~vkalavri],
still learning about the deltaIteration and aggregators, so no news yet, but a 
question popped up.

Unlike {{BulkIteration}}, {{DeltaIteration}} does not expose the method 
{{registerAggregationConvergenceCriterion}} of the {{AggregatorRegistry}} 
directly, but only the {{registerAggregator}} method. 

I was wondering why that is the case. Do you know anything about that?

> 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)

[jira] [Commented] (FLINK-2926) Add a Strongly Connected Components Library Method

[Martin Liesenberg (JIRA)]

[ 
https://issues.apache.org/jira/browse/FLINK-2926?page=com.atlassian.jira.plugin.system.issuetabpanels:comment-tabpanel=15267231#comment-15267231
 ] 

Martin Liesenberg commented on FLINK-2926:
--

yes, will do. thanks for the feedback. :)

> 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)

[jira] [Commented] (FLINK-2926) Add a Strongly Connected Components Library Method

[Vasia Kalavri (JIRA)]

[ 
https://issues.apache.org/jira/browse/FLINK-2926?page=com.atlassian.jira.plugin.system.issuetabpanels:comment-tabpanel=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)

[jira] [Commented] (FLINK-2926) Add a Strongly Connected Components Library Method

[Martin Liesenberg (JIRA)]

[ 
https://issues.apache.org/jira/browse/FLINK-2926?page=com.atlassian.jira.plugin.system.issuetabpanels:comment-tabpanel=15265308#comment-15265308
 ] 

Martin Liesenberg commented on FLINK-2926:
--

hi [~vkalavri], I updated the design doc, grateful for any feedback, if you 
want to have a look at it.
https://docs.google.com/document/d/10kwRoSjStCHpa8dr3vlwcOBTgyzT_X_b9E0OfGyY1Pg/edit

> 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)

[jira] [Commented] (FLINK-2926) Add a Strongly Connected Components Library Method

[Martin Liesenberg (JIRA)]

[ 
https://issues.apache.org/jira/browse/FLINK-2926?page=com.atlassian.jira.plugin.system.issuetabpanels:comment-tabpanel=15263992#comment-15263992
 ] 

Martin Liesenberg commented on FLINK-2926:
--

Cool, I'll update the design doc then and start coding.

Vasia Kalavri (JIRA)  schrieb am Fr., 29. Apr. 2016 um



> 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)

[jira] [Commented] (FLINK-2926) Add a Strongly Connected Components Library Method

[Vasia Kalavri (JIRA)]

[ 
https://issues.apache.org/jira/browse/FLINK-2926?page=com.atlassian.jira.plugin.system.issuetabpanels:comment-tabpanel=15263983#comment-15263983
 ] 

Vasia Kalavri commented on FLINK-2926:
--

Hey [~mliesenberg],
thanks for pinging! I'll assign the issue to you then ;)

> 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
>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)

[jira] [Commented] (FLINK-2926) Add a Strongly Connected Components Library Method

[Martin Liesenberg (JIRA)]

[ 
https://issues.apache.org/jira/browse/FLINK-2926?page=com.atlassian.jira.plugin.system.issuetabpanels:comment-tabpanel=15263788#comment-15263788
 ] 

Martin Liesenberg commented on FLINK-2926:
--

if there's still interest in having this algorithm as part of gelly's library, 
I'd start working on it again.

> 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
>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)

[jira] [Commented] (FLINK-2926) Add a Strongly Connected Components Library Method

[Martin Liesenberg (JIRA)]

[ 
https://issues.apache.org/jira/browse/FLINK-2926?page=com.atlassian.jira.plugin.system.issuetabpanels:comment-tabpanel=15029471#comment-15029471
 ] 

Martin Liesenberg commented on FLINK-2926:
--

Unfortunately I will not have time to work on this ticket until like early next 
year, so I'll assign it to unassigned and if it is still open one I have time 
again, I'll pick it up again. 

> 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)

[jira] [Commented] (FLINK-2926) Add a Strongly Connected Components Library Method

[Martin Liesenberg (JIRA)]

[ 
https://issues.apache.org/jira/browse/FLINK-2926?page=com.atlassian.jira.plugin.system.issuetabpanels:comment-tabpanel=14983860#comment-14983860
 ] 

Martin Liesenberg commented on FLINK-2926:
--

Thanks for the pointers. :)

> 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
>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)

[jira] [Commented] (FLINK-2926) Add a Strongly Connected Components Library Method

[Vasia Kalavri (JIRA)]

[ 
https://issues.apache.org/jira/browse/FLINK-2926?page=com.atlassian.jira.plugin.system.issuetabpanels:comment-tabpanel=14982523#comment-14982523
 ] 

Vasia Kalavri commented on FLINK-2926:
--

Hi [~mliesenberg],

what kind of iteration are you planning to use in your implementation?
If you'll use a bulk iteration, check 
{{IterativeDataSet.registerAggregationConvergenceCriterion()}}. I had the 
impression that delta iterations had a similar method, but I can't find it. 
What you can do in a delta iteration is use an aggregator and emit nothing to 
the workset when it has the value that signifies convergence.

> 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
>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)

[jira] [Commented] (FLINK-2926) Add a Strongly Connected Components Library Method

[Martin Liesenberg (JIRA)]

[ 
https://issues.apache.org/jira/browse/FLINK-2926?page=com.atlassian.jira.plugin.system.issuetabpanels:comment-tabpanel=14982493#comment-14982493
 ] 

Martin Liesenberg commented on FLINK-2926:
--

https://docs.google.com/document/d/10kwRoSjStCHpa8dr3vlwcOBTgyzT_X_b9E0OfGyY1Pg/edit?usp=sharing

A first draft based on what's in the ticket and the papers. Structured as 
proposed in the contribution guide. Let me know what you think. :)


One thing is not quite clear to me yet: how do I express a termination 
criterion based on a property of the graph and not in term of number of 
iterations. 

> 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
>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)

[jira] [Commented] (FLINK-2926) Add a Strongly Connected Components Library Method

[Martin Liesenberg (JIRA)]

[ 
https://issues.apache.org/jira/browse/FLINK-2926?page=com.atlassian.jira.plugin.system.issuetabpanels:comment-tabpanel=14980035#comment-14980035
 ] 

Martin Liesenberg commented on FLINK-2926:
--

I could take a stab at it, if no one else is working on it.

> 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)

[jira] [Commented] (FLINK-2926) Add a Strongly Connected Components Library Method

[Andra Lungu (JIRA)]

[ 
https://issues.apache.org/jira/browse/FLINK-2926?page=com.atlassian.jira.plugin.system.issuetabpanels:comment-tabpanel=14980039#comment-14980039
 ] 

Andra Lungu commented on FLINK-2926:


Awesome! It's all yours!
[~fhueske] or [~uce], can you please assign Martin to the issue?

Let us know if you encounter difficulties! :) 



> 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)

[jira] [Commented] (FLINK-2926) Add a Strongly Connected Components Library Method

[Martin Liesenberg (JIRA)]

[ 
https://issues.apache.org/jira/browse/FLINK-2926?page=com.atlassian.jira.plugin.system.issuetabpanels:comment-tabpanel=14980071#comment-14980071
 ] 

Martin Liesenberg commented on FLINK-2926:
--

Sure. What's the preferred format for that?

Markdown in a gist or a shared google doc or something else entirely?

> 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
>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)

[jira] [Commented] (FLINK-2926) Add a Strongly Connected Components Library Method

[Fabian Hueske (JIRA)]

[ 
https://issues.apache.org/jira/browse/FLINK-2926?page=com.atlassian.jira.plugin.system.issuetabpanels:comment-tabpanel=14980068#comment-14980068
 ] 

Fabian Hueske commented on FLINK-2926:
--

Hi [~mliesenberg], I attached the `requires-design-doc` label to this issue [1].
Can you please draft a document that sketches your implementation? The rational 
is to agree on an implementation design before the actual code is written to 
avoid long discussions and rewrites of a pull request.

Thank you very much, Fabian.

[1] http://flink.apache.org/contribute-code.html#before-you-start-coding

> 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
>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)

[jira] [Commented] (FLINK-2926) Add a Strongly Connected Components Library Method

[Andra Lungu (JIRA)]

[ 
https://issues.apache.org/jira/browse/FLINK-2926?page=com.atlassian.jira.plugin.system.issuetabpanels:comment-tabpanel=14980076#comment-14980076
 ] 

Andra Lungu commented on FLINK-2926:


Whatever you prefer. Google doc is the easiest, I guess. 

> 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
>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)