有向图中的 MapReduce 长度为 3 条路径

Question

我正在尝试解决一个练习，但我仍然没有找到解决方案。

设计一个 MapReduce 算法，将一个表示为弧列表的有向图作为输入，列出所有节点对 (x, y)，从而存在三个弧 (x, a), (a, b ) 和 (b, y)。 reducer 接收到的值列表的长度永远不应超过图中节点的数量。请提供伪代码。

这么久我通过以下方式找到了长度为2的路径：

map (k, v): 
   write (k, (v, "out"))
   write (v, (k, "in"))

reduce(k ,list(v)):
   // write all pairs of nodes such that one has an arc exiting and the other has an arc entering

但从这里开始我无法理解如何找到长度为 3 的路径，满足列表长度上的属性。

Answer 1

我不是 hadoop 语法方面的专家，但让我们从理论上解决这个问题。

考虑 G=(V,E) - ARCS 是我们的 E 包含诸如 (x,a)、(a,b)、(b,y) 等元素

您找到了一种方法来提取距离为 2 的所有节点。我们称此集合为 2-LEN。在您的简短示例中，它将包含 (x,b) 和 (a,y)。

让我们创建这样定义的新集合（伪代码）：

NEW_SET = new set
for each ((x,y) in ARCS)
     NEW_SET.add(x,y,1)
for each ((x,y) in 2-LEN)
     NEW_SET.add(x,y,2)

第三个参数你大概理解为距离。所以现在，对于您的示例 NEW_SET 将包含：(x,a,1), (a,b,1), (b,y,1), (x,b,2), (a,y ,2).

现在在您的 2 距离算法中使用相同的逻辑 - mapreduce NEW_SET 具有：

map(k,v,d):
   write (k, (v, "out", d))
   write (v, (k, "in" , d))

reduce(k , list (v)):
   //write all pairs of nodes such that one has an 'in' and the other has an 'out' AND have different d

对于地图后面的示例，我们将有以下内容：

(x, (a,out,1))
(a, (x,in,1))
(a, (b,out,1))
(b, (a,in,1))
(b, (y,out,1))
(y, (b,in,1))
(x, (b,out,2))
(b, (x,in,2))
(a, (y,out,2))
(y, (a,in,2))

所以现在你将 2 个距离节点与 1 个距离节点连接起来，导致所有对的距离为 3。

请注意，您将需要对该集合执行 uniq，因为您将获得 (x,y) 两次 - 一次来自 ((x,a),(a,y)) 一次来自 ((x,b ),(b,y))

正如我提到的，我不是 hadoop 语法方面的专家，但我相信应该有一种方法可以实现它。

有向图中的 MapReduce 长度为 3 条路径

MapReduce length 3 paths in directed graph

hadoop

mapreduce

graph