You are viewing a plain text version of this content. The canonical link for it is here.
Posted to issues@flink.apache.org by xccui <gi...@git.apache.org> on 2017/02/08 05:07:52 UTC
[GitHub] flink pull request #3284: [FLINK-1526] [Gelly] Add Minimum Spanning Tree lib...
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 <xi...@gmail.com>
Date: 2017-02-08T04:57:21Z
[FLINK-1526] [Gelly] Add Minimum Spanning Tree library method
----
---
If your project is set up for it, you can reply to this email and have your
reply appear on GitHub as well. If your project does not have this feature
enabled and wishes so, or if the feature is enabled but not working, please
contact infrastructure at infrastructure@apache.org or file a JIRA ticket
with INFRA.
---
[GitHub] flink issue #3284: [FLINK-1526] [Gelly] Add Minimum Spanning Tree library me...
Posted by greghogan <gi...@git.apache.org>.
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.
---
If your project is set up for it, you can reply to this email and have your
reply appear on GitHub as well. If your project does not have this feature
enabled and wishes so, or if the feature is enabled but not working, please
contact infrastructure at infrastructure@apache.org or file a JIRA ticket
with INFRA.
---
[GitHub] flink issue #3284: [FLINK-1526] [Gelly] Add Minimum Spanning Tree library me...
Posted by xccui <gi...@git.apache.org>.
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?
---
If your project is set up for it, you can reply to this email and have your
reply appear on GitHub as well. If your project does not have this feature
enabled and wishes so, or if the feature is enabled but not working, please
contact infrastructure at infrastructure@apache.org or file a JIRA ticket
with INFRA.
---
[GitHub] flink pull request #3284: [FLINK-1526] [Gelly] Add Minimum Spanning Tree lib...
Posted by greghogan <gi...@git.apache.org>.
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\u016fvka 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?
---
If your project is set up for it, you can reply to this email and have your
reply appear on GitHub as well. If your project does not have this feature
enabled and wishes so, or if the feature is enabled but not working, please
contact infrastructure at infrastructure@apache.org or file a JIRA ticket
with INFRA.
---
[GitHub] flink pull request #3284: [FLINK-1526] [Gelly] Add Minimum Spanning Tree lib...
Posted by xccui <gi...@git.apache.org>.
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\u016fvka 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.
---
If your project is set up for it, you can reply to this email and have your
reply appear on GitHub as well. If your project does not have this feature
enabled and wishes so, or if the feature is enabled but not working, please
contact infrastructure at infrastructure@apache.org or file a JIRA ticket
with INFRA.
---
[GitHub] flink pull request #3284: [FLINK-1526] [Gelly] Add Minimum Spanning Tree lib...
Posted by xccui <gi...@git.apache.org>.
Github user xccui closed the pull request at:
https://github.com/apache/flink/pull/3284
---
If your project is set up for it, you can reply to this email and have your
reply appear on GitHub as well. If your project does not have this feature
enabled and wishes so, or if the feature is enabled but not working, please
contact infrastructure at infrastructure@apache.org or file a JIRA ticket
with INFRA.
---
[GitHub] flink pull request #3284: [FLINK-1526] [Gelly] Add Minimum Spanning Tree lib...
Posted by greghogan <gi...@git.apache.org>.
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\u016fvka 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?
---
If your project is set up for it, you can reply to this email and have your
reply appear on GitHub as well. If your project does not have this feature
enabled and wishes so, or if the feature is enabled but not working, please
contact infrastructure at infrastructure@apache.org or file a JIRA ticket
with INFRA.
---