MapReduceを使用してグラフ内の距離2のノードのペアを見つける

Question

有向グラフのMapperクラスとReducerクラスを書く方法G =（V、E）。 yが2つのホップでxから到達可能であるように、すなわち、（x、z）と（z、y）の両方がEであるようなノードzが存在するように、ノードのすべての対（x、y）

1 2 
0 1 
3 2 
2 3 
4 1 
... 

が

出力ノード対XYのリストであるべきである：x、y）は、または入力は、例えば、タブで区切られたノードIDとエッジ、であるべきであるE.

であってもなくてもよいです長さが正確に2のパスによって接続され、1行に1つずつ、例えば：

1 3 
4 2 
... 

Answer 1

I「は、2つのホップが」中間ノードが必要であることを意味すると仮定します2つのノード間。たとえば、 "z"は（x、y）対の中間ノードです。

あなたのできることはノードIDをマッパーとレデューサーのキーにすることです。

この方法で、 "z"があなたのレデューサーに渡される1つのコレクションに含まれるすべてのエッジを収集します。

還元剤では、zで接続されているすべての（x、y）ペアを検索するコードを追加します。

key: 1 - Edges (reducer values): (1, 2), (0, 1) => produces no pair 
key: 2 - Edges (reducer values): (1, 2), (3, 2), (2, 3) => produces (1, 3) as 2 in the middle 
key: 3 - Edges (reducer values): (3, 2), (2, 3), (1, 3) => produces no pair 

：あなたの例から

減速は、すべてのエッジのために取得します