Как удалить все связанные узлы в ориентированном графе с помощью networkx?

Question

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

Вот пример:

Скажем, я удалить узел «11», я хочу узел «2», чтобы быть удалены, а также (и в моем собственном примере, они будут узлы под 2, которые теперь также должны быть удалены), потому что он больше не связан с основным графиком. Обратите внимание: этот узел «9» или «10» не должен быть удален, потому что узлы «8» и «3» еще не подключены к ним.

Я использую библиотеку python libraryx. Я искал документацию, но я не уверен в терминологии, поэтому я не уверен, что это называется. Если возможно, я хотел бы использовать функцию, предоставляемую библиотекой, чем создать собственную рекурсию через график (так как мой график довольно большой).

Любая помощь или предложения относительно того, как это сделать, было бы замечательно.

Спасибо!

Answer 1

Я предполагаю, что выполняются следующие условия:

• Граф ациклический. Вы упомянули об этом в своем комментарии, но я хотел бы четко указать, что это исходное предположение.
• Существует известный набор корневых узлов. Нам нужно иметь некоторый способ узнать, какие узлы всегда считаются доступными, и я предполагаю, что (каким-то образом) эта информация известна.
• Начальный график не содержит лишних узлов. То есть, если начальный граф содержит любые узлы, которые необходимо удалить, они уже были удалены. Это позволяет алгоритму работать, поддерживая инвариант, что каждый узел должен быть там.

Если это так, то дается начальная установка, единственная причина, что узел в графе будет либо

1. узел находится в корневом достижимости узлов, или
2. У узла есть родитель, который находится в корневом наборе узлов.

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

Учитывая эту настройку, после удаления узла вам нужно будет сканировать все дочерние узлы этого узла, чтобы увидеть, нет ли у кого-либо из них других родителей, которые сохранили бы их на графике. Поскольку мы предполагаем, что единственными узлами в графе являются узлы, которые должны быть там, если у дочернего элемента удаленного узла есть хотя бы один другой родитель, то он все равно должен быть на графике. В противном случае этот узел необходимо удалить.Один из способов сделать шаг удаления, таким образом, был бы следующий рекурсивный алгоритм:

• Для каждого из детей узла удаляемых:
  • Если этот узел имеет только один из родителей: (он должен быть узел, который мы собираемся удалить)
    • Рекурсивно удалить этот узел с графика.
• Удалить указанный узел из графа.

Это, вероятно, не очень хороший алгоритм для реализации непосредственно, однако, поскольку вовлеченная рекурсия может стать довольно глубокой, если у вас большой граф. Таким образом, вы можете реализовать его с помощью алгоритма рабочего списка, как это:

• Создать рабочий список W.
• Добавить V, узел удалять, W.
• Хотя W не пусто:
  • Удалить первую запись из W; назовите его w.
  • Для каждого из детей в W:
    • Если ребенок имеет только один из родителей, добавьте его в W.
  • Удалить ж из графика.

Это заканчивает тем, что в худшем случае O (м) время, где М числа ребер в графе, так как в теории, каждое ребро должно быть отсканировано. Однако это может быть намного быстрее, если предположить, что ваш график имеет некоторые избытки в нем.

Надеюсь, это поможет!

Answer 2

Позволь мне представить вам питон NetworkX коды, который решает свою задачу:

import networkx as nx 
import matplotlib.pyplot as plt#for the purpose of drawing the graphs 
DG=nx.DiGraph() 
DG.add_edges_from([(3,8),(3,10),(5,11),(7,11),(7,8),(11,2),(11,9),(11,10),(8,9)]) 
DG.remove_node(11) 

connected_components метод удивительно не работает на ориентированных графах, поэтому мы переходим график в неориентированный, выяснить, не связанные узлы а затем удалить их из ориентированного графа

UG=DG.to_undirected() 
not_connected_nodes=[] 
for component in nx.connected_components(UG): 
    if len(component)==1:#if it's not connected, there's only one node inside 
     not_connected_nodes.append(component[0]) 
for node in not_connected_nodes: 
    DG.remove_node(node)#delete non-connected nodes 

Если вы хотите, чтобы увидеть результат, добавьте в скрипт следующие две строки:

nx.draw(DG) 
plt.show()