Graphframes BFS問題

Question

我測試graphframes BFS玩具例子：

val g: GraphFrame = examples.Graphs.friends 
val paths: DataFrame = g.bfs.fromExpr("name = 'Esther'").toExpr("name <> 'Esther'").run() 

結果我得到的是：

+-------------+------------+------------+ 
|   from|   e0|   to| 
+-------------+------------+------------+ 
|[e,Esther,32]|[e,f,follow]|[f,Fanny,36]| 
|[e,Esther,32]|[e,d,friend]|[d,David,29]| 
+-------------+------------+------------+ 

這是非常奇怪的，因爲芬妮與大衛也有出邊。鏈接到它們的頂點也具有輸出邊，例如，結果數據幀不僅應包含一個跳躍路徑，而且還應包含源頂點的所有路徑。

我自己創建了一個玩具圖：

1 2 
2 3 
3 4 
4 5 

當我做同樣類型的查詢：

g.bfs.fromExpr("id = 1").toExpr("id <> 1").run() 

我仍然只得到一個跳鄰居。我錯過了什麼嗎？我還測試了其他運營商，如果沒有成功，就代表「不平等」。瘋狂的猜測：也許當BFS再次到達源頂點（它應該看它，但不訪問其鄰居）時，它不匹配「toExpr」表達式並中止。

另一個問題：GraphFrames是否定向，是不是？爲了得到一個「非直接圖」，我應該添加相互的邊緣，不是嗎？

Answer 1

一旦到達範妮和大衛，你已經找到了從以斯帖到非以斯帖節點的最短路徑，所以搜索停止。

根據GraphFrames User Guide，bfs方法「找到從一個頂點（或一組頂點）到另一個頂點（或一組頂點）的最短路徑。開始和結束頂點被指定爲Spark DataFrame表達式「。

在你使用的圖表中，Esther到非Esther節點的最短路徑只是一跳，所以廣度優先搜索停在那裏。

考慮你的數字玩具圖。你發現這個（一跳）：

import org.graphframes.GraphFrame 

val edgesDf = spark.sqlContext.createDataFrame(Seq(
    (1, 2), 
    (2, 3), 
    (3, 4), 
    (4, 5)  
)).toDF("src", "dst") 

val g = GraphFrame.fromEdges(edgesDf) 
g.bfs.fromExpr("id = 1").toExpr("id <> 1").run().show() 

+----+-----+---+ 
|from| e0| to| 
+----+-----+---+ 
| [1]|[1,2]|[2]| 
+----+-----+---+ 

假設你問，它是這樣，而不是：

g.bfs.fromExpr("id = 1").toExpr("id > 3").run().show() 

+----+-----+---+-----+---+-----+---+ 
|from| e0| v1| e1| v2| e2| to| 
+----+-----+---+-----+---+-----+---+ 
| [1]|[1,2]|[2]|[2,3]|[3]|[3,4]|[4]| 
+----+-----+---+-----+---+-----+---+ 

現在bfs方法有三個跳。這是從1到大於3的節點的最短路徑。儘管存在從4到5（和5> 3）的邊緣，但它不會繼續，因爲這會是更長的路徑（4跳）。

另一個問題：GraphFrames是否定向，是不是？爲了得到一個「非直接圖」，我應該添加相互的邊緣，不是嗎？

我認爲這取決於你想應用到圖的算法。有人可能會編寫一個算法，忽略底層的DataFrame中的方向。但是如果一個算法假設有向圖，那麼我認爲你是對的：你必須添加相反的邊。

如果您將此作爲單獨問題提出，您可能會得到更好的回覆（來自其他人）。