Как эффективно найти все пути, образованные числом k узлов в ориентированном ациклическом графе?

Вот функция, которая возвращает пути заданной длины между всеми узлами в графе. Он перебирает все наборы узлов и использует networkx.all_simple_paths для получения путей.

import networkx as nx

g = nx.DiGraph()

g.add_nodes_from(['A','B','C','D','E'])

g.add_path(['A','B','C','D'])
g.add_path(['A','B','C','E'])
g.add_path(['A','C','D','E'])
g.add_path(['B','C','D','D'])

def find_paths(graph, number_nodes=4):
    paths = []
    for source in graph.nodes_iter():
        for target in graph.nodes_iter():
            if not source==target:
                p_source_target = nx.all_simple_paths(graph, 
                                                      source, 
                                                      target, 
                                                      cutoff=number_nodes-1)
                paths.extend([p for p in p_source_target if len(p)==number_nodes])
    return paths

find_paths(g)
# output:
[['B', 'C', 'D', 'E'],
 ['A', 'C', 'D', 'E'],
 ['A', 'B', 'C', 'E'],
 ['A', 'B', 'C', 'D']]

Часть вашей проблемы может заключаться в том, что если вы столкнетесь с узлом u как вторым узлом пути, то вы выполните все вычисления, чтобы найти все пути длины 3. Но затем, если вы снова встретите u как второй узел, вы повторяете все эти расчеты.

Поэтому постарайтесь избежать этого. Мы сделаем это рекурсивно, сначала вычислив все пути длины 3 (что требует вычисления путей длины 2).

def get_paths(G, n):
    '''returns a dict, paths, such that paths[u] is a list of all paths 
       of length n that start from u'''
    if n == 1: #base case, return a dict so that D[u] is a
               #list of all length 1 paths starting from u.
               #it's a boring list.
        return {u: [[u]] for u in G.nodes()}
    #if we get to here n>1 (unless input was bad)
    subpath_dict = get_paths(G,n-1)  #contains all length n-1 paths, 
                                     #indexed by first node
    path_dict = {}
    for u in G:
        path_dict[u] = []  
        for v in G.successors(u):
            path_dict[u].extend([[u]+subpath for subpath in subpath_dict[v]])
    return(path_dict)

G=nx.DiGraph()
G.add_path([1,2,3,4,5,6])
G.add_path([1,3,6,8,10])

path_dict = get_paths(G,4)
path_list = []
for paths in path_dict.values():
    path_list.extend(paths)

Количество последовательностей имеет порядок |V|*d^3, где d — средняя степень выхода узла. Исходя из того, как создается граф, d ограничено. Я полагаю, что d не очень мало (например, ‹ 5). Это означает, что для графа узлов 5M есть пути> 1G.

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

Одной из идей является алгоритм, который проходит DAG в обратном топологическом порядке и делает две вещи:

• для узла сохранить все пути, которые начинаются с этого узла длины 3,
• используя последующие пути длины 3, выведите все пути длины 4.

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

Другая идея состоит в том, чтобы сделать простой алгоритм более оптимизированным. В вашем решении есть три цикла for для каждого узла. Это означает четыре цикла for для всех путей. Обратите внимание, что каждый цикл проходит через узлы. Можно соединить первые два цикла, перебирая ребра. Это связано с тем, что каждый путь должен начинаться с одного ребра. Алгоритм такой:

for n1, n2 in DAG.edges():
  for n3 in DAG.successors(n2):
    for n4 in DAG.successors(n3):
      paths.append([n1, n2, n3, n4])

Или еще проще, сначала выбрав средний край:

for n2, n3 in DAG.edges():
  for n1, n4 in itertools.product(DAG.predecessors(n2), DAG.successors(n3)):
    paths.append([n1, n2, n3, n4])

Внешний цикл можно оптимизировать, не выбирая среднее ребро, которое начинается на исходном узле или заканчивается на целевом узле. Но это довольно быстро обнаруживается в методе product(). Возможно, эта оптимизация может помочь, не отправляя ненужные данные в другой процесс.