网络图中的2个节点合并

Question

我正在浏览networkx中的块模型函数。这似乎和我想要的非常相似。

我希望将networkx图中的两个节点合并在一起，并将其替换为与所连接的任何节点相对应的节点标签。其余的节点应该保持原样，而不改变它们的名称。(节点连接规则如块模型1教程中所解释)

• 至于我所理解的，块模型在使用之前需要创建整个图的显式定义，这不太方便。
• 无法控制所形成的块模型的名称。(新图的节点)。

我如何才能完成这个看似简单的任务，将两个节点折叠成一个？我想在一个带加权边的无向图上这样做。

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