为了收缩双连接组件,我们将首先重新标记每个组件中的节点,使它们具有相同的标签,然后删除自循环。

构建标签映射

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