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 を指定することで、101 の長さを持つ 0 から 100 までのすべてのエッジを見つけようとするため、反復回数が多くなります。

BFS と最短距離の楽しい例は、頂点 (またはノード) が空港であり、エッジがそれらの間のフライトであるフライトに関する古典的なグラフ シナリオ (参照: Apache Spark の GraphFrames を使用したオンタイム フライト パフォーマンス) で説明できます。空港。

SFO(サンフランシスコ) と(バッファロー)間の直行便を探している場合BUF、BFS クエリは次のようになります。

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

参照リンクに記載されているように、直行便がないため、結果はありません。しかし、 を 2 に増やすと(つまりとmaxPathLengthノードの間に 1 つの追加ノード)、多くのパスが見つかります (例: > >またはサンフランシスコからボストン、バッファロー)。SFOBUFSFOBOSBUF

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