You are viewing a plain text version of this content. The canonical link for it is here.
Posted to issues@flink.apache.org by greghogan <gi...@git.apache.org> on 2016/04/17 01:39:22 UTC
[GitHub] flink pull request: [FLINK-3772] [gelly] Graph algorithms for vert...
GitHub user greghogan opened a pull request:
https://github.com/apache/flink/pull/1901
[FLINK-3772] [gelly] Graph algorithms for vertex and edge degree
Graph algorithms for annotating
* vertex degree for undirected graphs
* vertex out-, in-, and out- and in-degree for directed graphs
* edge source, target, and source and target degree for undirected graphs
You can merge this pull request into a Git repository by running:
$ git pull https://github.com/greghogan/flink 3772_graph_algorithms_for_vertex_and_edge_degree
Alternatively you can review and apply these changes as the patch at:
https://github.com/apache/flink/pull/1901.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 #1901
----
commit 6a19cd62e4556d8b0d0a688eceee1788a0dd4054
Author: Greg Hogan <co...@greghogan.com>
Date: 2016-04-16T14:30:58Z
[FLINK-3772] [gelly] Graph algorithms for vertex and edge degree
Graph algorithms for annotating
vertex degree for undirected graphs
vertex out-, in-, and out- and in-degree for directed graphs
edge source, target, and source and target degree for undirected graphs
----
---
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: [FLINK-3772] [gelly] Graph algorithms for vert...
Posted by greghogan <gi...@git.apache.org>.
Github user greghogan commented on the pull request:
https://github.com/apache/flink/pull/1901#issuecomment-217852205
Merging ...
---
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: [FLINK-3772] [gelly] Graph algorithms for vert...
Posted by vasia <gi...@git.apache.org>.
Github user vasia commented on a diff in the pull request:
https://github.com/apache/flink/pull/1901#discussion_r62310380
--- Diff: docs/apis/batch/libs/gelly.md ---
@@ -2067,7 +2067,92 @@ configuration.
<tbody>
<tr>
- <td><strong>TranslateGraphIds</strong></td>
+ <td>degree.annotate.directed.<br/><strong>VertexInDegree</strong></td>
+ <td>
+ <p>Annotate vertices of a directed graph with the in-degree count.</p>
--- End diff --
What do you mean by in-degree "count"? What's the result of this operation?
---
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: [FLINK-3772] [gelly] Graph algorithms for vert...
Posted by greghogan <gi...@git.apache.org>.
Github user greghogan commented on a diff in the pull request:
https://github.com/apache/flink/pull/1901#discussion_r62384029
--- Diff: docs/apis/batch/libs/gelly.md ---
@@ -2067,7 +2067,92 @@ configuration.
<tbody>
<tr>
- <td><strong>TranslateGraphIds</strong></td>
+ <td>degree.annotate.directed.<br/><strong>VertexInDegree</strong></td>
+ <td>
+ <p>Annotate vertices of a directed graph with the in-degree count.</p>
--- End diff --
I am removing "count" from the descriptions since "degree" implies a count.
---
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: [FLINK-3772] [gelly] Graph algorithms for vert...
Posted by vasia <gi...@git.apache.org>.
Github user vasia commented on a diff in the pull request:
https://github.com/apache/flink/pull/1901#discussion_r62460922
--- Diff: docs/apis/batch/libs/gelly.md ---
@@ -2067,7 +2067,92 @@ configuration.
<tbody>
<tr>
- <td><strong>TranslateGraphIds</strong></td>
+ <td>degree.annotate.directed.<br/><strong>VertexInDegree</strong></td>
+ <td>
+ <p>Annotate vertices of a directed graph with the in-degree count.</p>
+{% highlight java %}
+DataSet<Vertex<K, LongValue>> inDegree = graph
+ .run(new VertexInDegree()
+ .setIncludeZeroDegreeVertices(true));
+{% endhighlight %}
+ </td>
+ </tr>
+
+ <tr>
+ <td>degree.annotate.directed.<br/><strong>VertexOutDegree</strong></td>
+ <td>
+ <p>Annotate vertices of a directed graph with the out-degree count.</p>
+{% highlight java %}
+DataSet<Vertex<K, LongValue>> outDegree = graph
+ .run(new VertexOutDegree()
+ .setIncludeZeroDegreeVertices(true));
+{% endhighlight %}
+ </td>
+ </tr>
+
+ <tr>
+ <td>degree.annotate.directed.<br/><strong>VertexDegreePair</strong></td>
+ <td>
+ <p>Annotate vertices of a directed graph with both the out-degree and in-degree count.</p>
+{% highlight java %}
+DataSet<Vertex<K, Tuple2<LongValue, LongValue>>> pairDegree = graph
+ .run(new VertexDegreePair()
+ .setIncludeZeroDegreeVertices(true));
+{% endhighlight %}
+ </td>
+ </tr>
+
+ <tr>
+ <td>degree.annotate.undirected.<br/><strong>VertexDegree</strong></td>
+ <td>
+ <p>Annotate vertices of an undirected graph with the degree count.</p>
+{% highlight java %}
+DataSet<Vertex<K, LongValue>> degree = graph
+ .run(new VertexDegree()
+ .setIncludeZeroDegreeVertices(true)
+ .setReduceOnTargetId(true));
+{% endhighlight %}
+ </td>
+ </tr>
+
+ <tr>
+ <td>degree.annotate.undirected.<br/><strong>EdgeSourceDegree</strong></td>
+ <td>
+ <p>Annotate edges of an undirected graph with degree of the source ID.</p>
--- End diff --
So, this method expects an undirected graph as input? Or does it convert a directed graph input into an undirected one? Can you please add a note about the expected input?
---
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: [FLINK-3772] [gelly] Graph algorithms for vert...
Posted by greghogan <gi...@git.apache.org>.
Github user greghogan closed the pull request at:
https://github.com/apache/flink/pull/1901
---
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: [FLINK-3772] [gelly] Graph algorithms for vert...
Posted by greghogan <gi...@git.apache.org>.
Github user greghogan commented on the pull request:
https://github.com/apache/flink/pull/1901#issuecomment-217428888
@vasia I had looked at one of the failed tests and it wasn't due to bad logic but rather to running out of some minimal number of memory buffers. This results, I expect, from updating the `Graph` API's degree functions to translate the output of the degree algorithms. I think it is best to leave the `Graph` API as-is for now.
---
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: [FLINK-3772] [gelly] Graph algorithms for vert...
Posted by vasia <gi...@git.apache.org>.
Github user vasia commented on the pull request:
https://github.com/apache/flink/pull/1901#issuecomment-217403403
@greghogan, after your last commit, there are several gelly test cases failing on travis. Could you please take a look? Thanks!
---
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: [FLINK-3772] [gelly] Graph algorithms for vert...
Posted by vasia <gi...@git.apache.org>.
Github user vasia commented on a diff in the pull request:
https://github.com/apache/flink/pull/1901#discussion_r62310412
--- Diff: docs/apis/batch/libs/gelly.md ---
@@ -2067,7 +2067,92 @@ configuration.
<tbody>
<tr>
- <td><strong>TranslateGraphIds</strong></td>
+ <td>degree.annotate.directed.<br/><strong>VertexInDegree</strong></td>
+ <td>
+ <p>Annotate vertices of a directed graph with the in-degree count.</p>
+{% highlight java %}
+DataSet<Vertex<K, LongValue>> inDegree = graph
+ .run(new VertexInDegree()
+ .setIncludeZeroDegreeVertices(true));
+{% endhighlight %}
+ </td>
+ </tr>
+
+ <tr>
+ <td>degree.annotate.directed.<br/><strong>VertexOutDegree</strong></td>
+ <td>
+ <p>Annotate vertices of a directed graph with the out-degree count.</p>
+{% highlight java %}
+DataSet<Vertex<K, LongValue>> outDegree = graph
+ .run(new VertexOutDegree()
+ .setIncludeZeroDegreeVertices(true));
+{% endhighlight %}
+ </td>
+ </tr>
+
+ <tr>
+ <td>degree.annotate.directed.<br/><strong>VertexDegreePair</strong></td>
+ <td>
+ <p>Annotate vertices of a directed graph with both the out-degree and in-degree count.</p>
+{% highlight java %}
+DataSet<Vertex<K, Tuple2<LongValue, LongValue>>> pairDegree = graph
+ .run(new VertexDegreePair()
+ .setIncludeZeroDegreeVertices(true));
+{% endhighlight %}
+ </td>
+ </tr>
+
+ <tr>
+ <td>degree.annotate.undirected.<br/><strong>VertexDegree</strong></td>
+ <td>
+ <p>Annotate vertices of an undirected graph with the degree count.</p>
+{% highlight java %}
+DataSet<Vertex<K, LongValue>> degree = graph
+ .run(new VertexDegree()
+ .setIncludeZeroDegreeVertices(true)
+ .setReduceOnTargetId(true));
+{% endhighlight %}
+ </td>
+ </tr>
+
+ <tr>
+ <td>degree.annotate.undirected.<br/><strong>EdgeSourceDegree</strong></td>
+ <td>
+ <p>Annotate edges of an undirected graph with degree of the source ID.</p>
--- End diff --
When you say "undirected" graph, do you mean the algorithm does not take into account the edge direction or does the input graph have to be undirected? Since gelly graphs are in fact always directed and we simply add opposite-direction edges to represent undirected graphs, we should be clear about this. Also, which is the source vertex is an undirected edge?
---
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: [FLINK-3772] [gelly] Graph algorithms for vert...
Posted by vasia <gi...@git.apache.org>.
Github user vasia commented on a diff in the pull request:
https://github.com/apache/flink/pull/1901#discussion_r62310388
--- Diff: docs/apis/batch/libs/gelly.md ---
@@ -2067,7 +2067,92 @@ configuration.
<tbody>
<tr>
- <td><strong>TranslateGraphIds</strong></td>
+ <td>degree.annotate.directed.<br/><strong>VertexInDegree</strong></td>
+ <td>
+ <p>Annotate vertices of a directed graph with the in-degree count.</p>
+{% highlight java %}
+DataSet<Vertex<K, LongValue>> inDegree = graph
+ .run(new VertexInDegree()
+ .setIncludeZeroDegreeVertices(true));
--- End diff --
What does the `setIncludeZeroDegreeVertices` do and what other options are available? Could you please document all of them (for the rest of algorithms also)?
---
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: [FLINK-3772] [gelly] Graph algorithms for vert...
Posted by vasia <gi...@git.apache.org>.
Github user vasia commented on the pull request:
https://github.com/apache/flink/pull/1901#issuecomment-217799706
I've only left a minor comment @greghogan, otherwise I think it's good to merge.
---
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: [FLINK-3772] [gelly] Graph algorithms for vert...
Posted by greghogan <gi...@git.apache.org>.
Github user greghogan commented on a diff in the pull request:
https://github.com/apache/flink/pull/1901#discussion_r62325628
--- Diff: docs/apis/batch/libs/gelly.md ---
@@ -2067,7 +2067,92 @@ configuration.
<tbody>
<tr>
- <td><strong>TranslateGraphIds</strong></td>
+ <td>degree.annotate.directed.<br/><strong>VertexInDegree</strong></td>
+ <td>
+ <p>Annotate vertices of a directed graph with the in-degree count.</p>
+{% highlight java %}
+DataSet<Vertex<K, LongValue>> inDegree = graph
+ .run(new VertexInDegree()
+ .setIncludeZeroDegreeVertices(true));
+{% endhighlight %}
+ </td>
+ </tr>
+
+ <tr>
+ <td>degree.annotate.directed.<br/><strong>VertexOutDegree</strong></td>
+ <td>
+ <p>Annotate vertices of a directed graph with the out-degree count.</p>
+{% highlight java %}
+DataSet<Vertex<K, LongValue>> outDegree = graph
+ .run(new VertexOutDegree()
+ .setIncludeZeroDegreeVertices(true));
+{% endhighlight %}
+ </td>
+ </tr>
+
+ <tr>
+ <td>degree.annotate.directed.<br/><strong>VertexDegreePair</strong></td>
+ <td>
+ <p>Annotate vertices of a directed graph with both the out-degree and in-degree count.</p>
+{% highlight java %}
+DataSet<Vertex<K, Tuple2<LongValue, LongValue>>> pairDegree = graph
+ .run(new VertexDegreePair()
+ .setIncludeZeroDegreeVertices(true));
+{% endhighlight %}
+ </td>
+ </tr>
+
+ <tr>
+ <td>degree.annotate.undirected.<br/><strong>VertexDegree</strong></td>
+ <td>
+ <p>Annotate vertices of an undirected graph with the degree count.</p>
+{% highlight java %}
+DataSet<Vertex<K, LongValue>> degree = graph
+ .run(new VertexDegree()
+ .setIncludeZeroDegreeVertices(true)
+ .setReduceOnTargetId(true));
+{% endhighlight %}
+ </td>
+ </tr>
+
+ <tr>
+ <td>degree.annotate.undirected.<br/><strong>EdgeSourceDegree</strong></td>
+ <td>
+ <p>Annotate edges of an undirected graph with degree of the source ID.</p>
--- End diff --
An `Edge` is always directed but a `Graph` may be undirected if it contains a matching reverse of every edge.
---
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: [FLINK-3772] [gelly] Graph algorithms for vert...
Posted by greghogan <gi...@git.apache.org>.
Github user greghogan commented on the pull request:
https://github.com/apache/flink/pull/1901#issuecomment-217868088
Closed in 70181b28cf17e25b4b70f21f718ada2537cde2b6
---
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.
---