Ошибка при реализации Karger Min Cut в Python 2.7

Question

Я столкнулся с тупиком при реализации алгоритма Karger Min Cut в Python. Я сломал себе голову, но до сих пор не могу понять, почему моя реализация не работает, хотя она отлично работает с карандашом и бумагой ...

Рассмотрим график с четырьмя узлами 1, 2, 3, 4 и пятью краями

[1, 2], [1, 3], [2, 3], [2, 4], [3, 4].

В питона, я представлял их двумя списками:

nodes = [1, 2, 3, 4] 
edges = [[1, 2], [1, 3], [2, 3], [2, 4], [3, 4]] 

Моя идея: случайным образом выбрать ребро, скажем [1, 3], свернуть его, удалить node = 3 из списка узлов, как если 3 сливается в 1 и, удалите край [1, 3] из списка ребер.

Теперь два списка выглядит следующим образом:

nodes = [1, 2, 4] 
edges = [[1, 2], [2, 3], [2, 4], [3, 4]] 

В 3 слит в 1, список ребер дополнительно обновлен до

edges = [[1, 2], [2, 1], [2, 4], [1, 4]] 

, изменяя все 3 в списке результирующих кромок 1 .

Это завершает первый цикл.

Во втором цикле, предположим, что ребро [1, 2] случайным образом выбирается из списка ребер, затем повторите описанные выше шаги, которые я получил так что

nodes = [1, 4] 
edges = [[2, 1], [2, 4], [1, 4]] 

который далее изменены, чтобы [[1, 1], [1, 4], [1, 4]]. Так как [1, 1] указывает на замкнутый контур, он удаляется, и результирующий список ребер для этого раунда равен [[1, 4], [1, 4]]

Поскольку число узлов равно двум, процесс заканчивается и число минимальных разрезов равно 2, длина конечных ребер список.

Так моя реализация в Python выглядит следующим образом:

import numpy as np 


nodes = [] 
edges = [] 


f = open("kargerMinCut.txt", "r") 
# The txt file has the form of an adjacency list 
# The link to the txt file is at the very end   

for l in f: 
    v = l.split() 
    # The first element of each line is a (distinct) 
    # vertex and is appended to nodes list.  
    nodes.append(int(v[0])) 
    for u in v[1:]: 
     # Edges list has the form as described in my 4 nodes example 
     # above, which is unlike what in an typical adjacency list for 
     # an undirected graph is. Here, if node 1 and node 2 share 
     # an edge, then edge [1, 2] only appears once in the "edges" 
     # list, edge [2, 1] is not, which is why I used "set" below. 
     edge = [int(v[0])] 
     edge.append(int(u)) 
     count = 0 
     for edg in edges: 
      if (set(edg) == set(edge)): 
       count += 1 
     if (count == 0): 
      edges.append(edge) 

f.close() 


while (len(nodes) > 2): 
    # Number of current edges 
    m = len(edges) 
    # Choose a random edge uniformly 
    idx = np.random.randint(m) 
    edgeChosen = edges[idx] 
    # Two corresponding nodes of the chosen edge 
    i = edgeChosen[0] 
    j = edgeChosen[1] 

    # Remove the second one from nodes list 
    nodes.remove(j) 
    # Remove the chosen edge from edges list 
    del edges[idx] 

    # Change all "j"s to "i" 
    for ed in edges: 
     for e in ed: 
      if e == j: 
       e = i 

    # Remove those [i, i] edges (self loop) 
    for ed in edges[:]: 
     if len(set(ed)) == 1: 
      edges.remove(ed) 


print len(edges) 

Это только один прогон алгоритма Karger Min Cut. Хотя те, для циклов в цикле while неэффективны, я просто хочу попробовать эту идею. Я экспериментировал с приведенным выше кодом на входе с 200 узлами и ребрами 2000+.

Но независимо от того, что я сделал, Python выдает следующую ошибку после успешного удаления пары узлов и ребер:

nodes.remove(j) 
ValueError: list.remove(x): x not in list 

который смешно. Если x не находится в списке узлов, значит, x является одним из «j», ранее включенным в выбранное ребро, и либо был удален, либо изменен на соответствующий «i».

Однако я не могу найти, что не так с моим кодом. Я что-то упускаю? Есть идеи на это? Большое спасибо.

Ссылка на файл данных (большое спасибо nischayn22 на GitHub): https://github.com/nischayn22/PythonScripts/blob/master/kargerMinCut.txt

Answer 1

Фактическая часть кода делает ошибку в

edgeChosen = edges[idx] 
i = edgeChosen[0] 
j = edgeChosen[1] 

j не в узлах.

Если вы разместите свой полный код, мы сможем помочь.

Answer 2

Вот довольно рудиментарная рабочая версия. Этот код можно улучшить многими способами, но он работает и должен указывать на то, как правильно все это делать.

from random import randint 

nodes = [1,2,3,4] 
edges = [[1, 2], [1, 3], [2, 3], [2, 4], [3, 4]] 


while (len(nodes) > 2): 
    target_edge = edges[randint(0, len(edges) - 1)] 
    replace_with = target_edge[0] 
    num_to_replace = target_edge[1] 
    for edge in edges: 
     if(edge[0] == num_to_replace): 
      edge[0] = replace_with 
     if(edge[1] == num_to_replace): 
      edge[1] = replace_with 
    edges.remove(target_edge) 
    nodes.remove(num_to_replace) 
    #remove self loops 
    for edge in edges: 
     if(edge[0] == edge[1]): 
      edges.remove(edge) 
    print(edges) 

print(nodes) 
print(edges)