Implementing topological sort in Spark GraphX

Question

I am trying to implement topological sort using Spark's GraphX library.

This is the code I've written so far:

MyObject.scala

import java.util.ArrayList

import scala.collection.mutable.Queue

import org.apache.spark.SparkConf
import org.apache.spark.SparkContext
import org.apache.spark.graphx.Edge
import org.apache.spark.graphx.EdgeDirection
import org.apache.spark.graphx.Graph
import org.apache.spark.graphx.Graph.graphToGraphOps
import org.apache.spark.graphx.VertexId
import org.apache.spark.rdd.RDD
import org.apache.spark.rdd.RDD.rddToPairRDDFunctions

object MyObject {

  def main(args: Array[String]): Unit = {
    val conf = new SparkConf().setAppName("Spark-App").setMaster("local[2]")
    val sc = new SparkContext(conf)

    val resources: RDD[Resource] = makeResources(sc)
    val relations: RDD[Relation] = makeRelations(sc)

    println("Building graph ...")
    var graph = buildGraph(resources, relations, sc)
    println("Graph built!!")

    println("Testing topo sort ...")
    val topoSortResult = topoSort(graph, sc);
    println("topoSortResult = " + topoSortResult)
    println("Testing topo sort done!")
  }

  def buildGraph(resources: RDD[Resource], relations: RDD[Relation], sc: SparkContext): Graph[Resource, Relation] =
    {
      val vertices: RDD[(Long, Resource)] = resources.map(resource => (resource.id, resource))
      val edges: RDD[Edge[Relation]] = relations.map(relation => Edge(relation.srcId, relation.dstId, relation))
      var graph = Graph[Resource, Relation](vertices, edges)
      graph
    }

  def makeResources(sc: SparkContext): RDD[Resource] =
    {
      var list: List[Resource] = List()
      list = list :+ new Resource(1L)
      list = list :+ new Resource(2L)
      list = list :+ new Resource(3L)
      list = list :+ new Resource(4L)
      list = list :+ new Resource(5L)
      sc.parallelize(list)
    }

  def makeRelations(sc: SparkContext): RDD[Relation] =
    {
      var list: List[Relation] = List()
      list = list :+ new Relation(1L, "depends_on", 2L)
      list = list :+ new Relation(3L, "depends_on", 2L)
      list = list :+ new Relation(4L, "depends_on", 2L)
      list = list :+ new Relation(5L, "depends_on", 2L)
      sc.parallelize(list)

    }

  def topoSort(graph: Graph[Resource, Relation], sc: SparkContext): java.util.List[(VertexId, Resource)] =
    {
      // Will contain the result
      val sortedResources: java.util.List[(VertexId, Resource)] = new ArrayList()

      // Contains all the vertices
      val vertices = graph.vertices

      // Contains all the vertices whose in-degree > 0
      val inDegrees = graph.inDegrees;
      val inDegreesKeys_array = inDegrees.keys.collect();

      // Contains all the vertices whose in-degree == 0
      val inDegreeZeroList = vertices.filter(vertex => !inDegreesKeys_array.contains(vertex._1))

      // A map of vertexID vs its in-degree
      val inDegreeMapRDD = inDegreeZeroList.map(vertex => (vertex._1, 0)).union(inDegrees);

      // Insert all the resources whose in-degree == 0 into a queue
      val queue = new Queue[(VertexId, Resource)]
      for (vertex <- inDegreeZeroList.toLocalIterator) { queue.enqueue(vertex) }

      // Get an RDD containing the outgoing edges of every vertex
      val neighbours = graph.collectNeighbors(EdgeDirection.Out)

      // Initiate the algorithm
      while (!queue.isEmpty) {
        val vertex_top = queue.dequeue()
        // Add the topmost element of the queue to the result
        sortedResources.add(vertex_top)

        // Get the neigbours (from outgoing edges) of this vertex
        // This will be an RDD containing just 1 element which will be an array of neighbour vertices
        val vertex_neighbours = neighbours.filter(vertex => vertex._1.equals(vertex_top._1))

        // For each vertex, decrease its in-degree by 1
        vertex_neighbours.foreach(arr => {
          val neighbour_array = arr._2
          neighbour_array.foreach(vertex => {
            val oldInDegree = inDegreeMapRDD.filter(vertex_iter => (vertex_iter._1 == vertex._1)).first()._2
            val newInDegree = oldInDegree - 1
            // Reflect the new in-degree in the in-degree map RDD
            inDegreeMapRDD.map(vertex_iter => {
              if (vertex_iter._1 == vertex._1) {
                (vertex._1, newInDegree)
              }
              else{
                vertex_iter
              }
            });
            // Add this vertex to the result if its in-degree has become zero
            if (newInDegree == 0) {
              queue.enqueue(vertex)
            }
          })
        })
      }

      return sortedResources
    }

}

