Какой алгоритм мне нужен для этой операции направленного графа?

Question

Возможно, я обдумываю это и упускаю что-то очевидное, но мне было интересно, какой алгоритм NetworkX я мог бы использовать для достижения следующего:

Дано DiGraph, такие как:

И список узлов, таких как: Q1, Q2

Найдите все узлы, которые связаны (или, другими словами, потомками) Q1 и Q2, результаты будут следующими:

Какой алгоритм достиг бы этого?

Answer 1

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

Другой способ - использовать посещение (DFS или BFS) на графике, обращая ребра.

Рассмотрим следующий пример, где я строю дерево BFS, начиная с узла "Q1".

import networkx as nx

g = nx.DiGraph()

g.add_edges_from([("M1","Q1"),("I1","M1"),("I2","M1"),("I3","M1"),("I3","M2"),("M2","Q2")])

#creating a graph with the edges reversed
g2 = nx.DiGraph()
g2.add_edges_from([(v,u) for (u,v) in g.edges()])

t = nx.bfs_tree(g2, "Q1")

for (u,v) in t.edges():
    t.remove_edge(u,v)
    t.add_edge(v,u)


print(t.nodes(),t.edges())
# ['Q1', 'M1', 'I1', 'I2', 'I3'] [('M1', 'Q1'), ('I1', 'M1'), ('I2', 'M1'), ('I3', 'M1')]

Answer 2

Похоже, вам просто нужно сделать рекурсию по сети x.Digraph.predecessors