Repository: spark Updated Branches: refs/heads/branch-1.2 e90f6b5c6 -> 37db20c94
[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 <kikushima.ke...@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. (cherry picked from commit 3ee3ab592eee831d759c940eb68231817ad6d083) Signed-off-by: Ankur Dave <ankurd...@gmail.com> Project: http://git-wip-us.apache.org/repos/asf/spark/repo Commit: http://git-wip-us.apache.org/repos/asf/spark/commit/37db20c9 Tree: http://git-wip-us.apache.org/repos/asf/spark/tree/37db20c9 Diff: http://git-wip-us.apache.org/repos/asf/spark/diff/37db20c9 Branch: refs/heads/branch-1.2 Commit: 37db20c9414d26ebd423e9500825bedc037b20f5 Parents: e90f6b5 Author: Kenji Kikushima <kikushima.ke...@lab.ntt.co.jp> Authored: Wed Jan 21 12:34:00 2015 -0800 Committer: Ankur Dave <ankurd...@gmail.com> Committed: Wed Jan 21 12:38:09 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/37db20c9/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/37db20c9/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-unsubscr...@spark.apache.org For additional commands, e-mail: commits-h...@spark.apache.org
