8

次のように、spark サイトで単一ソースの最短パス (SSSP) の例を実行しました。

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)

しかし、次のような実際のパスが必要です:
=>
0 -> 0,0
0 -> 2,1
0 -> 3,1
0 -> 2 -> 4,2
0 -> 3 -> 1,2

spark graphXでSSSPの実際のパスを取得するには?
誰かヒントをくれませんか？
ご協力いただきありがとうございます！

4

2 に答える 2

0

時代遅れの答えかもしれませんが、このソリューションを見てくださいApache Sparkを使用してグラフ内のすべてのパスを見つける

于 2015-08-28T12:59:02.860 に答える