在Karger的最小切割算法中，消除圖中的自循環

我試圖實現Karger's algorithm以查找圖的最小切割。關鍵部分是執行單一收縮的方法。這裏是我的執行至今（以「測試」）：在Karger的最小切割算法中，消除圖中的自循環

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，這似乎很有用。任何人都可以發現這個代碼中的錯誤？

來源

2017-08-16 Kurt Peek

我建議使用具有聯合查找結構的克魯斯卡爾實現而不是實際收縮。它更快，也更容易。 1）把每個邊緣放在它自己的集合中。 2）以隨機順序遍歷邊，合併由每條邊連接的集合，直到只有2組。 3）然後連接2組的剩餘邊是切割。 –

問題出在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-16 22:37:58

在Karger的最小切割算法中，消除圖中的自循環

回答

相關問題