0

この問題のコードをいくつか書きました。(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])])}

出力は、グラフ内のすべてのノードのフリーズセットである 2 つのノードのみを含むグラフである必要があります。この時点で、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)
4

1 に答える 1

1

is問題はキーワードの使い方だと思います。Python ではis、2 つの引数がまったく同じオブジェクトを参照している場合にのみ true を返すことに注意してください ( char* == char*C++と同等)。==内容が同じ場合、演算子は true を返します ( string == stringC++ と同等)。

ではなく、is not試してみてください!=。

Pythonでグラフ内の要素をトラバースするときに、この同じ問題が発生したことがあります。: )

PS--また、次の行を完全に記述しますif。

links.add(frozenset(tuple(u | v))) if u in links or v in links else None
于 2012-07-05T19:08:09.767 に答える