I have a node in a graph that acts as a sort of 'temporary connector' node. I'd like to remove that node and update the edges in the graph so that all of its immediate predecessors point to its immediate successors.
Is there baked-in functionality to do that in networkx
, or will I need to roll my own solution?
Example:
I have a graph 1 > 2 > 3
. I'd like to remove node 2
and end up with the graph 1 > 3
.
Here's how I am currently doing it:
In [230]: g = nx.DiGraph()
In [231]: g.add_edges_from([(1,2),(2,3)])
In [232]: g.edges()
Out[232]: [(1, 2), (2, 3)]
In [233]: predecessors = g.predecessors(2)
In [234]: successors = g.successors(2)
In [235]: new_edges = [(p,s) for p in predecessors for s in successors]
In [236]: new_edges
Out[236]: [(1, 3)]
In [237]: g.remove_node(2)
In [238]: g.add_edges_from(new_edges)
In [239]: g.nodes()
Out[239]: [1, 3]
In [240]: g.edges()
Out[240]: [(1, 3)]
To remove multiple nodes, there is also the Graph. remove_nodes_from() method. Show activity on this post. Documentation covers it.
The Graph. remove_nodes_from() method takes a list (container actually) of nodes. So you just need to create a list that satisfies your condition. You can use Python's list comprehension structure to compactly create a list of nodes to delete.
I tried using mjvaak's answer on a huge complex Graph but it didn't work since it was creating edges with nodes that did not exist anymore. I fixed it by simply taking the edges from g0.
So I changed:
edges = g.edges(node)
for:
edges = g0.edges(node)
The fixed code is thus the following:
def simplifyGraph(G):
''' Loop over the graph until all nodes of degree 2 have been removed and their incident edges fused '''
g = G.copy()
while any(degree==2 for _, degree in g.degree):
g0 = g.copy() #<- simply changing g itself would cause error `dictionary changed size during iteration`
for node, degree in g.degree():
if degree==2:
if g.is_directed(): #<-for directed graphs
a0,b0 = list(g0.in_edges(node))[0]
a1,b1 = list(g0.out_edges(node))[0]
else:
edges = g0.edges(node)
edges = list(edges.__iter__())
a0,b0 = edges[0]
a1,b1 = edges[1]
e0 = a0 if a0!=node else b0
e1 = a1 if a1!=node else b1
g0.remove_node(node)
g0.add_edge(e0, e1)
g = g0
return g
Thank you mjkvaak for the solution! It just needed a slight modification for bigger graphs.
If you love us? You can donate to us via Paypal or buy me a coffee so we can maintain and grow! Thank you!
Donate Us With