时间戳

首页 > 解决方案 > 当且仅当图保持连接时从nx图中删除节点？

python - 当且仅当图保持连接时从nx图中删除节点？

问题描述

当且仅当图保持连接时，我试图从现有的 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

我只是犹豫是否要创建副本来执行此操作，因为我正在迭代地从大图中删除节点。有一个更好的方法吗？

标签： pythonperformancenetworkxgraph-theory

解决方案

您可能忽略了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

推荐阅读