如何在Python中将匹配对聚合为“连接的组件”

Question

实际问题：

我有许多公司的董事数据，但有时“ XYZ董事约翰·史密斯”和“ ABC董事约翰·史密斯”是同一个人，有时却不是。另外，“
XYZ董事约翰·史密斯”和“美国广播公司董事约翰·史密斯”可能是同一个人，也可能不是同一个人。通常，检查附加信息（例如，比较“ 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}是另一个人。（该问题的较早版本称为“
clique”，这显然是另外一回事；这可以解释为什么find_cliquesinnetworkx给出“错误”结果（出于我的目的）。

以下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;

（注意：我编辑了答案，因为我认为显示此步骤可能对附录有帮助，但评论太久了。）