如何通过Apache Spark graphX获取SSSP实际路径? [英] How to get SSSP actual path by apache spark graphX?

问题描述

我在spark网站上运行了单源最短路径(SSSP)示例，如下所示:

I have ran the single source shortest path (SSSP) example on spark site as follows:

graphx-SSSP预凝胶示例

代码(标量):

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
得到结果:
(0,0.0)
(4,2.0)
(2,1.0)
(3,1.0)
(1,2.0)

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

但是我需要如下所示的实际路径:
=>
0-> 0,0
0-> 2,1
0-> 3,1
0-> 2-> 4,2
0-> 3-> 1,2

But I need actual path like as follows:
=>
0 -> 0,0
0 -> 2,1
0 -> 3,1
0 -> 2 -> 4,2
0 -> 3 -> 1,2

如何通过spark graphX获取SSSP实际路径?
有人给我一些提示吗?
感谢您的帮助！

How to get SSSP actual path by spark graphX?
anybody give me some hint?
Thanks for your help!

推荐答案

您必须修改算法才能存储最短路径长度和实际路径. 因此，除了存储Double作为顶点的属性外，还应该存储元组:(Double, List[VertexId]) 也许这段代码对您有用.

You have to modify algorithm in order to store not only shortest path length but also actual path. So instead of storing Double as property of vertex you should store tuple: (Double, List[VertexId]) Maybe this code can be useful for 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"))
  }
}

这篇关于如何通过Apache Spark graphX获取SSSP实际路径?的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！