[jira] [Commented] (FLINK-1526) Add Minimum Spanning Tree library method and example
[ https://issues.apache.org/jira/browse/FLINK-1526?page=com.atlassian.jira.plugin.system.issuetabpanels:comment-tabpanel=17323742#comment-17323742 ] Flink Jira Bot commented on FLINK-1526: --- 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 Minimum Spanning Tree library method and example > > > Key: FLINK-1526 > URL: https://issues.apache.org/jira/browse/FLINK-1526 > Project: Flink > Issue Type: Task > Components: Library / Graph Processing (Gelly) >Reporter: Vasia Kalavri >Assignee: Xingcan Cui >Priority: Major > Labels: algorithm, stale-assigned > > This issue proposes the addition of a library method and an example for > distributed minimum spanning tree in Gelly. > The DMST algorithm is very interesting because it is quite different from > PageRank-like iterative graph algorithms. It consists of distinct phases > inside the same iteration and requires a mechanism to detect convergence of > one phase to proceed to the next one. Current implementations in > vertex-centric models are quite long (>1000 lines) and hard to understand. > You can find a description of the algorithm [here | > http://ilpubs.stanford.edu:8090/1077/3/p535-salihoglu.pdf] and [here | > http://www.vldb.org/pvldb/vol7/p1047-han.pdf]. -- This message was sent by Atlassian Jira (v8.3.4#803005)
[jira] [Commented] (FLINK-1526) Add Minimum Spanning Tree library method and example
[ https://issues.apache.org/jira/browse/FLINK-1526?page=com.atlassian.jira.plugin.system.issuetabpanels:comment-tabpanel=15982354#comment-15982354 ] ASF GitHub Bot commented on FLINK-1526: --- Github user xccui closed the pull request at: https://github.com/apache/flink/pull/3284 > Add Minimum Spanning Tree library method and example > > > Key: FLINK-1526 > URL: https://issues.apache.org/jira/browse/FLINK-1526 > Project: Flink > Issue Type: Task > Components: Gelly >Reporter: Vasia Kalavri >Assignee: Xingcan Cui > Labels: algorithm > > This issue proposes the addition of a library method and an example for > distributed minimum spanning tree in Gelly. > The DMST algorithm is very interesting because it is quite different from > PageRank-like iterative graph algorithms. It consists of distinct phases > inside the same iteration and requires a mechanism to detect convergence of > one phase to proceed to the next one. Current implementations in > vertex-centric models are quite long (>1000 lines) and hard to understand. > You can find a description of the algorithm [here | > http://ilpubs.stanford.edu:8090/1077/3/p535-salihoglu.pdf] and [here | > http://www.vldb.org/pvldb/vol7/p1047-han.pdf]. -- This message was sent by Atlassian JIRA (v6.3.15#6346)
[jira] [Commented] (FLINK-1526) Add Minimum Spanning Tree library method and example
[ https://issues.apache.org/jira/browse/FLINK-1526?page=com.atlassian.jira.plugin.system.issuetabpanels:comment-tabpanel=15879128#comment-15879128 ] ASF GitHub Bot commented on FLINK-1526: --- Github user greghogan commented on the issue: https://github.com/apache/flink/pull/3284 Hi @xccui, I've been looking at this and FLINK-1707 (Affinity Propagation) the last few days (had to learn the algorithm first). My first analysis for an algorithm is to look at the performance and FLINK-4949 will make this much simpler to execute and measure. The ticket talks about for-loop iterations but it seems we really want nested iterations. > Add Minimum Spanning Tree library method and example > > > Key: FLINK-1526 > URL: https://issues.apache.org/jira/browse/FLINK-1526 > Project: Flink > Issue Type: Task > Components: Gelly >Reporter: Vasia Kalavri >Assignee: Xingcan Cui > > This issue proposes the addition of a library method and an example for > distributed minimum spanning tree in Gelly. > The DMST algorithm is very interesting because it is quite different from > PageRank-like iterative graph algorithms. It consists of distinct phases > inside the same iteration and requires a mechanism to detect convergence of > one phase to proceed to the next one. Current implementations in > vertex-centric models are quite long (>1000 lines) and hard to understand. > You can find a description of the algorithm [here | > http://ilpubs.stanford.edu:8090/1077/3/p535-salihoglu.pdf] and [here | > http://www.vldb.org/pvldb/vol7/p1047-han.pdf]. -- This message was sent by Atlassian JIRA (v6.3.15#6346)
[jira] [Commented] (FLINK-1526) Add Minimum Spanning Tree library method and example
[ https://issues.apache.org/jira/browse/FLINK-1526?page=com.atlassian.jira.plugin.system.issuetabpanels:comment-tabpanel=15877287#comment-15877287 ] ASF GitHub Bot commented on FLINK-1526: --- Github user xccui commented on the issue: https://github.com/apache/flink/pull/3284 With the present situation (for gelly), shall I close this PR? > Add Minimum Spanning Tree library method and example > > > Key: FLINK-1526 > URL: https://issues.apache.org/jira/browse/FLINK-1526 > Project: Flink > Issue Type: Task > Components: Gelly >Reporter: Vasia Kalavri >Assignee: Xingcan Cui > > This issue proposes the addition of a library method and an example for > distributed minimum spanning tree in Gelly. > The DMST algorithm is very interesting because it is quite different from > PageRank-like iterative graph algorithms. It consists of distinct phases > inside the same iteration and requires a mechanism to detect convergence of > one phase to proceed to the next one. Current implementations in > vertex-centric models are quite long (>1000 lines) and hard to understand. > You can find a description of the algorithm [here | > http://ilpubs.stanford.edu:8090/1077/3/p535-salihoglu.pdf] and [here | > http://www.vldb.org/pvldb/vol7/p1047-han.pdf]. -- This message was sent by Atlassian JIRA (v6.3.15#6346)
[jira] [Commented] (FLINK-1526) Add Minimum Spanning Tree library method and example
[ https://issues.apache.org/jira/browse/FLINK-1526?page=com.atlassian.jira.plugin.system.issuetabpanels:comment-tabpanel=15860513#comment-15860513 ] ASF GitHub Bot commented on FLINK-1526: --- Github user xccui commented on a diff in the pull request: https://github.com/apache/flink/pull/3284#discussion_r100455274 --- Diff: docs/dev/libs/gelly/library_methods.md --- @@ -242,6 +242,28 @@ The algorithm takes a directed, vertex (and possibly edge) attributed graph as i vertex represents a group of vertices and each edge represents a group of edges from the input graph. Furthermore, each vertex and edge in the output graph stores the common group value and the number of represented elements. +## Minimum Spanning Tree + + Overview +This is an implementation of the distributed minimum spanning tree (MST) algorithm. A minimum spanning tree for a connected and +undirected graph is a subset of edges with minimum possible total edge weight that connects all the vertices without cycles. +One of the possible use cases for MST could be laying out cables that connect all buildings with the minimum total cable length. + + Details +Unlike a sequential version of the algorithm, a distributed MST algorithm is based on the message-passing model. +We use [vertex-centric iterations](#vertex-centric-iterations) to implement the Borůvka algorithm described in +[this paper](http://ieeexplore.ieee.org/abstract/document/508073/). As there are different steps inside the iteration, --- End diff -- Yes greg, you are right. A pdf is surely better than a web site. Think it over, I want to change the paper to https://cs.uwaterloo.ca/~kdaudjee/comparison.pdf since it fits more. > Add Minimum Spanning Tree library method and example > > > Key: FLINK-1526 > URL: https://issues.apache.org/jira/browse/FLINK-1526 > Project: Flink > Issue Type: Task > Components: Gelly >Reporter: Vasia Kalavri >Assignee: Xingcan Cui > > This issue proposes the addition of a library method and an example for > distributed minimum spanning tree in Gelly. > The DMST algorithm is very interesting because it is quite different from > PageRank-like iterative graph algorithms. It consists of distinct phases > inside the same iteration and requires a mechanism to detect convergence of > one phase to proceed to the next one. Current implementations in > vertex-centric models are quite long (>1000 lines) and hard to understand. > You can find a description of the algorithm [here | > http://ilpubs.stanford.edu:8090/1077/3/p535-salihoglu.pdf] and [here | > http://www.vldb.org/pvldb/vol7/p1047-han.pdf]. -- This message was sent by Atlassian JIRA (v6.3.15#6346)
[jira] [Commented] (FLINK-1526) Add Minimum Spanning Tree library method and example
[ https://issues.apache.org/jira/browse/FLINK-1526?page=com.atlassian.jira.plugin.system.issuetabpanels:comment-tabpanel=15860271#comment-15860271 ] ASF GitHub Bot commented on FLINK-1526: --- Github user greghogan commented on a diff in the pull request: https://github.com/apache/flink/pull/3284#discussion_r100421801 --- Diff: docs/dev/libs/gelly/library_methods.md --- @@ -242,6 +242,28 @@ The algorithm takes a directed, vertex (and possibly edge) attributed graph as i vertex represents a group of vertices and each edge represents a group of edges from the input graph. Furthermore, each vertex and edge in the output graph stores the common group value and the number of represented elements. +## Minimum Spanning Tree + + Overview +This is an implementation of the distributed minimum spanning tree (MST) algorithm. A minimum spanning tree for a connected and +undirected graph is a subset of edges with minimum possible total edge weight that connects all the vertices without cycles. +One of the possible use cases for MST could be laying out cables that connect all buildings with the minimum total cable length. + + Details +Unlike a sequential version of the algorithm, a distributed MST algorithm is based on the message-passing model. +We use [vertex-centric iterations](#vertex-centric-iterations) to implement the Borůvka algorithm described in +[this paper](http://ieeexplore.ieee.org/abstract/document/508073/). As there are different steps inside the iteration, --- End diff -- Should we cite https://www.cs.ubc.ca/~condon/papers/chungcondon96.pdf? > Add Minimum Spanning Tree library method and example > > > Key: FLINK-1526 > URL: https://issues.apache.org/jira/browse/FLINK-1526 > Project: Flink > Issue Type: Task > Components: Gelly >Reporter: Vasia Kalavri >Assignee: Xingcan Cui > > This issue proposes the addition of a library method and an example for > distributed minimum spanning tree in Gelly. > The DMST algorithm is very interesting because it is quite different from > PageRank-like iterative graph algorithms. It consists of distinct phases > inside the same iteration and requires a mechanism to detect convergence of > one phase to proceed to the next one. Current implementations in > vertex-centric models are quite long (>1000 lines) and hard to understand. > You can find a description of the algorithm [here | > http://ilpubs.stanford.edu:8090/1077/3/p535-salihoglu.pdf] and [here | > http://www.vldb.org/pvldb/vol7/p1047-han.pdf]. -- This message was sent by Atlassian JIRA (v6.3.15#6346)
[jira] [Commented] (FLINK-1526) Add Minimum Spanning Tree library method and example
[ https://issues.apache.org/jira/browse/FLINK-1526?page=com.atlassian.jira.plugin.system.issuetabpanels:comment-tabpanel=15860265#comment-15860265 ] ASF GitHub Bot commented on FLINK-1526: --- Github user greghogan commented on a diff in the pull request: https://github.com/apache/flink/pull/3284#discussion_r100421089 --- Diff: docs/dev/libs/gelly/library_methods.md --- @@ -242,6 +242,28 @@ The algorithm takes a directed, vertex (and possibly edge) attributed graph as i vertex represents a group of vertices and each edge represents a group of edges from the input graph. Furthermore, each vertex and edge in the output graph stores the common group value and the number of represented elements. +## Minimum Spanning Tree + + Overview +This is an implementation of the distributed minimum spanning tree (MST) algorithm. A minimum spanning tree for a connected and +undirected graph is a subset of edges with minimum possible total edge weight that connects all the vertices without cycles. +One of the possible use cases for MST could be laying out cables that connect all buildings with the minimum total cable length. + + Details +Unlike a sequential version of the algorithm, a distributed MST algorithm is based on the message-passing model. +We use [vertex-centric iterations](#vertex-centric-iterations) to implement the Borůvka algorithm described in +[this paper](http://ieeexplore.ieee.org/abstract/document/508073/). As there are different steps inside the iteration, --- End diff -- Should we cite https://www.cs.ubc.ca/~condon/papers/chungcondon96.pdf? > Add Minimum Spanning Tree library method and example > > > Key: FLINK-1526 > URL: https://issues.apache.org/jira/browse/FLINK-1526 > Project: Flink > Issue Type: Task > Components: Gelly >Reporter: Vasia Kalavri >Assignee: Xingcan Cui > > This issue proposes the addition of a library method and an example for > distributed minimum spanning tree in Gelly. > The DMST algorithm is very interesting because it is quite different from > PageRank-like iterative graph algorithms. It consists of distinct phases > inside the same iteration and requires a mechanism to detect convergence of > one phase to proceed to the next one. Current implementations in > vertex-centric models are quite long (>1000 lines) and hard to understand. > You can find a description of the algorithm [here | > http://ilpubs.stanford.edu:8090/1077/3/p535-salihoglu.pdf] and [here | > http://www.vldb.org/pvldb/vol7/p1047-han.pdf]. -- This message was sent by Atlassian JIRA (v6.3.15#6346)
[jira] [Commented] (FLINK-1526) Add Minimum Spanning Tree library method and example
[
https://issues.apache.org/jira/browse/FLINK-1526?page=com.atlassian.jira.plugin.system.issuetabpanels:comment-tabpanel=15857415#comment-15857415
]
ASF GitHub Bot commented on FLINK-1526:
---
GitHub user xccui opened a pull request:
https://github.com/apache/flink/pull/3284
[FLINK-1526] [Gelly] Add Minimum Spanning Tree library method
Thanks for contributing to Apache Flink. Before you open your pull request,
please take the following check list into consideration.
If your changes take all of the items into account, feel free to open your
pull request. For more information and/or questions please refer to the [How To
Contribute guide](http://flink.apache.org/how-to-contribute.html).
In addition to going through the list, please provide a meaningful
description of your changes.
- [X] General
- The pull request references the related JIRA issue ("[FLINK-XXX] Jira
title text")
- The pull request addresses only one issue
- Each commit in the PR has a meaningful commit message (including the
JIRA id)
- [X] Documentation
- Documentation has been added for new functionality
- Old documentation affected by the pull request has been updated
- JavaDoc for public methods has been added
- [ ] Tests & Build
- Functionality added by the pull request is covered by tests
- `mvn clean verify` has been executed successfully locally or a Travis
build has passed
You can merge this pull request into a Git repository by running:
$ git pull https://github.com/xccui/flink master
Alternatively you can review and apply these changes as the patch at:
https://github.com/apache/flink/pull/3284.patch
To close this pull request, make a commit to your master/trunk branch
with (at least) the following in the commit message:
This closes #3284
commit 495aa623dccecfba66124b44c7dd955b61853c94
Author: xccui
Date: 2017-02-08T04:57:21Z
[FLINK-1526] [Gelly] Add Minimum Spanning Tree library method
> Add Minimum Spanning Tree library method and example
>
>
> Key: FLINK-1526
> URL: https://issues.apache.org/jira/browse/FLINK-1526
> Project: Flink
> Issue Type: Task
> Components: Gelly
>Reporter: Vasia Kalavri
>Assignee: Xingcan Cui
>
> This issue proposes the addition of a library method and an example for
> distributed minimum spanning tree in Gelly.
> The DMST algorithm is very interesting because it is quite different from
> PageRank-like iterative graph algorithms. It consists of distinct phases
> inside the same iteration and requires a mechanism to detect convergence of
> one phase to proceed to the next one. Current implementations in
> vertex-centric models are quite long (>1000 lines) and hard to understand.
> You can find a description of the algorithm [here |
> http://ilpubs.stanford.edu:8090/1077/3/p535-salihoglu.pdf] and [here |
> http://www.vldb.org/pvldb/vol7/p1047-han.pdf].
--
This message was sent by Atlassian JIRA
(v6.3.15#6346)
[jira] [Commented] (FLINK-1526) Add Minimum Spanning Tree library method and example
[ https://issues.apache.org/jira/browse/FLINK-1526?page=com.atlassian.jira.plugin.system.issuetabpanels:comment-tabpanel=15474504#comment-15474504 ] Olga Golovneva commented on FLINK-1526: --- Hi Greg, I didn't found much details about this issue either, here is what I have: http://mail-archives.apache.org/mod_mbox/flink-dev/201504.mbox/%3ccajz2dcugxrxsdxh_rq4dr52ego+out5oz+5n5xm2an5psrx...@mail.gmail.com%3e I suppose, the problem was in data caching within a loop Thnx > Add Minimum Spanning Tree library method and example > > > Key: FLINK-1526 > URL: https://issues.apache.org/jira/browse/FLINK-1526 > Project: Flink > Issue Type: Task > Components: Gelly >Reporter: Vasia Kalavri > > This issue proposes the addition of a library method and an example for > distributed minimum spanning tree in Gelly. > The DMST algorithm is very interesting because it is quite different from > PageRank-like iterative graph algorithms. It consists of distinct phases > inside the same iteration and requires a mechanism to detect convergence of > one phase to proceed to the next one. Current implementations in > vertex-centric models are quite long (>1000 lines) and hard to understand. > You can find a description of the algorithm [here | > http://ilpubs.stanford.edu:8090/1077/3/p535-salihoglu.pdf] and [here | > http://www.vldb.org/pvldb/vol7/p1047-han.pdf]. -- This message was sent by Atlassian JIRA (v6.3.4#6332)
[jira] [Commented] (FLINK-1526) Add Minimum Spanning Tree library method and example
[ https://issues.apache.org/jira/browse/FLINK-1526?page=com.atlassian.jira.plugin.system.issuetabpanels:comment-tabpanel=15473850#comment-15473850 ] Greg Hogan commented on FLINK-1526: --- Hi Olga, do you have a reference for the for-loop iteration issue as it pertains to this algorithm? There wasn't much discussion on this ticket or associated pull request. Is the intent to use iterations or a loop with data caching? > Add Minimum Spanning Tree library method and example > > > Key: FLINK-1526 > URL: https://issues.apache.org/jira/browse/FLINK-1526 > Project: Flink > Issue Type: Task > Components: Gelly >Reporter: Vasia Kalavri > > This issue proposes the addition of a library method and an example for > distributed minimum spanning tree in Gelly. > The DMST algorithm is very interesting because it is quite different from > PageRank-like iterative graph algorithms. It consists of distinct phases > inside the same iteration and requires a mechanism to detect convergence of > one phase to proceed to the next one. Current implementations in > vertex-centric models are quite long (>1000 lines) and hard to understand. > You can find a description of the algorithm [here | > http://ilpubs.stanford.edu:8090/1077/3/p535-salihoglu.pdf] and [here | > http://www.vldb.org/pvldb/vol7/p1047-han.pdf]. -- This message was sent by Atlassian JIRA (v6.3.4#6332)
[jira] [Commented] (FLINK-1526) Add Minimum Spanning Tree library method and example
[ https://issues.apache.org/jira/browse/FLINK-1526?page=com.atlassian.jira.plugin.system.issuetabpanels:comment-tabpanel=15472586#comment-15472586 ] Olga Golovneva commented on FLINK-1526: --- Hi, I was wondering what is the current state for this JIRA? I am really interested in implementing Boruvka's algorithm, I just wanted to check out if the for-loop iteration issue has been fixed by now. > Add Minimum Spanning Tree library method and example > > > Key: FLINK-1526 > URL: https://issues.apache.org/jira/browse/FLINK-1526 > Project: Flink > Issue Type: Task > Components: Gelly >Reporter: Vasia Kalavri > > This issue proposes the addition of a library method and an example for > distributed minimum spanning tree in Gelly. > The DMST algorithm is very interesting because it is quite different from > PageRank-like iterative graph algorithms. It consists of distinct phases > inside the same iteration and requires a mechanism to detect convergence of > one phase to proceed to the next one. Current implementations in > vertex-centric models are quite long (>1000 lines) and hard to understand. > You can find a description of the algorithm [here | > http://ilpubs.stanford.edu:8090/1077/3/p535-salihoglu.pdf] and [here | > http://www.vldb.org/pvldb/vol7/p1047-han.pdf]. -- This message was sent by Atlassian JIRA (v6.3.4#6332)
[jira] [Commented] (FLINK-1526) Add Minimum Spanning Tree library method and example
[ https://issues.apache.org/jira/browse/FLINK-1526?page=com.atlassian.jira.plugin.system.issuetabpanels:comment-tabpanelfocusedCommentId=14570554#comment-14570554 ] ASF GitHub Bot commented on FLINK-1526: --- Github user vasia commented on the pull request: https://github.com/apache/flink/pull/434#issuecomment-108278253 Hey @andralungu! I think we should close this one. We can't really continue from this state anyway. I guess we'll have to revisit this problem once we have for-loop iteration support. Add Minimum Spanning Tree library method and example Key: FLINK-1526 URL: https://issues.apache.org/jira/browse/FLINK-1526 Project: Flink Issue Type: Task Components: Gelly Reporter: Vasia Kalavri Assignee: Andra Lungu This issue proposes the addition of a library method and an example for distributed minimum spanning tree in Gelly. The DMST algorithm is very interesting because it is quite different from PageRank-like iterative graph algorithms. It consists of distinct phases inside the same iteration and requires a mechanism to detect convergence of one phase to proceed to the next one. Current implementations in vertex-centric models are quite long (1000 lines) and hard to understand. You can find a description of the algorithm [here | http://ilpubs.stanford.edu:8090/1077/3/p535-salihoglu.pdf] and [here | http://www.vldb.org/pvldb/vol7/p1047-han.pdf]. -- This message was sent by Atlassian JIRA (v6.3.4#6332)
[jira] [Commented] (FLINK-1526) Add Minimum Spanning Tree library method and example
[
https://issues.apache.org/jira/browse/FLINK-1526?page=com.atlassian.jira.plugin.system.issuetabpanels:comment-tabpanelfocusedCommentId=14337709#comment-14337709
]
ASF GitHub Bot commented on FLINK-1526:
---
Github user hsaputra commented on a diff in the pull request:
https://github.com/apache/flink/pull/434#discussion_r25399853
--- Diff:
flink-staging/flink-gelly/src/main/java/org/apache/flink/graph/example/MinSpanningTreeExample.java
---
@@ -0,0 +1,132 @@
+/*
+ * Licensed to the Apache Software Foundation (ASF) under one
+ * or more contributor license agreements. See the NOTICE file
+ * distributed with this work for additional information
+ * regarding copyright ownership. The ASF licenses this file
+ * to you under the Apache License, Version 2.0 (the
+ * License); you may not use this file except in compliance
+ * with the License. You may obtain a copy of the License at
+ *
+ * http://www.apache.org/licenses/LICENSE-2.0
+ *
+ * Unless required by applicable law or agreed to in writing, software
+ * distributed under the License is distributed on an AS IS BASIS,
+ * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+ * See the License for the specific language governing permissions and
+ * limitations under the License.
+ */
+
+package org.apache.flink.graph.example;
+
+import org.apache.flink.graph.example.utils.MinSpanningTreeData;
+import org.apache.flink.graph.library.MinSpanningTree;
+import org.apache.flink.graph.Edge;
+import org.apache.flink.graph.Graph;
+import org.apache.flink.graph.Vertex;
+import org.apache.flink.api.common.ProgramDescription;
+import org.apache.flink.api.common.functions.MapFunction;
+import org.apache.flink.api.java.DataSet;
+import org.apache.flink.api.java.ExecutionEnvironment;
+import org.apache.flink.api.java.tuple.Tuple1;
+import org.apache.flink.api.java.tuple.Tuple3;
+
+public class MinSpanningTreeExample implements ProgramDescription {
--- End diff --
Could you add Javadoc description of what this class does and the sample
output?
We are trying to add contributions to add more comments and descriptions to
keep up with new code coming in.
Add Minimum Spanning Tree library method and example
Key: FLINK-1526
URL: https://issues.apache.org/jira/browse/FLINK-1526
Project: Flink
Issue Type: Task
Components: Gelly
Reporter: Vasia Kalavri
Assignee: Andra Lungu
This issue proposes the addition of a library method and an example for
distributed minimum spanning tree in Gelly.
The DMST algorithm is very interesting because it is quite different from
PageRank-like iterative graph algorithms. It consists of distinct phases
inside the same iteration and requires a mechanism to detect convergence of
one phase to proceed to the next one. Current implementations in
vertex-centric models are quite long (1000 lines) and hard to understand.
You can find a description of the algorithm [here |
http://ilpubs.stanford.edu:8090/1077/3/p535-salihoglu.pdf] and [here |
http://www.vldb.org/pvldb/vol7/p1047-han.pdf].
--
This message was sent by Atlassian JIRA
(v6.3.4#6332)
[jira] [Commented] (FLINK-1526) Add Minimum Spanning Tree library method and example
[
https://issues.apache.org/jira/browse/FLINK-1526?page=com.atlassian.jira.plugin.system.issuetabpanels:comment-tabpanelfocusedCommentId=14337710#comment-14337710
]
ASF GitHub Bot commented on FLINK-1526:
---
Github user hsaputra commented on a diff in the pull request:
https://github.com/apache/flink/pull/434#discussion_r25399885
--- Diff:
flink-staging/flink-gelly/src/main/java/org/apache/flink/graph/example/utils/MinSpanningTreeData.java
---
@@ -0,0 +1,91 @@
+/*
+ * Licensed to the Apache Software Foundation (ASF) under one
+ * or more contributor license agreements. See the NOTICE file
+ * distributed with this work for additional information
+ * regarding copyright ownership. The ASF licenses this file
+ * to you under the Apache License, Version 2.0 (the
+ * License); you may not use this file except in compliance
+ * with the License. You may obtain a copy of the License at
+ *
+ * http://www.apache.org/licenses/LICENSE-2.0
+ *
+ * Unless required by applicable law or agreed to in writing, software
+ * distributed under the License is distributed on an AS IS BASIS,
+ * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+ * See the License for the specific language governing permissions and
+ * limitations under the License.
+ */
+
+package org.apache.flink.graph.example.utils;
+
+import org.apache.flink.graph.Edge;
+import org.apache.flink.graph.Vertex;
+import org.apache.flink.api.java.DataSet;
+import org.apache.flink.api.java.ExecutionEnvironment;
+
+import java.util.ArrayList;
+import java.util.List;
+
+public class MinSpanningTreeData {
--- End diff --
Could you add Javadoc description of what this class does and relationships
to other classes?
Add Minimum Spanning Tree library method and example
Key: FLINK-1526
URL: https://issues.apache.org/jira/browse/FLINK-1526
Project: Flink
Issue Type: Task
Components: Gelly
Reporter: Vasia Kalavri
Assignee: Andra Lungu
This issue proposes the addition of a library method and an example for
distributed minimum spanning tree in Gelly.
The DMST algorithm is very interesting because it is quite different from
PageRank-like iterative graph algorithms. It consists of distinct phases
inside the same iteration and requires a mechanism to detect convergence of
one phase to proceed to the next one. Current implementations in
vertex-centric models are quite long (1000 lines) and hard to understand.
You can find a description of the algorithm [here |
http://ilpubs.stanford.edu:8090/1077/3/p535-salihoglu.pdf] and [here |
http://www.vldb.org/pvldb/vol7/p1047-han.pdf].
--
This message was sent by Atlassian JIRA
(v6.3.4#6332)
[jira] [Commented] (FLINK-1526) Add Minimum Spanning Tree library method and example
[
https://issues.apache.org/jira/browse/FLINK-1526?page=com.atlassian.jira.plugin.system.issuetabpanels:comment-tabpanelfocusedCommentId=14337711#comment-14337711
]
ASF GitHub Bot commented on FLINK-1526:
---
Github user hsaputra commented on a diff in the pull request:
https://github.com/apache/flink/pull/434#discussion_r25399902
--- Diff:
flink-staging/flink-gelly/src/main/java/org/apache/flink/graph/library/MinSpanningTree.java
---
@@ -0,0 +1,388 @@
+/*
+ * Licensed to the Apache Software Foundation (ASF) under one
+ * or more contributor license agreements. See the NOTICE file
+ * distributed with this work for additional information
+ * regarding copyright ownership. The ASF licenses this file
+ * to you under the Apache License, Version 2.0 (the
+ * License); you may not use this file except in compliance
+ * with the License. You may obtain a copy of the License at
+ *
+ * http://www.apache.org/licenses/LICENSE-2.0
+ *
+ * Unless required by applicable law or agreed to in writing, software
+ * distributed under the License is distributed on an AS IS BASIS,
+ * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+ * See the License for the specific language governing permissions and
+ * limitations under the License.
+ */
+
+package org.apache.flink.graph.library;
+
+import org.apache.flink.api.common.functions.CoGroupFunction;
+import org.apache.flink.api.common.functions.FlatMapFunction;
+import org.apache.flink.api.common.functions.FlatJoinFunction;
+import org.apache.flink.api.common.functions.MapFunction;
+import org.apache.flink.api.common.functions.RichFilterFunction;
+import org.apache.flink.graph.Edge;
+import org.apache.flink.graph.Graph;
+import org.apache.flink.graph.GraphAlgorithm;
+import org.apache.flink.api.java.DataSet;
+import org.apache.flink.api.java.operators.IterativeDataSet;
+import org.apache.flink.api.java.tuple.Tuple2;
+import org.apache.flink.api.java.tuple.Tuple3;
+import org.apache.flink.api.java.tuple.Tuple6;
+import org.apache.flink.configuration.Configuration;
+import org.apache.flink.graph.example.utils.ConvergenceDetectionAggregator;
+import org.apache.flink.types.BooleanValue;
+import org.apache.flink.util.Collector;
+
+import java.util.Iterator;
+
+@SuppressWarnings(serial)
+public class MinSpanningTree implements GraphAlgorithmLong, String,
Double {
--- End diff --
Could you add Javadoc description of what this class does and relationships
to other classes?
Add Minimum Spanning Tree library method and example
Key: FLINK-1526
URL: https://issues.apache.org/jira/browse/FLINK-1526
Project: Flink
Issue Type: Task
Components: Gelly
Reporter: Vasia Kalavri
Assignee: Andra Lungu
This issue proposes the addition of a library method and an example for
distributed minimum spanning tree in Gelly.
The DMST algorithm is very interesting because it is quite different from
PageRank-like iterative graph algorithms. It consists of distinct phases
inside the same iteration and requires a mechanism to detect convergence of
one phase to proceed to the next one. Current implementations in
vertex-centric models are quite long (1000 lines) and hard to understand.
You can find a description of the algorithm [here |
http://ilpubs.stanford.edu:8090/1077/3/p535-salihoglu.pdf] and [here |
http://www.vldb.org/pvldb/vol7/p1047-han.pdf].
--
This message was sent by Atlassian JIRA
(v6.3.4#6332)
[jira] [Commented] (FLINK-1526) Add Minimum Spanning Tree library method and example
[ https://issues.apache.org/jira/browse/FLINK-1526?page=com.atlassian.jira.plugin.system.issuetabpanels:comment-tabpanelfocusedCommentId=14333445#comment-14333445 ] ASF GitHub Bot commented on FLINK-1526: --- GitHub user andralungu opened a pull request: https://github.com/apache/flink/pull/434 [FLINK-1526] Added MinSpanningTree example, library and test You can merge this pull request into a Git repository by running: $ git pull https://github.com/andralungu/flink dmst Alternatively you can review and apply these changes as the patch at: https://github.com/apache/flink/pull/434.patch To close this pull request, make a commit to your master/trunk branch with (at least) the following in the commit message: This closes #434 commit f60b022de056ac259459b68eee6ff0ae9993f0f8 Author: andralungu lungu.an...@gmail.com Date: 2015-02-23T15:56:15Z [FLINK-1526] Added MinSpanningTree example, library and test Add Minimum Spanning Tree library method and example Key: FLINK-1526 URL: https://issues.apache.org/jira/browse/FLINK-1526 Project: Flink Issue Type: Task Components: Gelly Reporter: Vasia Kalavri Assignee: Andra Lungu This issue proposes the addition of a library method and an example for distributed minimum spanning tree in Gelly. The DMST algorithm is very interesting because it is quite different from PageRank-like iterative graph algorithms. It consists of distinct phases inside the same iteration and requires a mechanism to detect convergence of one phase to proceed to the next one. Current implementations in vertex-centric models are quite long (1000 lines) and hard to understand. You can find a description of the algorithm [here | http://ilpubs.stanford.edu:8090/1077/3/p535-salihoglu.pdf] and [here | http://www.vldb.org/pvldb/vol7/p1047-han.pdf]. -- This message was sent by Atlassian JIRA (v6.3.4#6332)
