You are viewing a plain text version of this content. The canonical link for it is here.
Posted to commits@spark.apache.org by an...@apache.org on 2015/01/21 21:37:56 UTC
spark git commit: [SPARK-5064][GraphX] Add numEdges upperbound
validation for R-MAT graph generator to prevent infinite loop
Repository: spark
Updated Branches:
refs/heads/master 7450a992b -> 3ee3ab592
[SPARK-5064][GraphX] Add numEdges upperbound validation for R-MAT graph generator to prevent infinite loop
I looked into GraphGenerators#chooseCell, and found that chooseCell can't generate more edges than pow(2, (2 * (log2(numVertices)-1))) to make a Power-law graph. (Ex. numVertices:4 upperbound:4, numVertices:8 upperbound:16, numVertices:16 upperbound:64)
If we request more edges over the upperbound, rmatGraph fall into infinite loop. So, how about adding an argument validation?
Author: Kenji Kikushima <ki...@lab.ntt.co.jp>
Closes #3950 from kj-ki/SPARK-5064 and squashes the following commits:
4ee18c7 [Ankur Dave] Reword error message and add unit test
d760bc7 [Kenji Kikushima] Add numEdges upperbound validation for R-MAT graph generator to prevent infinite loop.
Project: http://git-wip-us.apache.org/repos/asf/spark/repo
Commit: http://git-wip-us.apache.org/repos/asf/spark/commit/3ee3ab59
Tree: http://git-wip-us.apache.org/repos/asf/spark/tree/3ee3ab59
Diff: http://git-wip-us.apache.org/repos/asf/spark/diff/3ee3ab59
Branch: refs/heads/master
Commit: 3ee3ab592eee831d759c940eb68231817ad6d083
Parents: 7450a99
Author: Kenji Kikushima <ki...@lab.ntt.co.jp>
Authored: Wed Jan 21 12:34:00 2015 -0800
Committer: Ankur Dave <an...@gmail.com>
Committed: Wed Jan 21 12:36:03 2015 -0800
----------------------------------------------------------------------
.../org/apache/spark/graphx/util/GraphGenerators.scala | 6 ++++++
.../apache/spark/graphx/util/GraphGeneratorsSuite.scala | 10 ++++++++++
2 files changed, 16 insertions(+)
----------------------------------------------------------------------
http://git-wip-us.apache.org/repos/asf/spark/blob/3ee3ab59/graphx/src/main/scala/org/apache/spark/graphx/util/GraphGenerators.scala
----------------------------------------------------------------------
diff --git a/graphx/src/main/scala/org/apache/spark/graphx/util/GraphGenerators.scala b/graphx/src/main/scala/org/apache/spark/graphx/util/GraphGenerators.scala
index 8a13c74..2d6a825 100644
--- a/graphx/src/main/scala/org/apache/spark/graphx/util/GraphGenerators.scala
+++ b/graphx/src/main/scala/org/apache/spark/graphx/util/GraphGenerators.scala
@@ -133,6 +133,12 @@ object GraphGenerators {
// This ensures that the 4 quadrants are the same size at all recursion levels
val numVertices = math.round(
math.pow(2.0, math.ceil(math.log(requestedNumVertices) / math.log(2.0)))).toInt
+ val numEdgesUpperBound =
+ math.pow(2.0, 2 * ((math.log(numVertices) / math.log(2.0)) - 1)).toInt
+ if (numEdgesUpperBound < numEdges) {
+ throw new IllegalArgumentException(
+ s"numEdges must be <= $numEdgesUpperBound but was $numEdges")
+ }
var edges: Set[Edge[Int]] = Set()
while (edges.size < numEdges) {
if (edges.size % 100 == 0) {
http://git-wip-us.apache.org/repos/asf/spark/blob/3ee3ab59/graphx/src/test/scala/org/apache/spark/graphx/util/GraphGeneratorsSuite.scala
----------------------------------------------------------------------
diff --git a/graphx/src/test/scala/org/apache/spark/graphx/util/GraphGeneratorsSuite.scala b/graphx/src/test/scala/org/apache/spark/graphx/util/GraphGeneratorsSuite.scala
index 3abefbe..8d9c8dd 100644
--- a/graphx/src/test/scala/org/apache/spark/graphx/util/GraphGeneratorsSuite.scala
+++ b/graphx/src/test/scala/org/apache/spark/graphx/util/GraphGeneratorsSuite.scala
@@ -110,4 +110,14 @@ class GraphGeneratorsSuite extends FunSuite with LocalSparkContext {
}
}
+ test("SPARK-5064 GraphGenerators.rmatGraph numEdges upper bound") {
+ withSpark { sc =>
+ val g1 = GraphGenerators.rmatGraph(sc, 4, 4)
+ assert(g1.edges.count() === 4)
+ intercept[IllegalArgumentException] {
+ val g2 = GraphGenerators.rmatGraph(sc, 4, 8)
+ }
+ }
+ }
+
}
---------------------------------------------------------------------
To unsubscribe, e-mail: commits-unsubscribe@spark.apache.org
For additional commands, e-mail: commits-help@spark.apache.org