В настоящее время я использую graph_tool.topology.all_paths, чтобы найти все пути между двумя вершинами определенной длины, но в документации явно не указано, какой алгоритм используется.Я предполагаю, что это либо поиск в ширину (BFS), либо алгоритм Дейкстры, такой как shortest_path или all_shortest_paths?
Мой график не взвешен и направлен, поэтому есть способ выполнить мой поиск, используя all_paths параллельно, и использовать больше ядер?Я знаю, что OpenMP включен с использованием openmp_enabled() и что он настроен на использование всех 8 ядер, которые у меня есть.
Я видел, что некоторые алгоритмы, такие как DFS , не могут быть выполненыпараллельно, но я не понимаю, почему поиск по моему графику, чтобы найти все пути до определенной длины, не выполняется с использованием нескольких ядер, особенно когда на странице сравнения производительности 1011 * Graph-Tool есть тесты для кратчайшего путииспользуя несколько ядер.
Запуск graph_tool.topology.all_paths(g, source, target, cutoff=4) с использованием базовой функции:
def find_paths_of_length(graph, path_length, start_vertex, end_vertex):
savedpath=[]
for path in graph_tool.topology.all_paths(graph, start_vertex, end_vertex, cutoff=path_length):
savedpath.append(path)
использует только 1 ядро.Есть ли способ, которым это можно сделать параллельно?Моя сеть содержит порядка 50 миллионов вершин и 200 миллионов ребер, и алгоритм соответствует O (V + E) согласно документации.
Заранее спасибо