Как собрать все цепочки с помощью python3

Question

Фон:

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

Что я пробовал:

Я использовал networkx.chain_decompostion для вычисления количествацепь.

import networkx as nx
info = nx.chain_decomposition(G)

Проблемы:

Я обнаружил, что найти только цепи с замкнутым контуром, такие как A1-A2-A3-A1.

Однако, естьдо сих пор многие цепочки не закрыты, например A1-A2-A3.

Есть ли простой способ собрать оба типа цепочек.Спасибо!

Answer 1

Функция chain_decomposition - это не то, что вы думаете.Из документов:

Цепная декомпозиция графа по дереву поиска в глубину представляет собой набор циклов или путей, полученных из набора фундаментальных циклов дерева [...]

Вероятно, вам нужна функция number_connected_components.Смотрите эту ссылку для деталей.Это предполагает, что каждый связанный компонент является цепочкой, то есть в вашем графе G есть несколько непересекающихся подграфов, каждый из которых соответствует (не разветвляющейся) молекуле полимера.Если это не так (полимер разветвлен), тогда вам нужно сделать что-то более умное.Например, вы можете вычислить все кратчайшие пути между оставленными узлами (атомы с одинарной связью).Вы можете найти узлы листа, проверив степень узлов с помощью list(G.degree) (листья имеют степень 1), а затем вычислить кратчайшие пути между всеми парами листьев с помощью all_shortest_paths.Чтобы найти циклические молекулы, вы можете использовать chain_decomposition, как и раньше.