NetworkX - 删除节点并重新连接边

Question

我在一个图中有一个节点，充当一种“临时连接器”节点。我想删除该节点并更新图中的边，以便所有直接前任指向其直接后继。

在networkx中有现成的功能可以做到这一点吗？还是我需要自己解决？

例如：

我有一个图形1> 2> 3。 我想删除节点2并得到图形1 > 3。

以下是我目前的做法：

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)]

- ryantuck

---

不确定为什么所有答案都假设与节点度有关。我们难道不是在谈论一个通用图，我们想要从标记节点列表中删除一些节点吗？ - lifezbeautiful

Answer 1

我尝试使用mjvaak的答案来处理一个非常复杂的图形，但由于它正在创建与不再存在的节点相连的边缘，因此无法正常工作。我通过简单地从g0中获取边缘来修复它。

所以，我进行了如下更改：

edges = g.edges(node)

对于：

edges = g0.edges(node)

固定的代码如下所示：

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

感谢mjkvaak提供的解决方案！对于更大的图表，只需要进行轻微修改即可。

- sauce_interstellaire

---

你所说的“巨大复杂的多图”具体是什么意思？能否提供一个可重现的例子？我认为原帖作者的解决方案是通用的，应该始终有效。 - lifezbeautiful

很抱歉，我正在处理一些专属于我所在研究小组的血管解剖网络数据，因此无法分享我所使用的数据。同时，我之前认为这是一个多重图，但后来发现这只是一个无向图。我已经在我的帖子中将“多重图”一词进行了编辑。 - sauce_interstellaire

我明白了，感谢您的解释和更新！ - lifezbeautiful

Answer 2

如何简化删除度数为2的节点并重新连接边的方法：

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)

输出：

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

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

- Corralien

Answer 3

我不知道我的解决方案是否比Ryan已经提出的更好，但是我在这里发布一个函数，因为它尝试从不同的角度来解决问题。关键是，在 图 1 > 2 > 3 中，节点2的度数为2（即有2条边连接到它）。一般来说，简化一个图的意义就是摆脱所有这样的度数为2的节点。下面的函数正是这样做的。

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

一个例子：

>>> 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)]

- mjkvaak

---

我认为这不是一个普遍的答案。可能有许多具有相同度数的节点，或者图可能更加复杂。 - Rahat Zaman

Answer 4

这里是一个通用解决方案，用户可以提供任何节点条件来删除节点并重新组合图形。在注释中，我还放置了一些代码，允许用户重新组合具有不同权重的边。

import networkx as nx
from itertools import combinations

def simplify_graph_with_predicate(G: nx.Graph, node_removal_predicate: callable):
    '''
    Loop over the graph until all nodes that match the supplied predicate 
    have been removed and their incident edges fused.
    '''
    g = G.copy()
    while any(node_removal_predicate(node) for node in g.nodes):

        g0 = g.copy()

        for node in g.nodes:
            if node_removal_predicate(node):

                if g.is_directed():
                    in_edges_containing_node = list(g0.in_edges(node))
                    out_edges_containing_node = list(g0.out_edges(node))

                    for in_src, _ in in_edges_containing_node:
                        for _, out_dst in out_edges_containing_node:
                            g0.add_edge(in_src, out_dst)
                            # dist = nx.shortest_path_length(
                            #   g0, in_src, out_dst, weight='weight'
                            # )
                            # g0.add_edge(in_src, out_dst, weight=dist)
                else:
                    edges_containing_node = g.edges(node)
                    dst_to_link = [e[1] for e in edges_containing_node]
                    dst_pairs_to_link = list(combinations(dst_to_link, r = 2))
                    for pair in dst_pairs_to_link:
                        g0.add_edge(pair[0], pair[1])
                        # dist = nx.shortest_path_length(
                        # g0, pair[0], pair[1], weight='weight'
                        # )
                        # g0.add_edge(pair[0], pair[1], weight=dist)
                
                g0.remove_node(node)
                break
        g = g0
    return g

示例用法1（提供的例子）：

g = nx.DiGraph()
g.add_edges_from([(1,2),(2,3)])
res = simplify_graph_with_predicate(g, lambda node: node == 2)
print(res.edges) # output: [(1,3)]

示例用法2：

g = nx.DiGraph()
g.add_edge("node_one", "node_two")
g.add_edge("node_two", "node_three")
res = simplify_graph_with_predicate(g, lambda node: "two" in node)
print(res.edges) # output: [('node_one', 'node_three')]

- aleksk