使用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)

1. First we initiate all possible source destination pair keeping in mind that reverse of edge is not unique A-B, A-C, B-C (B-A, C-A, B-C is omitted)

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

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. 现在我们开始地图缩小算法

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. 减少

1. Reduce

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

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

因为我们仍然有一些带有注释的元组=继续

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. 减少

我们没有连续的元组，现在我们使用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的内部两个循环本质上是矩阵乘法，加法用min代替，乘法用加法代替.您可以使用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上的Wikipedia页面上:

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屋！