получить упорядоченные узлы в компонентах направленной ациклической сетиx DiGraph

Question

У меня есть ориентированный граф с подграфами, где порядок узлов важен.

Пример мой график будет иметь два подграфа, все линейные 1-->2-->3 & 9-->8-->7-->6

Примечание: имена узлов будет случайным и уникальным, ни циклов в графах

NG = nx.DiGraph() 
NG.add_edges_from([(1,2),(2,3)]) 
NG.add_edges_from([(9,8),(8,7),(7,6)]) 

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

Я попытался

[i.nodes() for i in list(nx.weakly_connected_component_subgraphs(NG))] 

в результате список нодлистов, почти сразу, но не упорядочены в соответствии с их соединений:

[[1, 2, 3], [8, 9, 6, 7]] 

Как бы мне нужно продолжить, чтобы получить список заказывал нодлисты. i.e:

[[1, 2, 3], [9, 8, 7, 6]] 

Answer 1

Я предполагаю, что вы уверены, что это «Направленные ациклические графики».

Тогда nx.topological_sort(G) сортирует узлы в графе в соответствии с порядком, который вы хотите: то есть, если u появляется перед v, это означает, что нет пути от v к u (но, возможно, путь от u к v). Если вы используете nx.weakly_connected_component_subgraphs(G), вы получаете генератор для интересующих вас подграфов. Поэтому я рекомендую сначала найти подграфы, а затем отсортировать узлы.

[nx.topological_sort(H) for H in nx.weakly_connected_component_subgraphs(NG)] 

Должно получиться, что вы хотите.

---

Альтернативным более эффективный метод:

предыдущий код не будет наиболее эффективный код можно, но это очень просто. Создание каждого подграфа H требует времени, которого можно было бы избежать. Более эффективный метод будет делать weakly_connected_components(NG) (который генерирует списки узлов в каждом подграфе, а не сам подграф). Это создало бы списки, как вы уже. Затем вы выполните топологическую сортировку:

[nx.topological_sort(NG, nbunch=subgraph_nodes) for subgraph_nodes in nx.weakly_connected_components(NG)] 

Это будет более эффективно. Сначала он генерирует список узлов в каждом компоненте. Затем он проходит сортировку узлов в каждом компоненте. Если вы сделаете это, вы должны взглянуть на source for topological_sort. Он вернет отсортированный список всех узлов, доступных с любого узла, nbunch. В вашем случае это всего лишь nbunch, но в целом это не просто нужно вернуть nbunch.

---

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