使用 map reduce 遍历带有 bfs 的图的有效方法是什么? [英] What is an efficient way of traversing a graph with bfs using map reduce?

问题描述

这是一个招聘人员问我的面试问题，问题基本上是计算所有节点到每个节点的最短路径，我的解决方案如下

This was an interview question I got asked by a recruiter, the problem is basically to calculate the shortest path of all node to every node, and my solution was the following

启动所有可能的边(没有反向 A - B 与 B-A 相同)

initiate all possible edges (without reverse A - B is the same as B-A)

每个节点将在下面表示 (src, cost, current_list, dest) ，src 和 dest 基本上是我们之前启动的所有可能的边

Each node will be represent in the following (src, cost, current_list, dest) , the src and dest is basically all the possible edges we initiate earlier

地图:

for each edge you traverse, you duplicate your tuple and add the current   
traversed node to the cost and current list. 
if the node is the destination you annotate finish, if the the node is 
in the current list, you annotate delete

减少:

Don't really need to do anything besides outputting finish and deleting 
delete and let the other node go through the next round of map
And by outputting I mean for each src, dest pair only output the least cost

招聘人员说这效率不高，我可以看到这效率不高，因为您正在组合遍历，但我能想到的唯一选择是如果您有 n 个节点，然后生成 n 个服务器并为每个节点执行 dijkstra招聘人员说的也是错误的.有人可以帮我解决这个问题吗?

The recruiter say this is not efficient, I can see how this is not efficient since you are traversing combinatorialy, but the only alternative I can think of is if you have n node, then spawn n servers and do dijkstra for each node which the recruiter say is also wrong. Can someone give me some help on this problem?

例如.三角图

边是 A-B、B-C、C-A，路径成本为 1

The edges are A-B, B-C, C-A with path cost of 1

算法

1. 首先，我们启动所有可能的源目标对，记住边缘的反转不是唯一的A-B、A-C、B-C(省略B-A、C-A、B-C)

对于每个源目标对，我们有以下元组

for each source destination pair we have the following tuple

(src=A, cost=None, current_list=A, dest=B, annotate=continue)
(src=A, cost=None, current_list=A, dest=C, annotate=continue)
(src=B, cost=None, current_list=B, dest=C, annotate=continue)

1. 现在我们开始 map reduce 算法

1. Now we start the map reduce algorithm

for each tuple in the tuple list we initiate:

    for each neighbor of the node at the end of current_list
        if the next neighbor is already in the current_list
            set annotate = delete
        elif the next neighbor is the dest
            set annotate = finish
            add path cost to cost
        else
            duplicate the current node
            add neighbor to current_list
            add path cost to cost
        delete the current tuple

在我们的例子中

(src=A, cost=None, current_list=A, dest=B, annotate=continue)
 =>
(src=A, cost=1, current_list=AB, dest=B, annotate=finish)
(src=A, cost=1, current_list=AC, dest=B, annotate=continue)

(src=A, cost=None, current_list=A, dest=C, annotate=continue)
=>
(src=A, cost=1, current_list=AC, dest=C, annotate=finish)
(src=A, cost=1, current_list=AB, dest=C, annotate=continue)

(src=B, cost=None, current_list=B, dest=C, annotate=continue)
=>
(src=B, cost=1, current_list=BC, dest=C, annotate=finish)
(src=B, cost=1, current_list=BA, dest=C, annotate=continue)

1. 减少

注意:我们减少了 src、dest 对，并将其用作我们的 key对于元组列表中的每个元组

Note: we reduce on src, dest pair, and use it as our key for every tuple in tuple list

if annotate == finish
    keep trace of min cost and delete tuple for each src dest pair that is not the current min
    then pass the current min as result
elif annotate == delete
    delete the tuple

else
    pass down to the next round of map

地图

Map

因为我们还有一些元组有 annotate = continue

Since we still have some tuple that have annotate = continue

(src=B, cost=1, current_list=BA, dest=C, annotate=continue)  
=>
(src=B, cost=2, current_list=BAC, dest=C, annotate=finish)  
(src=B, cost=2, current_list=BAB, dest=C, annotate=delete)  


(src=A, cost=1, current_list=AC, dest=B, annotate=continue)
=>
(src=A, cost=2, current_list=ACB, dest=B, annotate=finish)
(src=A, cost=2, current_list=ACA, dest=B, annotate=delete)

(src=A, cost=1, current_list=AB, dest=C, annotate=continue)
=>
(src=A, cost=2, current_list=ABC, dest=C, annotate=finish)
(src=A, cost=2, current_list=ABA, dest=C, annotate=delete)

1. 减少

我们没有 continue 元组，现在我们只使用 reduce 来找到每个 src dest 对的最小值

We have no continue tuples, now we just use the reduce to find the min for each src dest pair

推荐答案

Floyd-Warshall 的内部两个循环本质上是矩阵乘法，加法替换为最小值，乘法替换为加法.您可以使用 map-reduce 进行矩阵乘法，因此您可以使用 |V| 实现 Floyd Warshall地图减少.

The inner two loops of Floyd-Warshall are essentially matrix multiplication with addition replaced by min and multiplication replaced by addition. You can do matrix multiplication with a map-reduce, so you can implement Floyd Warshall with |V| map-reduces.

来自 Floyd-Warshall 的维基百科页面:

From the wikipedia page on Floyd-Warshall:

1 let dist be a |V| × |V| array of minimum distances initialized to ∞ (infinity)
2 for each vertex v
3    dist[v][v] ← 0
4 for each edge (u,v)
5    dist[u][v] ← w(u,v)  // the weight of the edge (u,v)
6 for k from 1 to |V|
7    for i from 1 to |V|
8       for j from 1 to |V|
9          if dist[i][j] > dist[i][k] + dist[k][j] 
10             dist[i][j] ← dist[i][k] + dist[k][j]
11         end if

内部的两个循环(i 和 j，第 7 到 11 行)在结构上与矩阵乘法相同，您可以在 map-reduce"解决方案来执行此操作.

The inner two loops (i and j, lines 7 to 11) are structurally the same as matrix multiplication, and you can adapt any "matrix multiplication on map-reduce" solution to perform this.

外部 (k) 循环变为 |V|地图减少.

The outer (k) loop becomes |V| map-reduces.

这篇关于使用 map reduce 遍历带有 bfs 的图的有效方法是什么?的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！