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中的方向。但是如果一个算法假设有向图，那么我认为你是对的：你必须添加相反的边。

如果您将此作为单独问题提出，您可能会得到更好的回复（来自其他人）。