python - グラフの最小カットのランダム化された収縮アルゴリズム

Question

最小カット問題を解決するための Karger のアルゴリズムの実装を作成しようとしました。これが私のコードです

def randomVertices(g): 
    v1 = g.keys() [random.randint(0,len(g)-1)]
    v2 = g[v1] [random.randint(0,len(g[v1])-1)]
    return v1, v2


def mergeVertices(g):
    v1,v2 = randomVertices(g)

    g[v1].extend(g[v2])

    for x in g[v2]:
        l = g[x]
        for i in range(0,len(l)):
            if l[i] == v2: 
                l[i] = v1        

    while v1 in g[v1]:
        g[v1].remove(v1)

    del g[v2]

def minCut(g): 
    while len(g) > 2: 
        mergeVertices(g)
    return len(g[g.keys()[0]])

コメントはありませんが、一目瞭然です。「g」は、キーがグラフの頂点であり、それぞれが接続されている頂点の値を持つ辞書です。randomVertices は縮小したいエッジを与え、mergeVertices は 2 番目の頂点を削除し、この頂点にリンクされたキーの値を更新し、自己ループを取り除くことによって辞書 (したがってグラフ) を更新します。私には問題ないように見えますが、テストグラフで実行すると、その段階で KeyError が発生し、l = g[x]なぜこれが起こっているのか理解できません。あなたの何人かが私を助けることができることを望んでいました。ありがとう。

編集:私のコードは実際には問題ありません。エラーは、隣接するリストでファイルをロードした方法にありました。Cobarzan、私が実際にエッジを一様に選んでいないことを指摘してくれてありがとう.