Logo Questions Linux Laravel Mysql Ubuntu Git Menu
 

NetworkX - remove node and reconnect edges

Tags:

networkx

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)]
like image 625
ryantuck Avatar asked Nov 17 '18 16:11

ryantuck


People also ask

How do I remove a node from a graph in NetworkX?

To remove multiple nodes, there is also the Graph. remove_nodes_from() method. Show activity on this post. Documentation covers it.

How do you remove a node from a graph in Python?

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.


1 Answers

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.

like image 50
sauce_interstellaire Avatar answered Oct 25 '22 07:10

sauce_interstellaire