这是我的karger min cut算法的代码。据我所知，我实现的算法是正确的。但我没有得到正确答案。如果有人可以检查出了什么问题，我将不胜感激。
import random
from random import randint
#loading data from the text file#
with open('data.txt') as req_file:
mincut_data = []
for line in req_file:
line = line.split()
if line:
line = [int(i) for i in line]
mincut_data.append(line)
#extracting edges from the data #
edgelist = []
nodelist = []
for every_list in mincut_data:
nodelist.append(every_list[0])
temp_list = []
for temp in range(1,len(every_list)):
temp_list = [every_list[0], every_list[temp]]
flag = 0
for ad in edgelist:
if set(ad) == set(temp_list):
flag = 1
if flag == 0 :
edgelist.append([every_list[0],every_list[temp]])
#karger min cut algorithm#
while(len(nodelist) > 2):
val = randint(0,(len(edgelist)-1))
print val
target_edge = edgelist[val]
replace_with = target_edge[0]
should_replace = target_edge[1]
for edge in edgelist:
if(edge[0] == should_replace):
edge[0] = replace_with
if(edge[1] == should_replace):
edge[1] = replace_with
edgelist.remove(target_edge)
nodelist.remove(should_replace)
for edge in edgelist:
if edge[0] == edge[1]:
edgelist.remove(edge)
print ('edgelist remaining: ',edgelist)
print ('nodelist remaining: ',nodelist)
测试用例数据是：
1 2 3 4 7
2 1 3 4
3 1 2 4
4 1 2 3 5
5 4 6 7 8
6 5 7 8
7 1 5 6 8
8 5 6 7
请将其复制到文本文件中并将其另存为“data.txt”并运行该程序
答案应该是：最小切割数为2，切割位于边缘[（1,7），（4,5）]
所以Karger的算法是一个“随机算术”。也就是说，每次运行它都会产生一个绝不保证最佳的解决方案。一般的方法是运行很多次并保持最佳解决方案。对于许多配置，将会有许多最佳或近似最佳的解决方案，因此您可以尝试快速找到一个好的解决方案。
据我所知，你只运行算法一次。因此，解决方案不太可能是最佳解决方案。尝试在for循环中运行100次并保持最佳解决方案。
此代码也有效。
import random, copy
data = open("***.txt","r")
G = {}
for line in data:
lst = [int(s) for s in line.split()]
G[lst[0]] = lst[1:]
def choose_random_key(G):
v1 = random.choice(list(G.keys()))
v2 = random.choice(list(G[v1]))
return v1, v2
def karger(G):
length = []
while len(G) > 2:
v1, v2 = choose_random_key(G)
G[v1].extend(G[v2])
for x in G[v2]:
G[x].remove(v2)
G[x].append(v1)
while v1 in G[v1]:
G[v1].remove(v1)
del G[v2]
for key in G.keys():
length.append(len(G[key]))
return length[0]
def operation(n):
i = 0
count = 10000
while i < n:
data = copy.deepcopy(G)
min_cut = karger(data)
if min_cut < count:
count = min_cut
i = i + 1
return count
print(operation(100))
正如Phil所说，我必须运行我的程序100次。代码中还有一个更正是：
for edge in edgelist:
if edge[0] == edge[1]:
edgelist.remove(edge)
这部分代码没有正确消除自循环。所以我不得不改变代码：
for i in range((len(edgelist)-1),-1,-1):
if edgelist[i][0] == edgelist[i][1]:
edgelist.remove(edgelist[i])
这条线不需要。因为目标节点将自动更改为自循环，它将被删除。
edgelist.remove(target_edge)
然后如前所述，程序循环了100次，我通过随机化得到了最小的削减。 :)
在看这篇文章的答案时，我偶然发现了Joel的评论。根据Karger的算法，必须随机均匀地选择边缘。你可以找到我的实施，这是基于奥斯卡的答案和乔尔的评论如下：
class KargerMinCutter:
def __init__(self, graph_file):
self._graph = {}
self._total_edges = 0
with open(graph_file) as file:
for index, line in enumerate(file):
numbers = [int(number) for number in line.split()]
self._graph[numbers[0]] = numbers[1:]
self._total_edges += len(numbers[1:])
def find_min_cut(self):
min_cut = 0
while len(self._graph) > 2:
v1, v2 = self._pick_random_edge()
self._total_edges -= len(self._graph[v1])
self._total_edges -= len(self._graph[v2])
self._graph[v1].extend(self._graph[v2])
for vertex in self._graph[v2]:
self._graph[vertex].remove(v2)
self._graph[vertex].append(v1)
self._graph[v1] = list(filter(lambda v: v != v1, self._graph[v1]))
self._total_edges += len(self._graph[v1])
self._graph.pop(v2)
for edges in self._graph.values():
min_cut = len(edges)
return min_cut
def _pick_random_edge(self):
rand_edge = randint(0, self._total_edges - 1)
for vertex, vertex_edges in self._graph.items():
if len(vertex_edges) <= rand_edge:
rand_edge -= len(vertex_edges)
else:
from_vertex = vertex
to_vertex = vertex_edges[rand_edge]
return from_vertex, to_vertex
请注意，我的回复是在Python3中，因为这篇文章上次收到回复已经有几年了。
进一步迭代@sestus上面的有用答案，我想解决三个特性：
from random import randint
from math import log
class KargerMinCut():
# 0: Initialize graph
def __init__(self, graph_file):
# 0.1: Load graph file
self.graph = {}
self.total_edges = 0
self.vertex_count = 0
with open(graph_file, "r") as file:
for line in file:
numbers = [int(x) for x in line.split('\t') if x!='\n']
vertex = numbers[0]
vertex_edges = numbers[1:]
self.graph[vertex] = vertex_edges
self.total_edges+=len(vertex_edges)
self.vertex_count+=1
self.supervertices = {}
for key in self.graph:
self.supervertices[key] = [key]
# 1: Find the minimum cut
def find_min_cut(self):
min_cut = 0
while len(self.graph)>2:
# 1.1: Pick a random edge
v1, v2 = self.pick_random_edge()
self.total_edges -= len(self.graph[v1])
self.total_edges -= len(self.graph[v2])
# 1.2: Merge the edges
self.graph[v1].extend(self.graph[v2])
# 1.3: Update all references to v2 to point to v1
for vertex in self.graph[v2]:
self.graph[vertex].remove(v2)
self.graph[vertex].append(v1)
# 1.4: Remove self loops
self.graph[v1] = [x for x in self.graph[v1] if x != v1]
# 1.5: Update total edges
self.total_edges += len(self.graph[v1])
self.graph.pop(v2)
# 1.6: Update cut groupings
self.supervertices[v1].extend(self.supervertices.pop(v2))
# 1.7: Calc min cut
for edges in self.graph.values():
min_cut = len(edges)
# 1.8: Return min cut and the two supervertices
return min_cut, self.supervertices
# 2: Pick a truly random edge:
def pick_random_edge(self):
rand_edge = randint(0, self.total_edges-1)
for vertex, vertex_edges in self.graph.items():
if len(vertex_edges) < rand_edge:
rand_edge -= len(vertex_edges)
else:
from_vertex = vertex
to_vertex = vertex_edges[rand_edge-1]
return from_vertex, to_vertex
# H.1: Helpful young man who prints our graph
def print_graph(self):
for key in self.graph:
print("{}: {}".format(key, self.graph[key]))
graph = KargerMinCut('kargerMinCut.txt')
def full_karger(iterations):
graph = KargerMinCut('kargerMinCut.txt')
out = graph.find_min_cut()
min_cut = out[0]
supervertices = out[1]
for i in range(iterations):
graph = KargerMinCut('kargerMinCut.txt')
out = graph.find_min_cut()
if out[0] < min_cut:
min_cut = out[0]
supervertices = out[1]
return min_cut, supervertices
out = full_karger(100)
print("min_cut: {}\nsupervertices: {}".format(out[0],out[1]))