在Python中我的圖收縮算法行爲奇怪

我已經寫了一些代碼爲這個問題。（python27）在Python中我的圖收縮算法行爲奇怪

圖形被表示爲與frozensets的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])])}

輸出應該是一張圖表，其中只有兩個節點其是圖中的所有節點的frozensets。此時它會運行到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)

來源

2012-07-05 AndrewSokolowski

請修復您的縮進以匹配您正在運行的代碼。此外，如果您提供了您的輸入，預期的返回值和實際的返回值，這將有所幫助。 – chepner 2012-07-05 20:17:20

縮進僅在def的第一行被違反。我會添加示例圖形輸入，但它是隨機算法，所以我無法確切知道輸出是什麼。 – AndrewSokolowski 2012-07-05 20:34:16

@AndrewSokolowski在這種情況下，我會製作一個小的演示圖並選擇具體的'u'和'v'。先從一個你知道會發生什麼的例子開始，以幫助你決定你的代碼是否按照預期工作：「有一天，愛麗絲來到路邊的一個叉子上，在樹上看到一隻柴郡貓。我拿？*她問。*你想去哪兒？*是他的回答。*我不知道*，愛麗絲回答。*然後*，說貓，*沒關係。*「：） – user 2012-07-05 20:52:25

我覺得問題可能是is關鍵字的使用。需要注意的是在Python，is只有當兩個參數指確切相同的對象（等價於C char* == char* ++返回true。該==操作者如果內容是相同的（等價於C string == string ++）返回true。

因此，而不是is not嘗試!=

在python遍歷一個圖形元素時，我曾經有過這樣的問題相同：。）

PS--另外，我會寫下面的行作爲一個完整的if：

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

來源

2012-07-05 19:08:09 user

Thnx！我嘗試了你的建議，但不幸的是，循環仍然沒有改變一毛錢 – AndrewSokolowski 2012-07-05 20:06:08

發現一個愚蠢的錯誤，將嘗試調試它:) – AndrewSokolowski 2012-07-05 20:29:27

這個問題最終成爲了什麼？ – user 2012-07-06 05:58:46

在Python中我的圖收縮算法行爲奇怪

回答

相關問題