如何在Python中将匹配对聚合到"连接组件"中

Question

现实世界的问题:

我有许多公司的董事数据,但有时候"XYZ的董事John Smith"和"ABC的董事John Smith"是同一个人,有时他们不是.此外,"XYZ的导演约翰J.史密斯"和"ABC的导演约翰史密斯"可能是同一个人,也可能不是.通常检查附加信息(例如,关于"约翰史密斯,XYZ主任"和"约翰史密斯,ABC主任"的传记数据的比较)使得有可能解决两个观察是否是同一个人.

问题的概念版本:

本着这种精神,我正在收集识别匹配对的数据.例如,假设我有以下匹配对:{(a, b), (b, c), (c, d), (d, e), (f, g)}.我想使用关系"与人相同"的传递属性来生成"连通组件" {{a, b, c, d, e}, {f, g}}.那是{a, b, c, d, e}一个人,{f, g}是另一个人.(该问题的早期版本提到了"派系",这显然是别的东西;这可以解释为什么find_cliques在networkx给出"错误"结果(为了我的目的).

以下Python代码完成了这项工作.但我想知道:是否有更好的(计算成本更低)方法(例如,使用标准或可用的库)？

这里和那里似乎有相关的例子(例如,python中的Cliques),但这些是不完整的,所以我不确定他们指的是什么库或如何设置我的数据来使用它们.

示例Python 2代码:

def get_cliques(pairs):
    from sets import Set

    set_list = [Set(pairs[0])]

    for pair in pairs[1:]:
        matched=False
        for set in set_list:
            if pair[0] in set or pair[1] in set:
                set.update(pair)
                matched=True
                break
        if not matched:
            set_list.append(Set(pair))

    return set_list

pairs = [('a', 'b'), ('b', 'c'), ('c', 'd'), ('d', 'e'), ('f', 'g')]

print(get_cliques(pairs))

这产生了所需的输出:[Set(['a', 'c', 'b', 'e', 'd']), Set(['g', 'f'])].

示例Python 3代码:

这产生[set(['a', 'c', 'b', 'e', 'd']), set(['g', 'f'])]):

def get_cliques(pairs):

    set_list = [set(pairs[0])]

    for pair in pairs[1:]:
        matched=False
        for a_set in set_list:
            if pair[0] in a_set or pair[1] in a_set:
                a_set.update(pair)
                matched=True
                break
        if not matched:
            set_list.append(set(pair))

    return set_list

pairs = [('a', 'b'), ('b', 'c'), ('c', 'd'), ('d', 'e'), ('f', 'g')]

print(get_cliques(pairs))

Answer 1

使用networkX:

import networkx as nx
G1=nx.Graph()
G1.add_edges_from([("a","b"),("b","c"),("c","d"),("d","e"),("f","g")])
sorted(nx.connected_components(G1), key = len, reverse=True)

赠送:

[['a', 'd', 'e', 'b', 'c'], ['f', 'g']]

你现在必须检查最快的算法......

OP:

这很棒!我现在在PostgreSQL数据库中有这个.只需将对组织成一个两列表,然后用于array_agg()传递给PL/Python函数get_connected().谢谢.

CREATE OR REPLACE FUNCTION get_connected(
    lhs text[],
    rhs text[])
  RETURNS SETOF text[] AS
$BODY$
    pairs = zip(lhs, rhs)

    import networkx as nx
    G=nx.Graph()
    G.add_edges_from(pairs)
    return sorted(nx.connected_components(G), key = len, reverse=True)

$BODY$ LANGUAGE plpythonu;

(注意:我编辑了答案,因为我认为显示这一步可能是有用的附录,但对于评论来说太长了.)