Блог

Главная - Вопросы по программированию - Удаление узлов из графа nx тогда и только тогда, когда граф остается связанным?

Удаление узлов из графа nx тогда и только тогда, когда граф остается связанным?

#python #performance #networkx #graph-theory

#python #Производительность #networkx #теория графов

Вопрос:

Я пытаюсь удалить узлы из существующего графа nx G тогда и только тогда, когда граф остается подключенным. Каков наиболее эффективный способ сделать это?

Например, моя попытка удалить узел 5:

 node = 5

# make temporary copy
T = G.copy()

# remove node from copy
T.remove_node(node)

# replace G with T if the graph is connected
if nx.is_connected(T):
    G = T

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

Комментарии:

1. Вы гарантируете, что исходный граф подключен? Если это так, то будут более быстрые способы проверить, подключен ли новый граф. Возьмите одного соседа удаленного узла. Если от него есть путь к каждому из других узлов, то граф все еще связан. Это намного быстрее проверить (используя has_path ), чем выполнять проверку того, подключен ли весь граф.

2. Хорошая идея, она гарантированно подключена.

Ответ №1:

Возможно, вы упустили из виду единственный параметр, доступный для Graph.copy(), т.е. Graph.copy(as_view = False) . Что делает этот параметр, так это предоставляет «копию исходной структуры, не требуя никакой памяти для копирования информации». Вы можете выполнить удаление этой имитируемой структуры и, сохранив полное соединение, выполнить его на реальной вещи. Если вы беспокоитесь о засорении памяти при хранении двух полных сетей, то использование этого параметра может быть вашим решением. Если нет, вам нужно будет предоставить более подробную информацию в вашем вопросе и некоторый воспроизводимый код.

 import networkx as nx
import time as t

base_graph = nx.circulant_graph(n=1000, offsets=[1])
if nx.is_connected(base_graph):
    print('Graph is connected.')

node_id_to_remove = 500

start_time = t.time()
copied_real_graph = base_graph.copy(as_view=False)
print(f"Execution Time: {(t.time() - start_time)}")

start_time = t.time()
copied_view_graph = base_graph.copy(as_view=True)
print(f"Execution Time: {(t.time() - start_time)}")

-------------------
Graph is connected.
Execution Time: 0.005429983139038086
Execution Time: 0.0003299713134765625