Параллельные вычисления в графах

Question

Я хочу провести некоторый анализ графов, чтобы найти все возможные простые пути между всеми парами узлов в графе. С помощью библиотеки Networkx я могу использовать DFS, чтобы найти все возможные пути между 2 узлами с помощью этой функции:

nx.all_simple_paths(G,source,target)

Приведенный ниже код выполняется без какой-либо рабочей нагрузки, поскольку мой игрушечный пример содержит только 6 узлы в графе. Однако в моей реальной задаче мой граф содержит 5 213 узлов и 11 377 786 ребер, и найти все возможные простые пути в этом графе невозможно при следующем решении:

import networkx as nx
graph = nx.DiGraph()
graph.add_weighted_edges_from(final_edges_list) 

list_of_nodes = list(graph.nodes())

paths = {}

for n1 in list_of_nodes:
    for n2 in list_of_nodes:
        if n1 != n2:
            all_simple_paths = list(nx.all_simple_paths(graph,n1,n2))
            paths[n1+ "-"+n2] = all_simple_paths

Словарь "paths" содержит "n1-n2 "(исходный узел и целевой узел соответственно) в качестве ключей и список всех простых путей в качестве значений.

Вопрос в том, могу ли я использовать мультиобработку в этом сценарии, чтобы выполнить этот код в исходной задаче или нет. Мои знания о процессорах, потоках, общей памяти и ядрах процессоров очень наивны, и я не уверен, смогу ли я действительно использовать параллелизм (выполнение моих вложенных циклов параллельно) в своей задаче. Я использую сервер windows с 128 ГБ ОЗУ и 32-ядерным процессором.

PS: Тщательно изучив net (в основном StackOverFlow), я нашел решения, которые рекомендовали использовать многопоточность, а другие рекомендовали многопроцессорность. Я не уверен, понимаю ли я различие между этими двумя: |

Answer 1

Если вы хотите использовать многопоточность, тогда используйте expoolutor threadpool, чтобы отправить вызов функции потоку. Это вернет будущий объект. Future.result () вернет значение, возвращаемое вызовом. Если вызов еще не завершен, тогда этот метод будет ждать до секунд ожидания. Если вызов не будет завершен до этого времени, он вызовет TimeoutError.

with ThreadPoolExecutor() as executor:
    for n1 in list_of_nodes:
        for n2 in list_of_nodes:
            if n1 != n2:
                all_simple_paths_futures = executor.submit(nx.all_simple_paths, graph,n1,n2)
            paths[n1+ "-"+n2] = all_simple_paths_futures
try:            
    for key in paths.keys():
        # get back  results from thread
        future_obj = paths[key]
        paths[key]= list(future_obj.result())
except Exception as e:
    print(e)
    raise e

Чтобы узнать разницу между многопроцессорностью и потоками, проверьте эту ссылку: Многопроцессорность и многопоточность Python