路径分析

场景介绍

路径分析一般找寻最短路径或枚举所有环路。寻找最短路径，主要特点是以起始点为中心向外层层扩展，直到扩展到终点为止；找寻所有环路，在现实网络中，无约束的环很多，同时很大一部分环路信息是无用的，通过指定的约束条件，如环路长度约束、环路中边权重的约束，求解对应的环路信息。

算法原理

MSSP算法
 MSSP（Multiple Sources Shortest Path，多源最短路径）算法，是最短路径领域的基础算法，是指给定图数据集和指定部分结点，计算图中所有结点到给定结点的最短路径距离。
CD算法
 CD（Cycle Detection，环路检测）算法是图分析领域的基础算法，通常是在有向图中枚举出满足需求的所有环路。而在现实网络中，无约束的环很多，同时很大一部分环路信息是无用的，所以在本算法中，通过指定的约束条件，如环路长度约束、环路中边权重的约束，求解对应的环路信息。
BFS算法
 BFS（Breadth-First-Search，广度优先搜索）算法，是图分析领域的基础算法，通过广度优先的方式对图进行搜索遍历直到达到最大搜索深度或访问完所有可达结点。

编程实例

本示例以BFS算法来介绍编程示例。

run API

API

def run[VD: ClassTag, ED: ClassTag](graph: Graph[VD, ED],sourceID: Long,isDirected: Boolean,depthLimit: Int): Graph[(Int, Array[Long]), ED]

功能描述
 对于给定源点，最大搜索深度，以广度优先搜索的方式对无权图进行搜索，直到达到最大搜索深度或访问完所有可达结点，记录结点位于的层数和邻居信息。

BFS算法时序图如图1所示。

图1 BFS算法时序图

API描述

包名：package org.apache.spark.graphx.lib
类名：BFS
方法名：run
输入：Graph[VD, ED]，无权图。

参数详情：

参数名称	取值类型	描述
graph	Graph[VD, ED]，VD表示结点属性，ED表示边属性	有向图或无向图
sourceID	Long型如5907828等，正整数	源结点ID
isDirected	true或false，boolean类型，true表示有向图	图类型，有向/无向图
depthLimit	Int型，系统当前最大为10，如8等，正整数	最大搜索深度

核心参数：
1. sourceID：源结点
2. isDirected：是否为有向图
3. depthLimit：最大搜索深度
输出：Graph[(Int, Array[Long]), ED]: 输出一个Graph，结点属性信息为(结点位于的层数，结点的邻居)。

使用样例

使用BFS有向图样例：

val conf = new SparkConf().setAppName("bfs").setMaster(host)
val sc = new SparkContext(conf)
val input = sc.parallelize(Array((1, 2), (1, 3), (2, 4), (2, 5), (3, 6), (3, 7)))
   .map(f => Edge(f._1.toLong, f._2.toLong, 0))
val graph = Graph.fromEdges[Int, Int](input, 0) 
val sourceID = 1L 
val isDirected = true 
val depthLimit = 10  
val res = BFS.run(graph, sourceID, isDirected, depthLimit)

BFS无向图样例：

val conf = new SparkConf().setAppName("bfs").setMaster(host)
val sc = new SparkContext(conf)
val input = sc.parallelize(Array((1, 2), (1, 3), (2, 3), (2, 4), (2, 5)))
   .map(f => Edge(f._1.toLong, f._2.toLong, 0))
val graph = Graph.fromEdges[Int, Int](input, 0) 
val sourceID = 1L 
val isDirected = false 
val depthLimit = 10  
val res = BFS.run(graph, sourceID, isDirected, depthLimit)

样例结果
- 有向图样例结果
```
1;2,3
2;4,5
3;6,7
4;;2
5;;2
6;;2
7;;2
```
- 无向图样例结果
```
1;2,3;0
2;1,3,4,5;1
3;1,2;1
4;2;2
5;2;2
```
结果以分号为分隔符，第一列为结点ID，第二列为该结点的邻居，第三列为该结点的深度信息（未遍历到的为Int.MaxValue）。

父主题： 图分析算法