python - 在 networkx 图中合并 2 个节点

Question

我正在研究networkx中的blockmodel函数。这似乎与我想要的非常相似。

我希望合并 networkx 图中的两个节点，并将其替换为与任何要连接的节点相对应的节点标签。其余节点应保持原样，而不会更改其名称。（节点加入规则见blockmodel 1教程）

• 至于我的理解，blockmodel需要在使用之前创建整个图的显式分区，这不太方便。
• 无法控制形成的块模型的名称（即新图的节点）。

我怎样才能实现将 2 个节点合并为一个的看似简单的任务？我想在一个带有加权边的无向图上做这件事。

Answer 1

这是我为我正在研究的图形着色程序创建合并函数的尝试。但是，它不适用于加权边缘。

import networkx as nx
# G is a graph created using nx
# this is to establish the number of colors
k = 5
# inputs node1 and node2 are labels of nodes, e.g. 'a' or 'b' etc.
def coalesce(G,node1,node2):
    """Performs Briggs coalescing. Takes in the graph and two nodes.
    Returns 1 if unable to coalesce, 0 otherwise."""
    if node1 in G.neighbors(node2) or node2 in G.neighbors(node1):
        print "Cannot coalesce. Node",node1,"and node",node2,"share an edge"
        return 1
    elif G.degree(node1)+G.degree(node2) >= k:
        print "Cannot coalesce. Combined degree of",node1,"and",node2,"\
is",G.degree(node1)+G.degree(node2),"which is too high for k =",k
        return 1
    else:
        newedge = []
        for i in range(len(G.neighbors(node2))):
            newedge.append((node1 , G.neighbors(node2)[i]))
        G.add_edges_from(newedge)
        G.remove_node(node2)
        nx.relabel_nodes(G, {node1:node1+node2},copy=False)
    return 0