python - Python networkx：边缘收缩

Question

我有一个NetworkX图。我想知道如何在多个节点之间进行边缘收缩。

例如，如果我想收缩 X、Y 和 Z：

         _ node A _
       _/    |     \_
node X --- node Y --- node Z

会成为

           node A 
             |     
           node XYZ (or whatever X/Y/Z)

图形创建不是问题。有用。我想通过合并具有相同“含义”的节点来缩小图形：我称之为“end lvl”（节点名称长度等于 7）并且链接在一起的节点。

我在 NetworkX 中找到了冷凝功能，所以我尝试使用它：

# edge contraction for same nodes
# for each node, get the links to other nodes "end lvl"
# if there is such a link, it means that these node are
# the sames
#
# copy graph
I = G
for n,d in G.nodes(data=True):
    if n in I.nodes():
        if len(n) == 7:
            # list of nodes adjacent to n : filter only "end lvl" nodes
            neighbors = [ node for node in I.neighbors(n) if len(node) == 7 ]
            nodes_to_merges = neighbors.append(n)
            I = nx.condensation(I,scc=nodes_to_merges)

当我转换为 JSON 时，我得到的是：

{"directed": true, "graph": [], "nodes": [{"id": 0}], "links": [], "multigraph": false}

如您所见，有一个问题...

函数参考在这里。

Answer 1

怎么样：

add_node(XYZ)
add_edge(XYZ, A)
for edge incident on (X, Y, Z):
    v = nodes in edge not in (X, Y, Z, A)
    if v:
       remove_edge(edge)
       add_edge(v, XYZ)
for node in (X, Y, Z):
    remove_node(node)

Answer 2

而不是尝试使用 nx.condensation （这意味着收缩强连接的组件，而不是一般的节点组）使用这些函数：

http://networkx.readthedocs.io/en/stable/reference/classes.graph.html#adding-and-removing-nodes-and-edges

删除除一个折叠节点之外的所有节点并重新连接它们的节点。