В алгоритме минимального разреза Каргера устранение самоконтроля в графе

Question

Я пытаюсь реализовать алгоритм Каргера для нахождения минимального разреза графа. Ключевой частью является 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 который, кажется, работает. Кто-нибудь может обнаружить ошибку в этом коде?

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]

Теперь после "проблемного" случая (который соответствует сокращению по краям [1,2] а также [1,3] последовательно) я получаю ожидаемое (минимальное) сокращение:

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