Spark组件之GraphX学习16--最短路径ShortestPaths

更多代码请见：https://github.com/xubo245/SparkLearning

1解释

求图中的最短路径，更多的请见参考【3】，这篇写的很详细

2.代码：

/*** @author xubo* ref http://spark.apache.org/docs/1.5.2/graphx-programming-guide.html* time 20160503*/package org.apache.spark.graphx.learningimport org.apache.spark.SparkConf
import org.apache.spark.SparkContext
import org.apache.spark.graphx.Graph
import org.apache.spark.graphx.Graph.graphToGraphOps
import org.apache.spark.graphx.lib.ShortestPathsobject ShortPaths {def main(args: Array[String]): Unit = {val conf = new SparkConf().setAppName("ShortPaths").setMaster("local[4]")val sc = new SparkContext(conf)// 测试的真实结果，后面用于对比val shortestPaths = Set((1, Map(1 -> 0, 4 -> 2)), (2, Map(1 -> 1, 4 -> 2)), (3, Map(1 -> 2, 4 -> 1)),(4, Map(1 -> 2, 4 -> 0)), (5, Map(1 -> 1, 4 -> 1)), (6, Map(1 -> 3, 4 -> 1)))// 构造无向图的边序列val edgeSeq = Seq((1, 2), (1, 5), (2, 3), (2, 5), (3, 4), (4, 5), (4, 6)).flatMap {case e => Seq(e, e.swap)}// 构造无向图val edges = sc.parallelize(edgeSeq).map { case (v1, v2) => (v1.toLong, v2.toLong) }val graph = Graph.fromEdgeTuples(edges, 1)// 要求最短路径的点集合val landmarks = Seq(1, 4).map(_.toLong)// 计算最短路径val results = ShortestPaths.run(graph, landmarks).vertices.collect.map {case (v, spMap) => (v, spMap.mapValues(i => i))}val shortestPath1 = ShortestPaths.run(graph, landmarks)// 与真实结果对比println("\ngraph edges");println("edges:");graph.edges.collect.foreach(println)//    graph.edges.collect.foreach(println)println("vertices:");graph.vertices.collect.foreach(println)//    println("triplets:");//    graph.triplets.collect.foreach(println)println();println("\n shortestPath1");println("edges:");shortestPath1.edges.collect.foreach(println)println("vertices:");shortestPath1.vertices.collect.foreach(println)//    println("vertices:")assert(results.toSet == shortestPaths)println("results.toSet:" + results.toSet);println("end");sc.stop()}
}

3.结果：

分析：返回的是

(1,Map(1 -> 0, 4 -> 2))
(5,Map(1 -> 1, 4 -> 1))
(6,Map(4 -> 1, 1 -> 3))

(1,Map(1 -> 0, 4 -> 2))

表明的是1节点到1节点路径为0，到4节点为2

同理

(6,Map(4 -> 1, 1 -> 3))

全部结果：

graph edges
edges:
Edge(1,2,1)
Edge(1,5,1)
Edge(2,1,1)
Edge(2,3,1)
Edge(2,5,1)
Edge(3,2,1)
Edge(5,1,1)
Edge(3,4,1)
Edge(4,3,1)
Edge(5,2,1)
Edge(4,5,1)
Edge(4,6,1)
Edge(5,4,1)
Edge(6,4,1)
vertices:
(4,1)
(1,1)
(5,1)
(6,1)
(2,1)
(3,1)shortestPath1
edges:
Edge(1,2,1)
Edge(1,5,1)
Edge(2,1,1)
Edge(2,3,1)
Edge(2,5,1)
Edge(3,2,1)
Edge(5,1,1)
Edge(3,4,1)
Edge(4,3,1)
Edge(5,2,1)
Edge(4,5,1)
Edge(4,6,1)
Edge(5,4,1)
Edge(6,4,1)
vertices:
(4,Map(4 -> 0, 1 -> 2))
(1,Map(1 -> 0, 4 -> 2))
(5,Map(1 -> 1, 4 -> 1))
(6,Map(4 -> 1, 1 -> 3))
(2,Map(1 -> 1, 4 -> 2))
(3,Map(4 -> 1, 1 -> 2))
results.toSet:Set((1,Map(1 -> 0, 4 -> 2)), (5,Map(1 -> 1, 4 -> 1)), (2,Map(1 -> 1, 4 -> 2)), (6,Map(4 -> 1, 1 -> 3)), (4,Map(4 -> 0, 1 -> 2)), (3,Map(4 -> 1, 1 -> 2)))
end

如果改为全部节点，则为：

vertices:
(4,Map(5 -> 1, 1 -> 2, 6 -> 1, 2 -> 2, 3 -> 1, 4 -> 0))
(1,Map(5 -> 1, 1 -> 0, 6 -> 3, 2 -> 1, 3 -> 2, 4 -> 2))
(5,Map(5 -> 0, 1 -> 1, 6 -> 2, 2 -> 1, 3 -> 2, 4 -> 1))
(6,Map(5 -> 2, 1 -> 3, 6 -> 0, 2 -> 3, 3 -> 2, 4 -> 1))
(2,Map(5 -> 1, 1 -> 1, 6 -> 3, 2 -> 0, 3 -> 1, 4 -> 2))
(3,Map(5 -> 2, 1 -> 2, 6 -> 2, 2 -> 1, 3 -> 0, 4 -> 1))

results.toSet:Set((6,Map(5 -> 2, 1 -> 3, 6 -> 0, 2 -> 3, 3 -> 2, 4 -> 1)), (4,Map(5 -> 1, 1 -> 2, 6 -> 1, 2 -> 2, 3 -> 1, 4 -> 0)), (3,Map(5 -> 2, 1 -> 2, 6 -> 2, 2 -> 1, 3 -> 0, 4 -> 1)), (2,Map(5 -> 1, 1 -> 1, 6 -> 3, 2 -> 0, 3 -> 1, 4 -> 2)), (1,Map(5 -> 1, 1 -> 0, 6 -> 3, 2 -> 1, 3 -> 2, 4 -> 2)), (5,Map(5 -> 0, 1 -> 1, 6 -> 2, 2 -> 1, 3 -> 2, 4 -> 1)))

参考

【1】 http://spark.apache.org/docs/1.5.2/graphx-programming-guide.html

【2】https://github.com/xubo245/SparkLearning

【3】http://blog.csdn.net/zcf1002797280/article/details/50007913

本文来自互联网用户投稿，文章观点仅代表作者本人，不代表本站立场，不承担相关法律责任。如若转载，请注明出处。 如若内容造成侵权/违法违规/事实不符，请点击【内容举报】进行投诉反馈！