Я пытаюсь реализовать Krager Min. Алгоритм cut на питоне для решения следующей задачи. Эта задача взята из курса edx Стэнфорда, Алгоритмы: проектирование и анализ, часть 1.
Файл содержит представление списка смежности простого неориентированного графа. Имеется 200 вершин, помеченных от 1 до 200. Первый столбец в файле представляет собой метку вершины, а конкретная строка (другие записи, кроме первого столбца) сообщает обо всех вершинах, к которым примыкает вершина. Так, например, 6-я строка выглядит так: 6 155 56 52 120 ....... Это просто означает, что вершина с меткой 6 смежна (т.е. имеет общее ребро) с вершинами с метками 155,56, 52 120, ...... и т. д.
запустите алгоритм рандомизированного сокращения для задачи минимального разреза и используйте его на приведенном выше графике для вычисления минимального разреза.
Он включает следующий список смежности: https://pastebin.pl/view/39b087f8
Вот что я закодировал в python - я знаю, что реализация наивна, но я просто хочу сделать ее правильно, прежде чем она будет оптимизирована.
import random
import copy
with open('Contraction hwk.txt') as f: #Please input the correct file path
proto = f.readlines()
proto2 = [(x.replace('\t',' ').strip('\n')).split() for x in proto]
adjl = [[int(x) for x in i] for i in proto2]
solnset = []
for x in range(1000):#Repeated a 100 times cause the algo is not always correct
wadjl = copy.deepcopy(adjl)
nodes = list(range(1,len(adjl)+1))
while len(nodes) > 2:
randnodeval = random.choice(nodes) #Select a random node
randnode = wadjl[randnodeval-1] #Assign the random node to a var --> randnode
randedgeval = random.choice(randnode[1:]) # Picks another random node(edge node) that is adjacent to the initial this will contract with the original random node
if randedgeval == randnodeval:
continue
for node in wadjl[randedgeval-1][1:]:#This loop will go to all nodes adjacent to the edge node and replace the value of the edge node with the random node
if node == randnodeval:#If the node is the same as the random node it removes the node as an adjacent node (Deletion of edge node from random node)
modnode = wadjl[node-1][1:]
edgevalnode = modnode.index(randedgeval)
wadjl[node-1].pop(edgevalnode+1)
continue
modnode = wadjl[node-1][1:]
edgevalnode = modnode.index(randedgeval)
wadjl[node-1][edgevalnode+1] = randnodeval
randnodeidx = wadjl[randedgeval-1][1:].index(randnodeval)#This yeilds the index of the random node in the adjaceny list of the edge node
wadjl[randedgeval-1].pop(randnodeidx+1)#The random node is removed from that list(Deletion of random node from edgenode)
randnode.extend(wadjl[randedgeval-1][1:])#The adjacency list of the edge node is merged with that of the random node
del wadjl[randedgeval-1][1:]#The edge node is deleted
try:#repeates/edges to itself are removed from the random node
repeats = [i for i,x in enumerate(randnode) if x == randnodeval]
for repeate in repeats:
randnode.pop(repeat)
except:
pass
#Edge node is removed from the nodes list
noderemove = nodes.index(randedgeval)
nodes.pop(noderemove)
for entry in wadjl:
if len(entry) > 1:
minc = len(entry) - 1 #edges in min cut case
solnset.append(minc) #append solution to solution set
break
# print(solnset)
print(min(solnset))
Основываясь на некоторых поисковых запросах в Интернете, ответ кажется равным 17. Я получаю ответ 20, более того, я не думаю, что моя реализация алгоритма верна, поскольку набор решений слишком разнообразен. Я считаю, что при правильной реализации решение должно довольно часто появляться в этом наборе.