2

我在以下代码中使用使用 Scala 的 Apache Spark-GraphFrames，我在上面的代码中应用 BFS 并尝试找到顶点 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()
}
}

源节点：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 的单机上运行。

您能否指导我加快和优化代码。

4

1 回答 1

3

为了验证，我认为您正在尝试为图形的未加权边找到最短距离，因此使用了 BFS。在这种情况下，您可能希望maxPathLength(101)从查询中删除 ，以便它：

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

如BFS 定义中所述：

maxPathLength是路径长度的限制，默认值为 10。如果没有找到长度 <= maxPathLength 的有效路径，则终止 BFS。

通过在顶点 0 和顶点 100 之间指定 101，它将尝试找到从 0 到 100 长度为 101 的任何和所有边，因此需要大量迭代。

BFS 和最短距离的一个有趣示例可以在有关航班的经典图形场景中描述（参考：On-Time Flight Performance with GraphFrames for Apache Spark），其中顶点（或节点）是机场，而边缘是那些之间的航班机场。

SFO如果您要查找(San Francisco) 和(Buffalo)之间的直达航班BUF，BFS 查询将是：

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

如引用链接中所述，没有直飞航班，因此没有结果。但是，如果将 增加到2（即在和maxPathLength节点之间增加一个节点），那么您会发现许多路径（例如> >或旧金山到波士顿到布法罗）SFOBUFSFOBOSBUF

tripGraph.bfs.fromExpr("id = 'SFO'").toExpr("id = 'BUF').maxPathLength(2).run
于 2016-12-19T18:37:54.823 回答