Spark Scala GraphX:两个顶点之间的最短路径 [英] Spark Scala GraphX: Shortest path between two vertices
问题描述
我在Spark GraphX(Scala)中有向图G.我想找到从已知顶点v1
开始要到达另一个顶点v2
的应该交叉的边数.换句话说,我需要从顶点v1
到顶点v2
的最短路径,该路径以边的数量计算(不使用边的权重).
我正在查看 GraphX文档,但我无法找到一种方法来做到这一点.如果它具有树形结构,则为了计算图的深度也需要这样做.他们是这样做的简单方法吗?
要使用Spark GraphX查找顶点之间的最短路径,请使用 org.apache.spark.graphx.lib .>
假设您在g
中有一个GraphX图形,并且想要找到ID为v1
和v2
的顶点之间的最短路径,可以执行以下操作:
import org.apache.spark.graphx._
import org.apache.spark.graphx.lib.ShortestPaths
val result = ShortestPaths.run(g, Seq(v2))
val shortestPath = result // result is a graph
.vertices // we get the vertices RDD
.filter({case(vId, _) => vId == v1}) // we filter to get only the shortest path from v1
.first // there's only one value
._2 // the result is a tuple (v1, Map)
.get(v2) // we get its shortest path to v2 as an Option object
ShortestPaths GraphX算法返回一个图形,其中顶点RDD包含格式为(vertexId, Map(target -> shortestPath)
的元组.该图将包含原始图的所有顶点,以及它们到算法的Seq
参数中传递的所有目标顶点的最短路径.
在您的情况下,您想要两个特定顶点之间的最短路径,因此在上面的代码中,我演示了如何仅使用一个目标(v2
)调用该算法,然后对结果进行过滤以仅获得最短的顶点从所需顶点(v1
)开始的路径.
I have a directed graph G in Spark GraphX (Scala). I would like to find the number of edges that should be crossed starting from a known vertex v1
to arrive in another vertex v2
. In other words, I need the shortest path from the vertex v1
to the vertex v2
calculated in number of edges (not using the edges' weights).
I was looking at the GraphX documentation, but I wasn't able to find a method to do it. This is also needed in order to compute the depth of the graph if it has a tree structure. Is their an easy way to do this?
To find the shortest path between vertices using Spark GraphX, there is the ShortestPaths object, which is member of the org.apache.spark.graphx.lib.
Assuming you have a GraphX graph in g
and you want to find the shortest path between the vertices with ids v1
and v2
, you can do the following:
import org.apache.spark.graphx._
import org.apache.spark.graphx.lib.ShortestPaths
val result = ShortestPaths.run(g, Seq(v2))
val shortestPath = result // result is a graph
.vertices // we get the vertices RDD
.filter({case(vId, _) => vId == v1}) // we filter to get only the shortest path from v1
.first // there's only one value
._2 // the result is a tuple (v1, Map)
.get(v2) // we get its shortest path to v2 as an Option object
The ShortestPaths GraphX algorithm returns a graph where the vertices RDD contains tuples in the format (vertexId, Map(target -> shortestPath)
. This graph will contain all vertices of the original graph, and their shortest paths to all target vertices passed in the Seq
argument of the algorithm.
In your case, you want the shortest path between two specific vertices, so in the code above I show how to call the algorithm with only one target (v2
), and then I filter the result to get only the shortest path starting from the desired vertex (v1
).
这篇关于Spark Scala GraphX:两个顶点之间的最短路径的文章就介绍到这了,希望我们推荐的答案对大家有所帮助,也希望大家多多支持IT屋!