[GitHub] flink pull request: [FLINK-3945] [gelly] Degree annotation for dir...

2016-05-25 Thread greghogan 
Github user greghogan commented on a diff in the pull request:

https://github.com/apache/flink/pull/2021#discussion_r64594890
  
--- Diff: 
flink-libraries/flink-gelly/src/main/java/org/apache/flink/graph/asm/degree/annotate/directed/EdgeDegreesPair.java
 ---
@@ -0,0 +1,81 @@
+/*
+ * 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.asm.degree.annotate.directed;
+
+import org.apache.flink.api.common.ExecutionConfig;
+import 
org.apache.flink.api.common.operators.base.JoinOperatorBase.JoinHint;
+import org.apache.flink.api.java.DataSet;
+import org.apache.flink.api.java.tuple.Tuple2;
+import org.apache.flink.api.java.tuple.Tuple3;
+import org.apache.flink.graph.Edge;
+import org.apache.flink.graph.Graph;
+import org.apache.flink.graph.GraphAlgorithm;
+import org.apache.flink.graph.Vertex;
+import 
org.apache.flink.graph.asm.degree.annotate.DegreeAnnotationFunctions.JoinEdgeDegreeWithVertexDegree;
+import 
org.apache.flink.graph.asm.degree.annotate.directed.VertexDegrees.Degrees;
+
+/**
+ * Annotates edges of a directed graph with the degree, out-degree, and
+ * in-degree of both the source and target vertices.
+ *
+ * @param  ID type
+ * @param  vertex value type
+ * @param  edge value type
+ */
+public class EdgeDegreesPair
+implements GraphAlgorithm setParallelism(int parallelism) {
+   this.parallelism = parallelism;
+
+   return this;
+   }
+
+   @Override
+   public DataSet>> run(Graph input)
+   throws Exception {
+   // s, t, d(s)
+   DataSet>> edgeSourceDegrees = input
+   .run(new EdgeSourceDegrees()
+   .setParallelism(parallelism));
+
+   // t, d(t)
+   DataSet> vertexDegrees = input
+   .run(new VertexDegrees()
+   .setParallelism(parallelism));
+
+   // s, t, (d(s), d(t))
+   return edgeSourceDegrees
+   .join(vertexDegrees, JoinHint.REPARTITION_HASH_SECOND)
--- End diff --

I'm amenable to adding this configuration if we can show noticeably 
improved performance. Choosing a bad `JoinHint` will result in significantly 
degraded performance for most graphs in addition to adding to the user's 
cognitive load.


---
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 infrastruct...@apache.org or file a JIRA ticket
with INFRA.
---

[GitHub] flink pull request: [FLINK-3945] [gelly] Degree annotation for dir...

2016-05-25 Thread vasia 
Github user vasia commented on a diff in the pull request:

https://github.com/apache/flink/pull/2021#discussion_r64589442
  
--- Diff: 
flink-libraries/flink-gelly/src/main/java/org/apache/flink/graph/asm/degree/annotate/directed/EdgeDegreesPair.java
 ---
@@ -0,0 +1,81 @@
+/*
+ * 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.asm.degree.annotate.directed;
+
+import org.apache.flink.api.common.ExecutionConfig;
+import 
org.apache.flink.api.common.operators.base.JoinOperatorBase.JoinHint;
+import org.apache.flink.api.java.DataSet;
+import org.apache.flink.api.java.tuple.Tuple2;
+import org.apache.flink.api.java.tuple.Tuple3;
+import org.apache.flink.graph.Edge;
+import org.apache.flink.graph.Graph;
+import org.apache.flink.graph.GraphAlgorithm;
+import org.apache.flink.graph.Vertex;
+import 
org.apache.flink.graph.asm.degree.annotate.DegreeAnnotationFunctions.JoinEdgeDegreeWithVertexDegree;
+import 
org.apache.flink.graph.asm.degree.annotate.directed.VertexDegrees.Degrees;
+
+/**
+ * Annotates edges of a directed graph with the degree, out-degree, and
+ * in-degree of both the source and target vertices.
+ *
+ * @param  ID type
+ * @param  vertex value type
+ * @param  edge value type
+ */
+public class EdgeDegreesPair
+implements GraphAlgorithm setParallelism(int parallelism) {
+   this.parallelism = parallelism;
+
+   return this;
+   }
+
+   @Override
+   public DataSet>> run(Graph input)
+   throws Exception {
+   // s, t, d(s)
+   DataSet>> edgeSourceDegrees = input
+   .run(new EdgeSourceDegrees()
+   .setParallelism(parallelism));
+
+   // t, d(t)
+   DataSet> vertexDegrees = input
+   .run(new VertexDegrees()
+   .setParallelism(parallelism));
+
+   // s, t, (d(s), d(t))
+   return edgeSourceDegrees
+   .join(vertexDegrees, JoinHint.REPARTITION_HASH_SECOND)
--- End diff --

I agree that we should automatically set the parameters when possible. So, 
I would keep this as the default setting. However, I think we should allow 
users that _do_ have knowledge about the input graph to either let the 
optimizer decide or override the default setting.


---
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 infrastruct...@apache.org or file a JIRA ticket
with INFRA.
---

[GitHub] flink pull request: [FLINK-3945] [gelly] Degree annotation for dir...

2016-05-25 Thread greghogan 
Github user greghogan commented on a diff in the pull request:

https://github.com/apache/flink/pull/2021#discussion_r64587577
  
--- Diff: 
flink-libraries/flink-gelly/src/main/java/org/apache/flink/graph/asm/degree/annotate/directed/EdgeDegreesPair.java
 ---
@@ -0,0 +1,81 @@
+/*
+ * 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.asm.degree.annotate.directed;
+
+import org.apache.flink.api.common.ExecutionConfig;
+import 
org.apache.flink.api.common.operators.base.JoinOperatorBase.JoinHint;
+import org.apache.flink.api.java.DataSet;
+import org.apache.flink.api.java.tuple.Tuple2;
+import org.apache.flink.api.java.tuple.Tuple3;
+import org.apache.flink.graph.Edge;
+import org.apache.flink.graph.Graph;
+import org.apache.flink.graph.GraphAlgorithm;
+import org.apache.flink.graph.Vertex;
+import 
org.apache.flink.graph.asm.degree.annotate.DegreeAnnotationFunctions.JoinEdgeDegreeWithVertexDegree;
+import 
org.apache.flink.graph.asm.degree.annotate.directed.VertexDegrees.Degrees;
+
+/**
+ * Annotates edges of a directed graph with the degree, out-degree, and
+ * in-degree of both the source and target vertices.
+ *
+ * @param  ID type
+ * @param  vertex value type
+ * @param  edge value type
+ */
+public class EdgeDegreesPair
+implements GraphAlgorithm setParallelism(int parallelism) {
+   this.parallelism = parallelism;
+
+   return this;
+   }
+
+   @Override
+   public DataSet>> run(Graph input)
+   throws Exception {
+   // s, t, d(s)
+   DataSet>> edgeSourceDegrees = input
+   .run(new EdgeSourceDegrees()
+   .setParallelism(parallelism));
+
+   // t, d(t)
+   DataSet> vertexDegrees = input
+   .run(new VertexDegrees()
+   .setParallelism(parallelism));
+
+   // s, t, (d(s), d(t))
+   return edgeSourceDegrees
+   .join(vertexDegrees, JoinHint.REPARTITION_HASH_SECOND)
--- End diff --

Algorithms should not expect the user to have knowledge of the input graph 
or divine the best configuration. Worst case for an undirected graph is twice 
as many vertices as edges. 


---
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 infrastruct...@apache.org or file a JIRA ticket
with INFRA.
---

[GitHub] flink pull request: [FLINK-3945] [gelly] Degree annotation for dir...

2016-05-25 Thread vasia 
Github user vasia commented on a diff in the pull request:

https://github.com/apache/flink/pull/2021#discussion_r64577865
  
--- Diff: 
flink-libraries/flink-gelly/src/main/java/org/apache/flink/graph/asm/degree/annotate/directed/EdgeDegreesPair.java
 ---
@@ -0,0 +1,81 @@
+/*
+ * 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.asm.degree.annotate.directed;
+
+import org.apache.flink.api.common.ExecutionConfig;
+import 
org.apache.flink.api.common.operators.base.JoinOperatorBase.JoinHint;
+import org.apache.flink.api.java.DataSet;
+import org.apache.flink.api.java.tuple.Tuple2;
+import org.apache.flink.api.java.tuple.Tuple3;
+import org.apache.flink.graph.Edge;
+import org.apache.flink.graph.Graph;
+import org.apache.flink.graph.GraphAlgorithm;
+import org.apache.flink.graph.Vertex;
+import 
org.apache.flink.graph.asm.degree.annotate.DegreeAnnotationFunctions.JoinEdgeDegreeWithVertexDegree;
+import 
org.apache.flink.graph.asm.degree.annotate.directed.VertexDegrees.Degrees;
+
+/**
+ * Annotates edges of a directed graph with the degree, out-degree, and
+ * in-degree of both the source and target vertices.
+ *
+ * @param  ID type
+ * @param  vertex value type
+ * @param  edge value type
+ */
+public class EdgeDegreesPair
+implements GraphAlgorithm setParallelism(int parallelism) {
+   this.parallelism = parallelism;
+
+   return this;
+   }
+
+   @Override
+   public DataSet>> run(Graph input)
+   throws Exception {
+   // s, t, d(s)
+   DataSet>> edgeSourceDegrees = input
+   .run(new EdgeSourceDegrees()
+   .setParallelism(parallelism));
+
+   // t, d(t)
+   DataSet> vertexDegrees = input
+   .run(new VertexDegrees()
+   .setParallelism(parallelism));
+
+   // s, t, (d(s), d(t))
+   return edgeSourceDegrees
+   .join(vertexDegrees, JoinHint.REPARTITION_HASH_SECOND)
--- End diff --

I'm not sure whether it's a good idea to always provide a join hint here. 
It's true that the vertex set is _usually_ much smaller than the edge set, but 
what if that's not true? Can we at least provide a way to override this 
configuration?


---
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 infrastruct...@apache.org or file a JIRA ticket
with INFRA.
---

[GitHub] flink pull request: [FLINK-3945] [gelly] Degree annotation for dir...

2016-05-23 Thread greghogan 
GitHub user greghogan opened a pull request:

https://github.com/apache/flink/pull/2021

[FLINK-3945] [gelly] Degree annotation for directed graphs



You can merge this pull request into a Git repository by running:

$ git pull https://github.com/greghogan/flink 
3945_degree_annotation_for_directed_graphs

Alternatively you can review and apply these changes as the patch at:

https://github.com/apache/flink/pull/2021.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 #2021


commit 2f79f88cbf32b84fe544232390ab2b6deee1ed0f
Author: Greg Hogan 
Date:   2016-05-20T16:54:16Z

[FLINK-3945] [gelly] Degree annotation for directed 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 infrastruct...@apache.org or file a JIRA ticket
with INFRA.
---