python - 使用networkX的karger min cut算法运行时间非常慢

Question

Python 新手。尝试使用 networkX 包来完成工作，但它的运行时间似乎比“创建列表列表”来表示图形要长得多。这仅仅是因为 nextworkX 的数据结构对于这个简单的任务来说太多了吗？顺便说一句，结果将输出两倍的答案。因为 read_adjlist 函数会对文件中的 u 和 v 节点对相同的边进行两次计数。有什么办法可以避免这种情况并允许识别平行边缘吗？

谢谢大家。

import networkx as nx
import random

Graph_Adjacency_List = "***.txt"
handle = open(Graph_Adjacency_List, 'r')
G=nx.read_adjlist(handle,create_using=nx.MultiGraph(), nodetype=int)

def cut(G):
    while G.number_of_nodes()>2 :
        u,v= random.choice(G.edges())
        G = nx.contracted_edge(G, (u, v), self_loops=False)
    return G.number_of_edges()

m=100
for i in range(1000):
    random.seed()
    c=cut(G)
    if c< m:
        m=c
        print m

Answer 1

为了解决边缘上的重复计算问题，我简单地返回了:

int(G.number_of_edges()/2)

而不是:

G.number_of_edges()

为了解决算法速度慢的问题，我没有使用 nx.contracted_edge，该函数返回一个新图，像其他人评论的那样花费了大量时间。我就地进行了操作，查看了 nx.contracted_edge 的源代码并将 H 与 G 交换:

new_edges = ((u, w, d) for x, w, d in G.edges(v, data=True)
                 if False or w != u)
v_data = G.node[v]
G.remove_node(v)
G.add_edges_from(new_edges)
if 'contraction' in G.node[u]:
    G.node[u]['contraction'][v] = v_data
else:
    G.node[u]['contraction'] = {v: v_data}