时间戳

首页 > 解决方案 > 如何在不使用python断开图形的情况下随机删除n条边

python - 如何在不使用python断开图形的情况下随机删除n条边

问题描述

我正在使用 networkx 包，如何随机删除多个边缘但不会导致任何断开连接（节点数相同）。

我已经尝试对数据帧进行分层采样，但不工作，不知道该怎么做。请提供任何建议。

我是怎么做的：

removed_edge_cnt = 0
remove_list = set([])
pbar = tqdm(total=n)
while (removed_edge_cnt < n):
    removed = True
    drop_indices = np.random.choice(orig_data_copy.index, 1, replace=False)
    edge = orig_data_copy.iloc[drop_indices, :].values.ravel()
    orig_data_copy = orig_data_copy.drop(drop_indices)  # 不管該邊有沒有要刪掉都要drop避免一直取相同的edge
    # print('{}-{}:{}'.format(edge[0], edge[1], G.has_edge(edge[0], edge[1])))
    if G.has_edge(edge[0], edge[1]):  # 邊存在
        G.remove_edge(edge[0], edge[1])
        if not nx.is_weakly_connected(G):  # 移除是否會造成disconnect
            G.add_edge(edge[0], edge[1])
            removed = False
        if removed:
            removed_edge_cnt += 1
            remove_list.add((edge[0], edge[1]))
            pbar.update(1)
pbar.close()

标签： pythonnetworkxgraph-theory

解决方案

一个完全连通的图是一个从每个节点到另一个节点的路径。我认为这就是您所说的“不断开连接”

要检查一个图是否完全连接，请从任何节点进行深度优先搜索并确认每个节点都被访问过。

因此，删除您的随机边并检查图形是否仍然完全连接。如果没有，请更换链接并重试，直到找到可以删除的边缘。

推荐阅读