python - Karger 在 python 2.7 中的最小切割实现没有给出正确的切割

Question

 from random import randint
 from collections import defaultdict

 ######################

 def getGraph(filename):
 '''
 The function takes a txt file as input and returns
 the Graph with 1st element of each row as a vertex.
 '''
     with open(filename, 'r') as f_in:
         G = defaultdict(list)
         for row in f_in:
             row = row.split()
             G[row[0]] = row[1 : ]
     return G

 ######################

 def getVEPair(range):
 '''
 The function takes the range as input and returns a
 pair of random integers.
 '''
     v = randint(1, range)
     e = randint(1, range)
     return v, e

 ######################

 def removeVEPair(G, V, E):
 '''
 The function takes Graph, Vertex  and  Edge as input
 and removes this pair from the Graph. The function then
 returns the resulting Graph.
 '''
     while E in G[V]:
         G[V].remove(E)
     return G

 ######################

 def contractNodes(G, V, E):
 '''
 The function takes a Graph, vertex and edge as the input
 and contracts the two nodes which the edge connects. The
 function then returns the resulting Graph.
 '''
     edges = G[E]
     for edge in edges:

         if edge != V:
             G[V].append(edge)
     return G

 ######################

 def removeNode(G, V, E):
 '''
 The function intakes the graph and the node to be deleted.
 The function deletes the node and updates all instances of
 the deleted node in the Graph.
 The function then returns the resulting Graph.
 '''
     del G[E]
     for Vertex in G:
         while E in G[Vertex]:
             G[Vertex].remove(E)
             if V != Vertex:
                 G[Vertex].append(V)
     return G

 ######################

 def kargerMinCut():
 '''
 The function takes a graph as input and returns the min cut
 of the graph.
 '''
     minCut = []
     for i in range(0, 100):
         G = getGraph('dataGraph.txt')
         while(len(G) > 2):
             v, e = getVEPair(8)
             V = str(v)
             E = str(e)
             keys = G.keys()
             if V in keys and E != V:
                 if E in G[V]:
                     G = removeVEPair(G, V, E)
                     G = contractNodes(G, V, E)
                     G = removeNode(G, V, E)
                 else:
                     continue
         print G
         for v in G:
             minCut.append(len(G[v]))
             break
     return minCut
 ######################

 minCut = kargerMinCut()
 print '######################'
 print minCut
 print min(minCut)

我通过将下面的数据保存在 dataGraph.txt 文件中来执行上面的代码。数字即最小切割是 1，正确切割是 (4,5)，但我得到 (1,7)，(3,6)，(8,4)，(1,5)，(3,7 ), (4,5) 也作为算法的单独迭代中的最小切割对。

所以我的问题是，虽然 minCut 即 1 是正确的，但为什么我将这些其他对作为 minCuts？

在下面的数据中，每行的第一个元素表示一个节点，该行的其余元素表示第一个元素连接到的节点。例如 1 连接到 3、4 和 2。

1 3 4 2
2 1 4 3
3 1 2 4
4 5 3 2 1
5 4 8 6 7
6 8 7 5
7 5 8 6
8 5 7 6

Answer 1

我认为说“正确的切割是 (4,5)”是不正确的。

我认为更正确的说法是“正确的切割是两组 {1, 2, 3, 4} 和 {5, 6, 7, 8}”。切割是将图形顶点分成两部分，而切割集(这似乎是您所指的)是连接这两个集合的边集。对于您的图表，对应于最小切割的切割集是 {(4, 5)}。

为什么会得到“不正确”的结果，例如 (1, 5)？这是因为当您收缩一条边并将两个节点合并为一个节点时，您不会重新标记合并的节点。合并的节点保留两个节点之一的名称。当你到达终点并且算法恰好找到大小为 1 的切割时，两个幸存节点的标签是最小切割每一侧的节点的标签，这些节点碰巧没有被删除。正如我所说，正确的切割是 ({1, 2, 3, 4}, {5, 6, 7, 8}):值 1 和 5 只是切割两侧的代表。

您需要调整代码，以便在收缩边并将两个节点合并为一个节点时调整节点标签。最后，您可以从两个幸存节点的标签中读取切割，并从连接两组节点的边读取切割集。