顶点收缩 - python

Question

我有一个包含一些连接组件的子图，如下所示：

我正在使用

bicomponents = list(nx.biconnected_components(T))

识别子图中的所有连通分量。我需要删除整个连接的组件并将该组件收缩到一个顶点并获得一个新的叶子。例如，我需要删除组件 {28,30,31} 并引入一个新顶点 51（我有 n= 50 个顶点，所以新的顶点将是 51）并加入 29 获得新的叶子。

有人可以帮我做吗？

Answer 1

为了收缩双连通组件，我们将首先重新标记每个组件中的节点，使它们具有相同的标签，然后删除 self-loops。

构造标签映射

label_mapping = {}
for idx, node_component in enumerate(filter(lambda s: len(s) > 2, nx.biconnected_components(g)), start=len(g) + 1):
    for node in node_component:
        if node not in label_mapping:
            label_mapping[node] = idx

这里我做了两个假设：我们丢弃了琐碎的双连通分量（因此 filter，如果不需要，可以很容易地删除），如果一个节点属于两个双连通分量（切割顶点），我们不' 将这两个组件收缩为一个节点，但为两个组件保留两个节点。如果这不是所需的行为，我们需要合并具有公共节点的组件，其解决方案在 this question.

中

合同组件

h = nx.relabel_nodes(g, label_mapping)
h.remove_edges_from(h.selfloop_edges())

顶点收缩 - python

vertex contraction - python

vertex

networkx

python-3.x

构造标签映射

合同组件