2

我正在测试 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 是有向的，不是吗？为了获得“无向图”，我应该添加倒数边，不是吗？

4

1 回答 1

0

到达 Fanny 和 David 后，您已找到从 Esther 到非 Esther 节点的最短路径，因此搜索停止。

根据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），它也不会继续，因为那将是一条更长的路径（四跳）。

另一个问题：GraphFrames 是有向的，不是吗？为了获得“无向图”，我应该添加倒数边，不是吗？

我认为这取决于您要应用于图表的算法。有人可以编写一个忽略底层edgesDataFrame 方向的算法。但是，如果算法假设有向图，那么我认为您是对的：您必须添加倒数边。

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

于 2017-09-15T18:25:24.307 回答