CODEWITHSUNDEEP
pythonperformancenetworkxgraph-theory
Dom McEwen
Dom McEwen

Reputation: 421

Removing nodes from a nx graph if and only if the graph remains connected?

I'm trying to remove nodes from an existing nx graph G if and only if the graph remains connected. What is the most efficient way to do this?

My attempt for removing node 5 for example is:

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

I'm just hesitant about creating copies to do this since I'm iteratively removing nodes from a large graph. Is there a better way to do this?

Upvotes: 0

Views: 648

Answers (1)

Dbercules
Dbercules

Reputation: 719

You might have overlooked the single parameter available to Graph.copy() i.e. Graph.copy(as_view = False). What this parameter does is provide "a copy of the original structure without requiring any memory for copying the information". You could perform the removal on that mimicked structure and upon retaining full connection, execute it on the real thing. If you're worried about the memory clog of storing two complete networks, then the use of that parameter could be your solution. If not, you'll need to provide more detail in your question and some reproducible code.

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

Upvotes: 1

Related Questions