1

Python で Karger Min Cut アルゴリズムを実装するときにデッドロックに遭遇しました。私は頭を壊しましたが、鉛筆と紙で問題なく動作するにもかかわらず、実装が機能しない理由をまだ理解できません...

4 つのノード 1、2、3、4、および 5 つのエッジを持つグラフを考えてみましょう

[1, 2], [1, 3], [2, 3], [2, 4], [3, 4].

Python では、それらを 2 つのリストで表しました。

nodes = [1, 2, 3, 4]
edges = [[1, 2], [1, 3], [2, 3], [2, 4], [3, 4]]

私の考えは、エッジをランダムに選択し、[1, 3]それを折りたたんで、node = 3ノード リストから 3 が 1 にマージされたかのように削除し[1, 3]、エッジ リストからエッジを削除することです。

2 つのリストは次のようになります。

nodes = [1, 2, 4]
edges = [[1, 2], [2, 3], [2, 4], [3, 4]]

3 が 1 にマージされると、エッジ リストはさらに次のように更新されます。

edges = [[1, 2], [2, 1], [2, 4], [1, 4]]

結果のエッジ リストの 3 つすべてを 1 に変更します。

これで最初のループが完了します。

2 番目のループでは、エッジ[1, 2]がエッジ リストからランダムに選択され、上記の手順を繰り返して、

nodes = [1, 4]
edges = [[2, 1], [2, 4], [1, 4]]

これはさらに に変更され[[1, 1], [1, 4], [1, 4]]ます。自己ループを示すよう[1, 1]に、それは削除され、このラウンドの結果のエッジ リストは次のようになります。[[1, 4], [1, 4]]

ノードの数が 2 であるため、プロセスは終了し、最小カット数は 2 (最終エッジ リストの長さ) になります。

したがって、Python での私の実装は次のとおりです。

import numpy as np


nodes = []
edges = []


f = open("kargerMinCut.txt", "r")
# The txt file has the form of an adjacency list
# The link to the txt file is at the very end          

for l in f:
    v = l.split()
    # The first element of each line is a (distinct)
    # vertex and is appended to nodes list.    
    nodes.append(int(v[0]))
    for u in v[1:]:
        # Edges list has the form as described in my 4 nodes example
        # above, which is unlike what in an typical adjacency list for
        # an undirected graph is. Here, if node 1 and node 2 share 
        # an edge, then edge [1, 2] only appears once in the "edges"
        # list, edge [2, 1] is not, which is why I used "set" below.
        edge = [int(v[0])]
        edge.append(int(u))
        count = 0
        for edg in edges:
            if (set(edg) == set(edge)):
                count += 1
        if (count == 0):
            edges.append(edge)

f.close()


while (len(nodes) > 2):
    # Number of current edges
    m = len(edges)
    # Choose a random edge uniformly 
    idx = np.random.randint(m)
    edgeChosen = edges[idx]
    # Two corresponding nodes of the chosen edge
    i = edgeChosen[0]
    j = edgeChosen[1]

    # Remove the second one from nodes list
    nodes.remove(j)
    # Remove the chosen edge from edges list
    del edges[idx]

    # Change all "j"s to "i"
    for ed in edges:
        for e in ed:
            if e == j:
                e = i

    # Remove those [i, i] edges (self loop)
    for ed in edges[:]:
        if len(set(ed)) == 1:
            edges.remove(ed)


print len(edges)

これは Karger Min Cut アルゴリズムの 1 回の実行にすぎません。while ループ内の for ループは非効率的ですが、このアイデアを試してみたいと思います。200 個のノードと 2000 個以上のエッジを持つ入力で上記のコードを実験しました。

しかし、私が何をしたとしても、いくつかのノードとエッジを正常に削除した後、Python は次のエラーを返します。

nodes.remove(j)
ValueError: list.remove(x): x not in list

これはちょっと面白いです。xがノード リストにない場合はx、以前に選択したエッジに含まれていた「j」の 1 つが削除されたか、対応する「i」に変更されたことを意味します。

ただし、コードの何が問題なのかを見つけることができません。何か不足していますか？それに関するアイデアはありますか？どうもありがとう。

データ ファイルへのリンク (GitHub の nischayn22 に感謝します): https://github.com/nischayn22/PythonScripts/blob/master/kargerMinCut.txt

4

2 に答える 2

1

これはかなり初歩的な作業バージョンです。このコードはさまざまな方法で改善できますが、うまく機能し、正しく行う方法を示してくれるはずです。

from random import randint

nodes = [1,2,3,4]
edges = [[1, 2], [1, 3], [2, 3], [2, 4], [3, 4]]


while (len(nodes) > 2):
    target_edge = edges[randint(0, len(edges) - 1)]
    replace_with = target_edge[0]
    num_to_replace = target_edge[1]
    for edge in edges:
        if(edge[0] == num_to_replace):
            edge[0] = replace_with
        if(edge[1] == num_to_replace):
            edge[1] = replace_with
    edges.remove(target_edge)
    nodes.remove(num_to_replace)
    #remove self loops
    for edge in edges:
        if(edge[0] == edge[1]):
            edges.remove(edge)
    print(edges)

print(nodes)
print(edges)
于 2013-08-01T08:05:04.590 に答える