Есть ли более элегантный / оптимизированный способ сделать этот алгоритм подключения?

Question

Я создал алгоритм, который определяет, какие атомы связаны в молекуле из списка атомов (учитывая их расстояние друг от друга).Чтобы думать об этой проблеме вне физического контекста, это просто проблема замкнутой сети, в которой узлы - это атомы, а ребра - это атомные связи, соединяющие атомы.У меня есть список узлов и список ребер, которые соединяют узлы, и мне нужно выяснить список каждой уникальной молекулы.Я сделал это в коде ниже, однако это довольно медленно и довольно некрасиво.Есть ли способ оптимизировать этот алгоритм?

Вот мой код, который работает, с соответствующей информацией для вас, чтобы попробовать его (я предоставлю другой список атомов, чтобы попытаться назвать пары _1 и selected_atom_1, просто измените пары pair_1 на парыи selected_atom_1 to selected_atom, чтобы он работал, конечно)

pairs = [[0, 1],
 [0, 2],
 [3, 4],
 [3, 5],
 [6, 7],
 [6, 8],
 [9, 10],
 [9, 11],
 [12, 13],
 [12, 14],
 [15, 16],
 [15, 17],
 [18, 19],
 [18, 20],
 [21, 22],
 [21, 23],
 [24, 25],
 [24, 26],
 [27, 28],
 [27, 29],
 [30, 31],
 [30, 32],
 [33, 34],
 [33, 35],
 [36, 37],
 [36, 38],
 [39, 40],
 [39, 41],
 [42, 43],
 [42, 44],
 [45, 46],
 [45, 47]]

chosen_atom = [np.random.rand() for i in range(48)]

pairs_1 = [[0, 6],
 [1, 7],
 [2, 8],
 [3, 9],
 [4, 10],
 [5, 6],
 [5, 10],
 [6, 7],
 [7, 8],
 [8, 9],
 [9, 10]]

chosen_atom_1 = [np.random.rand() for i in range(11)]

# use list of lists to define unique molecules
molecule_list = []

for i in pairs:
    temp_array = []
    for ii in pairs:
        temp_pair = [i[0], i[1]]

        if temp_pair[0] == ii[0]:
            temp_array.append(ii[1])
            temp_array = set(temp_array)
            temp_array = list(temp_array)
        if temp_pair[1] == ii[1]:
            temp_array.append(ii[0])
            temp_array = set(temp_array)
            temp_array = list(temp_array)

        for iii in temp_array:
            for j in pairs:
                if iii == j[0]:
                    temp_array.append(j[1])
                    temp_array = set(temp_array)
                    temp_array = list(temp_array)
                if iii == j[1]:
                    temp_array.append(j[0])
                    temp_array = set(temp_array)
                    temp_array = list(temp_array)

        if len(temp_array) > len(chosen_atom):
            break
    molecule_list.append(temp_array)

molecule_list = [list(item) for item in set(tuple(row) for row in molecule_list)]

# the output of pairs should be
molecule_list = [[8, 6, 7],
 [27, 28, 29],
 [9, 10, 11],
 [0, 1, 2],
 [32, 30, 31],
 [18, 19, 20],
 [45, 46, 47],
 [33, 34, 35],
 [24, 25, 26],
 [42, 43, 44],
 [16, 17, 15],
 [12, 13, 14],
 [21, 22, 23],
 [3, 4, 5],
 [40, 41, 39],
 [36, 37, 38]]
# the output of pairs_1 should be:
molecule_list = [[0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10]]

Итак, выше я привел результаты, которые я получаю сейчас и должен получить - любые идеи по улучшению этого кода будут высоко оценены.

Answer 1

Как я уже говорил в комментариях, вам нужен алгоритм подключенных компонентов, и вы можете легко решить его с помощью пакета networkx:

import networkx as nx

G = nx.from_edgelist(pairs)

print([i for i in nx.connected_components(G)])

# jupyter notebook
%matplotlib inline
nx.draw(G, with_labels=True)

Вывод:

[{0, 1, 2}, {3, 4, 5}, {8, 6, 7}, {9, 10, 11}, {12, 13, 14}, {16, 17, 15}, {18, 19, 20}, {21, 22, 23}, {24, 25, 26}, {27, 28, 29}, {32, 30, 31}, {33, 34, 35}, {36, 37, 38}, {40, 41, 39}, {42, 43, 44}, {45, 46, 47}]

Вот мой скрипт для построения и визуализации молекулярного графа из атомных координат.

Answer 2

Эту проблему можно решить с помощью метода "union-find".

Свяжите каждый атом со связью с другим атомом в той же молекуле.Ссылка может быть недействительной.Если нет, то это приводит к другому атому, который сам имеет связь.Перейдя по ссылкам рекурсивно, вы в конце концов достигнете атома с пустой ссылкой.Назовем его основным атомом в молекуле.

Алгоритм работает следующим образом:

• по очереди каждое ребро, пусть ab;

• найдите главный атом a, пусть main (a);

• связывает main (a) с b, чтобы перегруппировать их вта же молекула. ​​

При этом основной (а) становится таким же, как основной (б), и в конце концов все атомы данной молекулы имеют один и тот же основной.

После этого первого прохода вы можете выполнить проход по атомам, чтобы перечислить сети, которые соответствуют различным молекулам.

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

---

Варианты и оптимизации:

• вместо того, чтобы связать main (a) с b, вы можете связатьэто к основному (b);

• пока вы ищете основной (а), вы можете связать все атомы с основным (а) на пути;это сокращает пути для будущих поисков;

• , если вы также сохраните длину пути от a до main (a), вы можете предпочесть присоединить main (a) к main (b).) или от основного (b) к основному (а);

• вместо того, чтобы дать основному атому ссылку в void, вы можете разрешить ему ссылаться на себя.