GraphX Advent Calendar - Day 14 - グラフ形状の評価 ~友達の輪を探せ~

GraphX Advent Calendar 2014 - Adventar 14日目です。 Pregel 活用例第２弾です。

友達関係のグラフから、「友達の輪」つまり、ネットワークの流れが循環しているところを抽出する処理です。今回は指定ステップ以内で循環している頂点を探します。

考え方

今日もスライドで解説です。

GraphX Advent Calendar Day 14 from Teppei Tosa

実装

val circleGraph = Pregel(
	// 各頂点に空􏰁リストをセットしたグラフを処理する
	graph.mapVertices((id, attr) => Set[VertexId]()),
	// 最初に辺を流すメッセージ：空グラフ
	Set[VertexId](),
	// 4階層以内で還流しているところを探す
	4,
	// メッセージを送る方向
	EdgeDirection.Out) (
		// 自分􏰁リストと、渡って来たリストを合体させる
		(id, attr, msg) => (msg ++ attr),
		// Srcが持っているリストにSrc􏰁IDを追加してDstに渡す
		edge => Iterator((edge.dstId, (edge.srcAttr + edge.srcId))),
		// 複数Srcから送られて来たリストを合体させる
		(a, b) => (a ++ b)
	// リストに自分􏰁IDが入っている頂点が「輪」􏰁中にいる頂点
	).subgraph(vpred = (id, attr) => attr.contains(id))

次回予告

まだまだ Pregel 活用例続きますよ〜

今日のサンプルソースはこちらです。

graphx-advent-samples/Day14.scala at master · ironpeace/graphx-advent-samples · GitHub