logo标签列表

Python 2.7中的Karger最小割算法

pythonalgorithmmin
5

这是我为Karger最小割算法编写的代码。据我所知，我实现的算法是正确的。但是我没有得到正确的答案。如果有人可以检查一下哪里出了问题，我将不胜感激。

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)]。
6个回答
11

这段代码也可以正常工作。

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))
2
我的理解是卡格尔算法从边中均匀随机选择一条边。该算法会从节点中均匀随机选择一个节点，然后在该节点的边中均匀随机选择一条边。因此，低度节点之间的边比高度节点之间的边更容易被选择。 - Joel
@Joel和Oscar：谢谢你们，这个答案/评论真的很有帮助。我只是想分享一下，我已经回复了Joel的评论，并使用随机边选择实现了Karger算法。您可以在下面看到我的答案。 - sestus
9
所以Karger的算法是一种“随机算法”。也就是说，每次运行它都会产生一个解决方案，这个解决方案并没有任何保证是最优的。一般的做法是多次运行它，并保留最佳的解决方案。对于许多配置，有很多最佳或近似最佳的解决方案，因此你可以启发式地快速找到一个好的解决方案。
据我所见，您只运行了一次算法。因此，解决方案不太可能是最优的。尝试在for循环中运行100次，并保留最佳解决方案。
所以你的意思是除了我需要多次运行它之外，我的程序是正确的吗？ - user 3317704
2

在查看本帖答案时，我发现了Joel的评论。根据Karger算法，必须随机选择边缘。您可以在下面找到我的实现，它基于Oscar的答案和Joel的评论：

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
2

正如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次，并通过随机化得到了最小割。 :)

1
注意，我的回答是关于Python3的，因为距离上一次回答已经过去了几年。
在@sestus上面有所补充，我想要提到三个特性：
  1. Within the _pick_random_edge method of the class KarmgerMinCut(), rand_edge will ultimately match the length of vertex_edges. I adjusted the code to subtract 1 from rand_edge so rand_edge does not attempt to grab an element at a location 1 greater than the array length.
  2. Understand which vertices comprise the two subgroupings representing the minimum cut. The functions implemented upon the "supervertices" dict achieve this.

  3. Run this algorithm a large number of times (in my case, 100 times) and keep track of the smallest min_cut and its related supervertices. That's what my outside function full_karger() achieves. I am not clever enough to implement this as an internal

    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]))
0

我完全同意以上的答案。但是当我使用Python 3.x运行您的代码时，它会产生Code 1。这段代码有时候可以工作，但有时候会失败。事实上，正如@user_3317704在上面提到的，您的代码中存在一个错误：

for edge in edgelist:
    if edge[0] == edge[1]:
        edgelist.remove(edge)

在进行for-do循环时，您不应更改列表中的项目。这会导致错误。供参考，可能是：

newEdgeList = edgeList.copy();
for edge in edgeList:
    if edge[0] == edge[1]:
        newEdgeList.remove(edge);
edgeList = newEdgeList;
网页内容由stack overflow 提供, 点击上面的
可以查看英文原文，
原文链接