SPARK-1329: Create pid2vid with correct number of partitions

ankurdave · ankurdave · commit 5a5c52a575bc · 2014-04-08T23:37:59.000-07:00
Each vertex partition is co-located with a pid2vid array created in RoutingTable.scala. This array maps edge partition IDs to the list of vertices in the current vertex partition that are mentioned by edges in that partition. Therefore the pid2vid array should have one entry per edge partition. GraphX currently creates one entry per vertex partition, which is a bug that leads to an ArrayIndexOutOfBoundsException when there are more edge partitions than vertex partitions. This commit fixes the bug and adds a test for this case. Resolves SPARK-1329. Thanks to Daniel Darabos for reporting this bug.
diff --git a/graphx/src/main/scala/org/apache/spark/graphx/impl/RoutingTable.scala b/graphx/src/main/scala/org/apache/spark/graphx/impl/RoutingTable.scala
@@ -69,9 +69,9 @@ class RoutingTable(edges: EdgeRDD[_], vertices: VertexRDD[_]) {
       vSet.iterator.map { vid => (vid, pid) }
     }
 
-    val numPartitions = vertices.partitions.size
+    val numEdgePartitions = edges.partitions.size
     vid2pid.partitionBy(vertices.partitioner.get).mapPartitions { iter =>
-      val pid2vid = Array.fill(numPartitions)(new PrimitiveVector[VertexId])
+      val pid2vid = Array.fill(numEdgePartitions)(new PrimitiveVector[VertexId])
       for ((vid, pid) <- iter) {
         pid2vid(pid) += vid
       }
diff --git a/graphx/src/test/scala/org/apache/spark/graphx/GraphSuite.scala b/graphx/src/test/scala/org/apache/spark/graphx/GraphSuite.scala
@@ -287,4 +287,16 @@ class GraphSuite extends FunSuite with LocalSparkContext {
     }
   }
 
+  test("more edge partitions than vertex partitions") {
+    withSpark { sc =>
+      val verts = sc.parallelize(List((1: VertexId, "a"), (2: VertexId, "b")), 1)
+      val edges = sc.parallelize(List(Edge(1, 2, 0), Edge(2, 1, 0)), 2)
+      val graph = Graph(verts, edges)
+      val triplets = graph.triplets.map(et => (et.srcId, et.dstId, et.srcAttr, et.dstAttr))
+        .collect.toSet
+      assert(triplets ===
+        Set((1: VertexId, 2: VertexId, "a", "b"), (2: VertexId, 1: VertexId, "b", "a")))
+    }
+  }
+
 }

Original file line number	Diff line number	Diff line change
`@@ -69,9 +69,9 @@ class RoutingTable(edges: EdgeRDD[_], vertices: VertexRDD[_]) {`
`69`	`69`	`vSet.iterator.map { vid => (vid, pid) }`
`70`	`70`	`}`
`71`	`71`
`72`		`- val numPartitions = vertices.partitions.size`
	`72`	`+ val numEdgePartitions = edges.partitions.size`
`73`	`73`	`vid2pid.partitionBy(vertices.partitioner.get).mapPartitions { iter =>`
`74`		`- val pid2vid = Array.fill(numPartitions)(new PrimitiveVector[VertexId])`
	`74`	`+ val pid2vid = Array.fill(numEdgePartitions)(new PrimitiveVector[VertexId])`
`75`	`75`	`for ((vid, pid) <- iter) {`
`76`	`76`	`pid2vid(pid) += vid`
`77`	`77`	`}`
Original file line number	Diff line number	Diff line change
`@@ -287,4 +287,16 @@ class GraphSuite extends FunSuite with LocalSparkContext {`
`287`	`287`	`}`
`288`	`288`	`}`
`289`	`289`
	`290`	`+ test("more edge partitions than vertex partitions") {`
	`291`	`+ withSpark { sc =>`
	`292`	`+ val verts = sc.parallelize(List((1: VertexId, "a"), (2: VertexId, "b")), 1)`
	`293`	`+ val edges = sc.parallelize(List(Edge(1, 2, 0), Edge(2, 1, 0)), 2)`
	`294`	`+ val graph = Graph(verts, edges)`
	`295`	`+ val triplets = graph.triplets.map(et => (et.srcId, et.dstId, et.srcAttr, et.dstAttr))`
	`296`	`+ .collect.toSet`
	`297`	`+ assert(triplets ===`
	`298`	`+ Set((1: VertexId, 2: VertexId, "a", "b"), (2: VertexId, 1: VertexId, "b", "a")))`
	`299`	`+ }`
	`300`	`+ }`
	`301`	`+`
`290`	`302`	`}`