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