在 Python 中实现 Karger Min Cut 算法时遇到了死锁。我打破了我的头,但仍然无法弄清楚为什么我的实现不起作用,而它在铅笔和纸上工作得很好......
考虑一个具有四个节点 1、2、3、4 和五个边的图
[1, 2], [1, 3], [2, 3], [2, 4], [3, 4]
.
在 python 中,我用两个列表来表示它们:
nodes = [1, 2, 3, 4]
edges = [[1, 2], [1, 3], [2, 3], [2, 4], [3, 4]]
我的想法是:随机选择一条边,比如说[1, 3]
,折叠它,node = 3
从节点列表中删除,就好像 3 合并为 1 一样,然后[1, 3]
从边列表中删除边。
现在这两个列表看起来像:
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。
这样就完成了第一个循环。
在第二个循环中,假设边缘[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 算法的一次运行。虽然 while 循环中的那些 for 循环效率低下,但我只是想尝试一下这个想法。我在具有 200 个节点和 2000 多个边的输入上试验了上述代码。
但无论我做什么,Python 在成功删除几个节点和边后都会出现以下错误:
nodes.remove(j)
ValueError: list.remove(x): x not in list
这很有趣。如果x
不在节点列表中,则表示它x
是先前包含在所选边中的“j”之一,并且已被删除或更改为相应的“i”。
但是,我找不到我的代码有什么问题。我错过了什么吗?有什么想法吗?非常感谢。
链接到数据文件(非常感谢 GitHub 上的 nischayn22):https ://github.com/nischayn22/PythonScripts/blob/master/kargerMinCut.txt