Как объединить совпадающие пары в связанные компоненты в Python

С сетьюX:

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;

(Примечание: я отредактировал ответ, так как подумал, что показ этого шага может быть полезным дополнением, но слишком длинным для комментария.)

Я не верю (поправьте меня, если я ошибаюсь), что это напрямую связано с проблемой наибольшей клики. В определении клики (Википедия) говорится, что клика «в неориентированном графе — это подмножество его вершин, такое что каждые две вершины в подмножестве соединены ребром». В этом случае мы хотим найти, какие узлы могут связаться друг с другом (даже косвенно).

Я сделал небольшой образец. Он строит граф и обходит его в поисках соседей. Это должно быть довольно эффективно, поскольку каждый узел проходится только один раз при формировании групп.

from collections import defaultdict

def get_cliques(pairs):
    # Build a graph using the pairs
    nodes = defaultdict(lambda: [])
    for a, b in pairs:
        if b is not None:
            nodes[a].append((b, nodes[b]))
            nodes[b].append((a, nodes[a]))
        else:
            nodes[a]  # empty list

    # Add all neighbors to the same group    
    visited = set()
    def _build_group(key, group):
        if key in visited:
            return
        visited.add(key)
        group.add(key)
        for key, _ in nodes[key]:
            _build_group(key, group)

    groups = []
    for key in nodes.keys():
        if key in visited: continue
        groups.append(set())
        _build_group(key, groups[-1])

    return groups

if __name__ == '__main__':
    pairs = [
        ('a', 'b'), ('b', 'c'), ('b', 'd'), # a "tree"
        ('f', None),                        # no relations
        ('h', 'i'), ('i', 'j'), ('j', 'h')  # circular
    ]
    print get_cliques(pairs)
    # Output: [set(['a', 'c', 'b', 'd']), set(['f']), set(['i', 'h', 'j'])]

Если ваш набор данных лучше всего смоделировать как график и он действительно большой, возможно, вам подойдет база данных графов, такая как Neo4j?

Комментарий DSM заставил меня искать алгоритмы консолидации наборов в Python. Rosetta Code имеет две версии одного и того же алгоритма. Пример использования (нерекурсивная версия):

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

# Copied from Rosetta Code
def consolidate(sets):
    setlist = [s for s in sets if s]
    for i, s1 in enumerate(setlist):
        if s1:
            for s2 in setlist[i+1:]:
                intersection = s1.intersection(s2)
                if intersection:
                    s2.update(s1)
                    s1.clear()
                    s1 = s2
    return [s for s in setlist if s]

print consolidate([set(pair) for pair in pairs])
# Output: [set(['a', 'c', 'b', 'd']), set([None, 'f']), set(['i', 'h', 'j'])]

Я попробовал альтернативную реализацию, используя словари в качестве поиска, и, возможно, получил небольшое сокращение вычислительной задержки.

# Modified to use a dictionary
from collections import defaultdict

def get_cliques2(pairs):
  maxClique = 1
  clique = defaultdict(int)
  for (a, b) in pairs:
    currentClique = max(clique[i] for i in (a,b))
    if currentClique == 0:
      currentClique = maxClique
      maxClique += 1
    clique[a] = clique[b] = currentClique
  reversed = defaultdict(list)
  for (k, v) in clique.iteritems(): reversed[v].append(k)
  return reversed

И просто чтобы убедить себя, что он возвращает правильный результат (get_cliques1 вот ваше исходное решение Python 2):

>>> from cliques import *
>>> get_cliques1(pairs) # Original Python 2 solution
[Set(['a', 'c', 'b', 'e', 'd']), Set(['g', 'f'])]
>>> get_cliques2(pairs) # Dictionary-based alternative
[['a', 'c', 'b', 'e', 'd'], ['g', 'f']]

Информация о времени в секундах (с 10 миллионами повторений):

$ python get_times.py 
get_cliques: 75.1285209656
get_cliques2: 69.9816100597

Для полноты и справки, это полный список как cliques.py, так и сценария синхронизации get_times.py:

# cliques.py
# Python 2.7
from collections import defaultdict
from sets import Set  # I moved your import out of the function to try to get closer to apples-apples

# Original Python 2 solution
def get_cliques1(pairs):

    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

# Modified to use a dictionary
def get_cliques2(pairs):
  maxClique = 1
  clique = defaultdict(int)
  for (a, b) in pairs:
    currentClique = max(clique[i] for i in (a,b))
    if currentClique == 0:
      currentClique = maxClique
      maxClique += 1
    clique[a] = clique[b] = currentClique
  reversed = defaultdict(list)
  for (k, v) in clique.iteritems(): reversed[v].append(k)
  return reversed.values()

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


# get_times.py
# Python 2.7
from timeit import timeit

REPS = 10000000

print "get_cliques: " + str(timeit(
  stmt='get_cliques1(pairs)', setup='from cliques import get_cliques1, pairs',
  number=REPS
))
print "get_cliques2: " + str(timeit(
  stmt='get_cliques2(pairs)', setup='from cliques import get_cliques2, pairs',
  number=REPS
))

Так что, по крайней мере, в этом надуманном сценарии есть измеримое ускорение. Это, по общему признанию, не является новаторским, и я уверен, что я оставил некоторые биты производительности на столе в своей реализации, но, возможно, это поможет вам подумать о других альтернативах?