NetworkX - remove node and reconnect edges

user_1700270 0
Viewed 2880

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)]
networkx
3 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.

user_153853070

I don't know if my solution is any better than Ryan already suggested, but I'm posting a function here, since it tries to tackle the question from a different perspective. They key is, that in a graph 1 > 2 > 3 the node 2 has degree 2 (i.e. has 2 edges connected to it). Generally speaking, to simplify a graph in the sense of the question that was asked would then mean getting rid of all such nodes with degree 2. The below function does exactly that.

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(g.in_edges(node))[0]
                    a1,b1 = list(g.out_edges(node))[0]

                else:
                    edges = g.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

An example:

>>> G = nx.DiGraph()
>>> G.add_edges_from([(1,2),(2,3)])
>>> list(G.edges)
[(1, 2), (2, 3)]

>>> g = simplifyGraph(G)
>>> list(g.edges)
[(1, 3)]
user_109805100

A simplified version on how to remove nodes with degree 2 and reconnect edges:

g = nx.DiGraph()
g.add_edges_from([(1,2),(2,3)])

for node, degree in dict(g.degree()).items():
    if degree == 2:
        # only 1 predecessor and 1 successor, equiv:
        # g.add_edge(list(g.predecessors(node))[0], list(g.successors(node))[0])
        g.add_edge(*g.predecessors(node), *g.successors(node))
        g.remove_node(node)

Output:

# before NodeView((1, 2, 3))
>>> g.nodes
NodeView((1, 3))

# before OutEdgeView([(1, 2), (2, 3)])
>>> g.edges
OutEdgeView([(1, 3)])
user_152399510
Related