0

我正在尝试实现Karger 算法来查找图形的最小切割。关键部分是contract执行单次收缩的方法。到目前为止，这是我的实现（带有“测试”）：

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 有一个“自循环”——也就是说，它出现在自己的邻接列表中。我不明白这怎么会发生。每次调用都以似乎有效contract的调用结束。remove_self_loops谁能发现这段代码中的错误？

4

1 回答 1

0

问题出在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]

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

{1: [4], 4: [1]}
于 2017-08-16T22:37:58.620 回答