How to get the actual SSSP path using apache spark graphX?

Question

I used the single-source shortest path (SSSP) example on a spark site as follows:

Graphx-SSSP subroutine example

code (scala):

object Pregel_SSSP { def main(args: Array[String]) { val sc = new SparkContext("local", "Allen Pregel Test", System.getenv("SPARK_HOME"), SparkContext.jarOfClass(this.getClass)) // A graph with edge attributes containing distances val graph: Graph[Int, Double] = GraphGenerators.logNormalGraph(sc, numVertices = 5).mapEdges(e => e.attr.toDouble) graph.edges.foreach(println) val sourceId: VertexId = 0 // The ultimate source // Initialize the graph such that all vertices except the root have distance infinity. val initialGraph = graph.mapVertices((id, _) => if (id == sourceId) 0.0 else Double.PositiveInfinity) val sssp = initialGraph.pregel(Double.PositiveInfinity, Int.MaxValue, EdgeDirection.Out)( // Vertex Program (id, dist, newDist) => math.min(dist, newDist), // Send Message triplet => { if (triplet.srcAttr + triplet.attr < triplet.dstAttr) { Iterator((triplet.dstId, triplet.srcAttr + triplet.attr)) } else { Iterator.empty } }, //Merge Message (a, b) => math.min(a, b)) println(sssp.vertices.collect.mkString("\n")) } } 

sourceId: 0
Get the result:
(0,0.0)
(4,2.0)
(2,1.0)
(3.1.0)
(1,2.0)

But I need the actual path as below:
=>
0 → 0,0
0 → 2,1
0 → 3,1
0 → 2 → 4.2
0 → 3 → 1.2

How to get the actual SSSP path using spark graphX?
will someone tell me?
Thank you for your help!

Answer 1

You need to change the algorithm to store not only the shortest path length, but also the actual path. Therefore, instead of saving Double as a vertex property, you should store a tuple: (Double, List[VertexId]) Perhaps this code may be useful to you.

 object Pregel_SSSP { def main(args: Array[String]) { val sc = new SparkContext("local", "Allen Pregel Test", System.getenv("SPARK_HOME"), SparkContext.jarOfClass(this.getClass)) // A graph with edge attributes containing distances val graph: Graph[Int, Double] = GraphGenerators.logNormalGraph(sc, numVertices = 5).mapEdges(e => e.attr.toDouble) graph.edges.foreach(println) val sourceId: VertexId = 0 // The ultimate source // Initialize the graph such that all vertices except the root have distance infinity. val initialGraph : Graph[(Double, List[VertexId]), Double] = graph.mapVertices((id, _) => if (id == sourceId) (0.0, List[VertexId](sourceId)) else (Double.PositiveInfinity, List[VertexId]())) val sssp = initialGraph.pregel((Double.PositiveInfinity, List[VertexId]()), Int.MaxValue, EdgeDirection.Out)( // Vertex Program (id, dist, newDist) => if (dist._1 < newDist._1) dist else newDist, // Send Message triplet => { if (triplet.srcAttr._1 < triplet.dstAttr._1 - triplet.attr ) { Iterator((triplet.dstId, (triplet.srcAttr._1 + triplet.attr , triplet.srcAttr._2 :+ triplet.dstId))) } else { Iterator.empty } }, //Merge Message (a, b) => if (a._1 < b._1) a else b) println(sssp.vertices.collect.mkString("\n")) } } 

Answer 2

This may be an outdated answer, but look at this solution Find all paths in a graph using Apache Spark