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

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

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