apache-pig - 从一组关系中找到最长为 2 的所有路径

Question

我有一个连接数据集，每行标记A都B以A B. A和之间的直接联系B只出现一次，形式为A B或B A。我想找到最多一跳的所有连接，即A并且C最多一跳，如果A和C是直接连接的，或者通过一些A连接。CB

比如我有如下直连数据

1 2
2 4
3 7
4 5

然后我想要的结果数据是

1 {2,4}
2 {1,4,5}
3 {7}
4 {1,2,5}
5 {2,4}
7 {3}

有人可以帮我找到一种尽可能高效的方法吗？谢谢你。

Answer 1

你可以这样做：

myudf.py

@outputSchema('bagofnums: {(num:int)}')
def merge_distinct(b1, b2):
    out = []
    for ignore, n in b1:
        out.append(n)
    for ignore, n in b2:
        out.append(n)

    return out

脚本.pig

register 'myudf.py' using jython as myudf ;

A = LOAD 'foo.in' USING PigStorage(' ') AS (num: int, link: int) ; 

-- Essentially flips A
B = FOREACH A GENERATE link AS num, num AS link ;

-- We need to union the flipped A with A so that we will know:
-- 3 links to 7
-- 7 links to 3
-- Instead of just:
-- 3 links to 7
C = UNION A, B ;
-- C is in the form (num, link)

-- You can't do JOIN C BY link, C BY num ; 
-- So, T just is C replicated
T = FOREACH D GENERATE * ;
D = JOIN C BY link, T BY num ; 
E = FOREACH (FILTER E BY $0 != $3) GENERATE $0 AS num, $3 AS link_hopped ;
-- The output from E are (num, link) pairs where the link is one hop away. EG
-- 1 links to 2
-- 2 links to 4
-- 3 links to 7
-- The output will be:
-- 1 links to 4

F = COGROUP C BY num, E BY num ;
-- I use a UDF here to merge the bags together. Otherwise you will end
-- up with a bag for C (direct links) and E (links one hop away).
G = FOREACH F GENERATE group AS num, myudf.merge_distinct(C, E) ;

G使用示例输入的架构和输出：

G: {num: int,bagofnums: {(num: int)}}
(1,{(2),(4)})
(2,{(4),(1),(5)})
(3,{(7)})
(4,{(5),(2),(1)})
(5,{(4),(2)})
(7,{(3)})