python - 我在 Python 中的图形收缩算法表现异常

Question

我已经为这个问题写了一些代码。 (python27)

图表示为具有 frozenset 键和 frozenset 集的字典:

sample_graph = {frozenset([7]): set([frozenset([4]), frozenset([5]), frozenset([3])]), frozenset([5]): set([frozenset([7]), frozenset([2]), frozenset([1])]), frozenset([3]): set([frozenset([7]), frozenset([4]), frozenset([2]), frozenset([1])]), frozenset([6]): set([frozenset([4]), frozenset([2]), frozenset([1])]), frozenset([4]): set([frozenset([6]), frozenset([7]), frozenset([3]), frozenset([1])]), frozenset([1]): set([frozenset([6]), frozenset([4]), frozenset([5]), frozenset([2]), frozenset([3])]), frozenset([2]): set([frozenset([6]), frozenset([5]), frozenset([3]), frozenset([1])])}

输出应该是一个只有两个节点的图，这两个节点是图中所有节点的卡住集。此时它遇到了 KeyError。

def kargerMinCut(graph):
if len(graph) == 2:
    return graph
u = random.choice(graph.keys())   # u and v are frozensets, idea is that they form
v = random.choice(list(graph[u])) # a clique in a single frozenset
for node in graph:
    if node != u and node != v:
        links = graph[node]       
        if u in links or v in links:
            links.add(frozenset(tuple(u | v))) # combine u and v to form one link
            links.discard(u)                   # delete old links to u and v
            links.discard(v)            
            graph[node] = links
graph[u | v] = graph[u] | graph[v]             # new key for u and v 
del graph[u], graph[v]                         # u and v are no longer needed
return kargerMinCut(graph)

Answer 1

我认为问题可能出在 is 关键字的使用上。请注意，在 python 中，is 仅在两个参数引用完全 相同对象时才返回 true(相当于 char* == char* C++. 如果内容相同，== 运算符返回 true(相当于 C++ 中的 string == string)。

所以 不是 试试 !=。

在 python 中遍历图形中的元素时，我曾经遇到过同样的问题。 :)

PS-- 此外，我会将以下行写成完整的 if:

links.add(frozenset(tuple(u | v))) if u in links or v in links else None