使用MapReduce在圖中找到距離爲2的節點對

Question

如何爲有向圖G =（V，E）編寫Mapper類和Reducer類。需要計算所有節點對（x，y），使得y可以在兩跳中從x到達，即存在使得（x，z）和（z，y）都在E中的節點z。這裏的x，y）可以是或可以不是在大腸桿菌

輸入應當與由製表符分隔的節點ID的邊緣，例如：

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

輸出應該節點對XY的列表通過長度精確爲2的路徑連接，例如每行一個：

1 3 
4 2 
... 

Answer 1

我假設「兩跳」意味着需要中間節點在兩個節點之間。例如，「z」是（x，y）對的中間節點。

你可以做的是讓節點ID成爲Mapper和Reducer中的關鍵。

通過這種方式，您將收集「z」所涉及的所有邊緣，並將其傳入您的Reducer中。

在縮減器中，您將添加將嘗試查找通過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