Имея networkx
DiGraph
со следующей структурой: Я пытаюсь найти способ пройти по ориентированному графу из крайних левых узлов (без каких-либо входящих ребер), представляя
data sources
из промежуточных узлов (имеющих входящие и исходящие края), представляющие operators
преобразование данных в крайние правые края (имеющие только входящие края), представляющие data destinations
. Я могу разделить исходный граф на набор изолированных подграфов (в красных рамках):
subgraphs = weakly_connected_components(g)
Но затем мне нужно найти способ пройтись по каждому из подграфов, как описано выше. Проблема в том, что у меня есть разные типы графов: 1 - обратное дерево 2 - прямая линия 3 - обратное дерево 4 - также может встречаться несколько связанных обратных деревьев (не обратное дерево).
Например. для subgraph 1
мне нужно передать узлы в следующей последовательности: 1.1, 1.2, 1.3 или 1.1, 1.3, 1.2. Точная последовательность не важна. Единственное строгое условие - не переходить к узлу 4.7 до перехода к 4.1 и 4.5 в подграфе 4, но, как упоминалось выше, мне нужно начать переход от узлов без каких-либо входящих ребер. Может ли кто-нибудь предложить какой-либо уже существующий алгоритм, уже реализованный в networkx
, который делает возможной такую ходьбу? Нулевая вероятность столкновения с петлей на графике.
Пример кода для построения графика на скриншоте:
import networkx as nx
from networkx.algorithms.components import weakly_connected_components
g = nx.DiGraph()
for i in range(0, 23):
g.add_node(i)
g.add_edge(13,12)
g.add_edge(9, 8)
g.add_edge(3, 10)
g.add_edge(5, 13)
g.add_edge(7, 11)
g.add_edge(9, 14)
g.add_edge(7, 15)
g.add_edge(7, 16)
g.add_edge(17, 18)
g.add_edge(18, 19)
g.add_edge(3, 20)
g.add_edge(3, 22)
g.add_edge(18, 22)
g.add_edge(22, 21)
# removing unused nodes (without edges)
g.remove_node(0)
g.remove_node(1)
g.remove_node(2)
g.remove_node(4)
g.remove_node(6)
# get subgraphs
subgraphs = weakly_connected_components(g)
for subgraph in subgraphs:
# here I need to iterate nodes in each subgraph
# in following sequence - passing dependent node can't
# be passed before passing it's dependency nodes. For
# example, 4.7 can't be passed before 4.1 and 4.5, 4.5
# can't be passed before 4.4. But no matter which of 4.1
# and 4.5 will be passed first.
Спасибо.