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

Question

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

Вот пример:

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

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

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

Спасибо!

Answer 1

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

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

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

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

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

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

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

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

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

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

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

Answer 2

Позвольте мне предоставить вам код python 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()