Реальная проблема:

У меня есть данные о директорах во многих фирмах, но иногда «Джон Смит, директор XYZ» и «Джон Смит, директор ABC» - это одно и то же лицо, иногда это не так. Также «Джон Дж. Смит, директор XYZ» и «Джон Смит, директор 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 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))