-1

嗨，伙计们，我必须在 python 中使用必须在 hadoop 上运行的 map reduce 范例编写一个算法：

让我们假设给定一个有向图 G = (V,E)，一条边 (v,u) ∈ E 意味着 v 正在跟随 u，或者 v 已经声明 u 是他的朋友，因此 u 有可能影响 v （但不一定反过来）。现在，给定一个网络 G = (V,E) 和一个节点 v ∈ V，我们想要找到所有节点 u，使得从 v 到 u 的路径最长为 3。 为 Hadoop 设计并实现一个算法找到所有这样的节点。假设输入文件给出每个节点的邻接表，即它们的形式为 v:u1 ,u2 ,u3 。. . 其中 v 是一个节点，每个 ui 对应于边 (v,ui )。

我不知道如何实现 map 和 reduce 任务。

4

1 回答 1

0

我会推荐https://github.com/Yelp/mrjob

mrjob 负责打包您的代码并处理流 API。你只需要编写一个 map 和 reduce 函数。它还支持多步骤作业，如果您需要多次 map-reduce。

对于您描述的问题，我认为您可以编写一个多步骤作业来解决该问题。您可以将 V 作为参数传递给作业。

  • 地图 1 - 对于每条边 (a,b) 产生 (a, (a,b)) 和 (b, (a, b)
  • 减少 1 - 您将获得一个边列表，其中一些以 a 开头，一些以 a 结尾。同时产生 (a, [(a, c)]) 和 (a, [(b, a), (a, c)]

您现在拥有长度为 1 和 2 的所有路径。在另一个步骤中重复以获取长度为 1 到 3 的所有路径。您的最终归约可以丢弃不以 v 开头的任何内容，并返回所有路径 (v, ui)

于 2013-04-06T18:30:30.820 回答