Параллельная заливка сети ⇐ Python

[Anonymous]

Я пытаюсь создать программу, содержащую список объектов узлов с классом:

Код: Выделить всё

class Node():
def __init__(self):
self.connections = []
self.label = None

Здесь элементами связей будут другие объекты узлов. Цель состоит в том, чтобы выполнить заливку списка узлов так, чтобы каждый узел заканчивался меткой, указывающей, частью какой подключенной сети он является. Текущий код выглядит следующим образом:

Код: Выделить всё

import multiprocessing as mp
import random

def flood_fill_labeling(node_list):
n = len(node_list)
L = [i for i in range(0,n)]
i = 1
while len(L)>0:
l = random.choice(L)
node_list[l].label = i
L.remove(l)
# Recursion here (if node has an edge)
if len(node_list[l].connections)>0:
L = flood_recursion(node_list[l].connections,i,L,node_list,1)
# End recursion
i+=1

def flood_recursion(connected_nodes,i,L,node_list,depth):
# Used to fill connected components in flood fill
if len(connected_nodes)==0:
pass
else:
next_rec=[]
for node in connected_nodes:
# If already labelled, pass
if node.label != None:
pass
else:
# Apply label and remove index from L
node.label = i
L.remove(node_list.index(node))
# Append connections to next recursion of flood fill
for next_node in node.connections:
next_rec.append(next_node)
# Flood fill the next set of connections
# If at depth 1, i.e. Just started recursion, split into parallel processes
if depth == 1:
L = mp.Pool().starmap(flood_recursion,[([j],i,L,node_list,depth+1) for j in next_rec])
L = list(set.intersection(*map(set,L)))
# Current issue is each process is returning a different variation of L. Intersection doesn't seem to resolve this
else:
L = flood_recursion(next_rec,i,L,node_list,depth+1)
return L

По сути, вы выбираете индекс узла, который еще не получил метку, случайным образом, присваиваете ему метку и рекурсивно помечаете соединяющиеся узлы до тех пор, пока все подключенные узлы не будут иметь одинаковую метку. >
Алгоритм работает для последовательного случая, но когда я пытаюсь распараллелить задачу, я сталкиваюсь с проблемами.
После завершения процессов возвращается L как двумерный список различных результатов, как и ожидалось, но их пересечение или объединение, похоже, не решает проблему, поскольку многие узлы в конце остаются без меток.
Любая помощь в этом ценится.

Подробнее здесь: https://stackoverflow.com/questions/790 ... n-parallel