各位，我必须用python编写一个算法，使用map reduce范例，必须在hadoop上运行：
假设给定一个有向图g=（v，e），一条边（v，u）∈ e意味着v跟随着u，或者v已经宣布u是他的朋友，因此u有可能影响v（但不一定相反）。现在，给定一个网络g=（v，e）和一个节点v∈ 我们要找到所有的节点u，使得从v到u的路径长度不超过3。为hadoop设计并实现了一个查找所有节点的算法。假设输入文件给出了每个节点的邻接列表，也就是说，它们的格式是v:u1，u2，u3。其中v是一个节点，每个ui对应于边（v，ui）。
我不知道如何实现map和减少任务。
1条答案
按热度按时间ntjbwcob1#
我建议你https://github.com/yelp/mrjob
mrjob负责打包代码和处理流式api。你只需要写一个Map和归约函数。它还支持多步骤作业，如果您需要多次Mapreduce。
对于您描述的问题，我认为您可以编写一个多步骤的作业来解决问题。将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的所有路径。您的最终reduce可以丢弃任何不以v开头的内容，并返回所有路径（v，ui）