在 Karger 的最小割算法中，消除图中的自环

Question

我正在尝试实现 Karger's algorithm 以查找图的最小割。关键部分是 contract 方法，它执行一次收缩。到目前为止，这是我的实现（带有 'test'）：

import pytest
import random


class Graph(object):
    def __init__(self, G):
        self.G = G      # Adjacency list

    @property
    def edges(self):
        E = list()
        for vertex in self.G:
            for adjacent_vertex in self.G[vertex]:
                if vertex < adjacent_vertex:
                    E.append([vertex, adjacent_vertex])
        return E

    def randomized_contract(self):
        edge = random.choice(self.edges)
        self.contract(edge)

    def contract(self, edge):
        vertex, adjacent_vertex = edge
        self.G[vertex].remove(adjacent_vertex)
        self.G[adjacent_vertex].remove(vertex)
        self.G[vertex] += self.G[adjacent_vertex]
        del self.G[adjacent_vertex]
        for v in self.G:
            for n, av in enumerate(self.G[v]):
                if av == adjacent_vertex:
                    self.G[v][n] = vertex
        self.remove_self_loops()

    def remove_self_loops(self):
        for vertex in self.G:
            for n, adjacent_vertex in enumerate(self.G[vertex]):
                if adjacent_vertex == vertex:
                    del self.G[vertex][n]

    def contract_till_cut(self):
        while len(self.G) > 2:
            self.randomized_contract()


def test_contract_till_cut():
    graph = Graph({1: [2,3], 2: [1,3], 3: [1,2,4], 4: [3]})
    graph.contract_till_cut()
    print(graph.G)


if __name__ == "__main__":
    pytest.main([__file__, "-s"])

我的问题是，在一个特定的运行上（您可能需要运行几次才能重现此结果），获取邻接列表

{1: [1, 4], 4: [1]}

其中节点 1 有一个 'self-loop' - 也就是说，它出现在它自己的邻接列表中。我不明白这是怎么发生的；对 contract 的每次调用都以对 remove_self_loops 的调用结束，这似乎有效。谁能发现这段代码中的错误？

Answer 1

问题出在 remove_self_loops 方法上：它在仅删除一个自循环后终止。我将其替换为以下内容：

def remove_self_loops(self):
    for vertex in self.G:
        self.G[vertex] = [av for av in self.G[vertex] if not av == vertex]

现在在 'problem' 案例之后（对应于沿边缘 [1,2] 和 [1,3] 连续收缩）我得到了预期的（最小）削减：

{1: [4], 4: [1]}

在 Karger 的最小割算法中，消除图中的自环

In Karger's min cut algorithm, eliminating self-loops in a graph

python

algorithm

graph-theory

kargers-algorithm