Apache-Spark圖框在BFS上非常緩慢

Question

我在下面的代碼中使用Scala使用Apache Spark-GraphFrames，我在上面的代碼中應用BFS並嘗試找到Vertice 0到100之間的距離。

import org.apache.spark._ 
import org.graphframes._ 
import org.graphframes.GraphFrame 
import org.apache.spark.sql.DataFrame 
import org.apache.spark.sql.SQLContext 
object SimpApp{ 
def main(args: Array[String]) { 
val conf = new SparkConf().setAppName("SimpApp") 
val sc = new SparkContext(conf) 
val sqlContext = new SQLContext(sc) 
val nodesList = sqlContext.read.format("com.databricks.spark.csv").option("header", "true").option("inferSchema", "true").load("CSV File Path") 
val edgesList= sqlContext.read.format("com.databricks.spark.csv").option("header", "true").option("inferSchema", "true").load("CSV File Path") 
val v=nodesList.toDF("id") 
val e=edgesList.toDF("src", "dst", "dist") 
val g = GraphFrame(v, e) 
var paths: DataFrame = g.bfs.fromExpr("id = 0").toExpr(s"id = 100").maxPathLength(101).run() 
paths.show() 
sc.stop() 
} 
} 

Soucre節點：0目的地節點：100

頂點列表是下面給出

id 
0 
1 
2 
3 
. 
. 
. 
up to 
1000 

這裏是邊列表

src dst dist 
0 1 2 
1, 2, 1 
2, 3, 5 
3, 4, 1 
4, 5, 3 
5, 6, 3 
6, 7, 6 
. . . 
. . . 
. . . 
up to 
999, 998, 4 

但是，上面給出的代碼的問題是，它需要大量的時間執行0到100個頂點，因爲它運行了4個小時但沒有輸出。 上面的代碼我運行在具有12 GB RAM的單機上。

可以請指導我加快和優化代碼。

Answer 1

爲了驗證，我認爲您正在嘗試爲圖的未加權邊緣找到最短距離，因此使用BFS。在這種情況下，你可能希望從你的查詢中刪除maxPathLength(101)所以它：

g.bfs.fromExpr("id = 0").toExpr("id = 100").run() 

正如BFS definition指出：

maxPathLength是與 默認的路徑的長度極限10.如果找不到長度爲< = maxPathLength的有效路徑，則BFS終止。

通過頂點0和頂點100之間的指定101，它將嘗試找到任何和所有邊緣從0到100具有的101因此大量迭代的長度。

BFS和最短距離的一個有趣的例子可以描述在關於航班的經典圖情景中（參考：On-Time Flight Performance with GraphFrames for Apache Spark），其中頂點（或節點）是機場，而邊是這些機場之間的航班。

如果你想找到SFO（舊金山）和BUF（布法羅）之間的直飛航班，該BFS查詢將是：

tripGraph.bfs.fromExpr("id = 'SFO'").toExpr("id = 'BUF').maxPathLength(1).run 

這在引用的鏈接指出的，沒有直航，因此沒有結果。但如果增加maxPathLength至2（即即一個附加的SFO和BUF節點之間的節點），那麼你將發現許多路徑（例如SFO>BOS>BUF或舊金山到波士頓布法羅）

tripGraph.bfs.fromExpr("id = 'SFO'").toExpr("id = 'BUF').maxPathLength(2).run 

的