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

Question

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

设计一个 MapReduce 算法，将一个表示为弧列表的有向图作为输入，列出所有节点对 (x, y)，使得存在三个弧 (x, a)、(a, b) 和(经过)。 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

对于 map 后面的示例，我们将有以下内容:

• (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 语法方面的专家，但我相信应该有一种方法可以实现它。