Как эффективно получить выходные узлы в ориентированном графе в networkx?

Question

Я создал простой ориентированный граф (DiGraph) в сетевом пакете Python networkx, например:

import networkx as nx

G = DiGraph([(1, 2)])

Теперь я хотел бы узнать самый быстрый / самый эффективный способ определить выходные узлы (который в данном случае является узлом 2). Под выходным узлом я подразумеваю узлы в ориентированном графе, которые не имеют преемника - с входными узлами , являющимися узлами, которые не имеют предшественника. Аналогия с Машинным обучением, в котором я поставляю значения входным узлам, выполняю математические операции на краях и получаю выходные значения в выходных узлах . См. здесь для примера, в котором p, d и lambda являются входными узлами, а p 'и d' являются выходными узлами.

После прочтения документации я пришел с такими неэффективными методами, как обход всех узлов графа, вызов successors() для них и сохранение всех узлов без преемника. Это, однако, ужасно неэффективно, тем более что график, очевидно, значительно больше и сложнее в моем реальном проекте. Я надеялся на простой и эффективный метод, такой как G.out_nodes() или что-то подобное, который отслеживает выходные узлы при редактировании графика, хотя, похоже, я не могу его найти. Однако, поскольку определение выходных и входных узлов в ориентированном графе не является необычной задачей, я считаю, что что-то упустил. Я надеялся, что вы сможете мне помочь. Большое спасибо.

Answer 1

Получив график, вы можете выполнить итерацию и получить узлы с out_degree, равным 0.

output_nodes = [u for u, deg in g.out_degree() if not deg]

Однако вы можете получить их непосредственно при построении графика, действительно, вы можете удалить из узлов u, если (u,v) - это ar c. Остальные будут выходными узлами.
Другая возможность - использовать другой способ представления вашего графа в соответствии с размером / наиболее распространенными операциями, которые нужно применить.