Resource.scala

class Resource(val id: Long) extends Serializable {
  override def toString(): String = {
    "id = " + id
  }
}

Relation.scala

class Relation(val srcId: Long, val name: String, val dstId: Long) extends Serializable {
  override def toString(): String = {
    srcId + " " + name + " " + dstId
  }
}

I am getting the error :

org.apache.spark.SparkException: RDD transformations and actions can only be invoked by the driver, not inside of other transformations; for example, rdd1.map(x => rdd2.values.count() * x) is invalid because the values transformation and count action cannot be performed inside of the rdd1.map transformation. For more information, see SPARK-5063.

for the line val oldInDegree = inDegreeMapRDD.filter(vertex_iter => (vertex_iter._1 == vertex._1)).first()._2.

I guess this is because it is illegal to modify an RDD inside the for-each loop of some other RDD.

Also, I fear that queue.enqueue(vertex) will not work, since it is not possible to modify a local collection inside a for-each loop.

How do I correctly implement this topological sort algorithm ?

The full stack trace of the exception is uploaded here (Had to upload it externally to prevent exceeding the body size limit of StackOverflow).

Eventide

Answer 1

vertex_neighbours.foreach(arr => {
      val neighbour_array = arr._2
      neighbour_array.foreach(vertex => {
      . . . 

The outer foreach could be replaced by a for loop.

Pease

Could you please show the final working version of the code with the changes you mentioned ? – Eventide

Answer 2

val vertex_neighbours = neighbours.filter(vertex => vertex._1.equals(vertex_top._1)).collect() 

You need to get the RDD before doing for loop over it.

Roath

Answer 3

The topological sorting algorithm implemented using spark graphx. The message passing starts from the nodes whose in-degree is zero and subsequently decreases the in-degree value for nodes which has connecting paths from u (in-degree == 0) to v (in-degree non-zero).

import scala.reflect.ClassTag
import org.apache.spark.graphx._

object TopologicalSort {

   def run[VD: ClassTag, ED: ClassTag](
     graph: Graph[VD, ED],
     maxIterations: Int = 500
): Graph[(Int, Int), ED] = {

val degreesMap = graph.inDegrees.collect().toMap
// initialize the graph vertices with in-degree value & topological order 
// equal to zero (in-degree, order)
val tsGraph = graph.mapVertices((vid, _) => (degreesMap.getOrElse(vid, 0), 0))

def sendMessage(edge: EdgeTriplet[(Int, Int), ED]): Iterator[(VertexId, (Int, Int))] =
  if (edge.srcAttr._1 == 0 && edge.dstAttr._1 > 0)
    Iterator((edge.dstId, (1, edge.srcAttr._2 + 1)))
  else Iterator.empty

def mergeMessage(a: (Int, Int), b: (Int, Int)): (Int, Int) = (a._1 + b._1, Math.min(a._2, b._2))

def vertexProgram(vid: VertexId, attr: (Int, Int), message: (Int, Int)): (Int, Int) =
  if (attr._1 == 0) (0, message._2) else (attr._1 - message._1, message._2)

val initialMsg = (0, 0)

Pregel(tsGraph, initialMsg, maxIterations, EdgeDirection.Out)(
  (vid, attr, msg) => vertexProgram(vid, attr, msg),
  sendMessage,
  mergeMessage
)}}

Waylonwayman