GraphX Advent Calendar - Day 13 - 指定階層内隣接頂点の検出 ~友達の友達の友達は誰？~

GraphX Advent Calendar 2014 - Adventar 13日目です。今日からは、昨日説明した Pregel を使った様々なアルゴリズムを見ていきたいと思います。

まずは、指定階層内の隣接頂点の検出についてです。つまり、友達の友達の友達は誰（３次階層以内の隣接頂点）？のようなものを判断するアルゴリズムです。

考え方

Pregel の処理は文章で説明するのはなかなか難しいです。今日もスライドで説明したいと思います。

GraphX Advent Calendar Day 13 from Teppei Tosa

実装

def sendMsgFunc(edge:EdgeTriplet[Int, Int]) = {
	if(edge.srcAttr <= 0){
		if(edge.dstAttr <= 0){
			// 両方とも0以下なら何も送信しない
			Iterator.empty
		}else{
			// 片方0以下で、片方0より大きいなら大きい方から1減算して送信する
			Iterator((edge.srcId, edge.dstAttr - 1))
		}
	}else{
		if(edge.dstAttr <= 0){
			// 片方0以下で、片方0より大きいなら大きい方から1減算して送信する
			Iterator((edge.dstId, edge.srcAttr - 1))
		}else{
			// 両方とも0より大きいなら、双方􏰁値を1減算して、双方に送信する
			val toSrc = Iterator((edge.srcId, edge.dstAttr - 1))
			val toDst = Iterator((edge.dstId, edge.srcAttr - 1))
			toDst ++ toSrc
		}
	}
}

val friends = Pregel(
	graph.mapVertices((vid, value)=> if(vid == 1) 2 else -1),

	// 最初􏰁イテレーションで送信するメッセージ
	-1,

	// 指定階層値􏰁回数イテレーションする
	2,

	// 双方向にメッセージ送信する
	EdgeDirection.Either
)(
	// 受信した値と自分􏰁値􏰁うち、大きい方を設定する
	vprog = (vid, attr, msg) => math.max(attr, msg),

	// イテレーション毎に辺上に何を流すか決定する処理(後述)
	sendMsgFunc,

	// 複数􏰁Edgeから値を受信したら大きい方をとる
	(a, b) => math.max(a, b)
)
// 頂点􏰁値が0以上􏰁頂点を抽出
.subgraph(vpred = (vid, v) => v >= 0)

次回予告

次回も Pregel を使った例を見ていきたいと思います。

今日のサンプルはこちらで確認できます。
graphx-advent-samples/Day13.scala at master · ironpeace/graphx-advent-samples · GitHub