Реализация минимального среза Karger в python 2.7 не дает правильных срезов - PullRequest
Новая
       11

Реализация минимального среза Karger в python 2.7 не дает правильных срезов

0 голосов
/ 24 июня 2018 
 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) также как min разрезают пары в отдельных итерациях алгоритма.

Так что моя проблема в том, что хотя minCut i.e 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

1 Ответ

0 голосов
/ 24 июня 2018

Я не думаю, что правильно говорить "правильный срез (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 являются просто представителями для двух сторон разреза.

Вам нужно будет адаптировать свой код так, чтобы он корректировал метки узлов, когда он сжимает ребро, и объединяет два узла в один. В конце вы можете прочитать вырезку из меток двух сохранившихся узлов и вырезку из краев, которые соединяют два набора узлов.

...