NetworkX all_simple_paths дает ошибку памяти

Question

Я использую NetworkX библиотека для поиска пути для моей задачи. Мне, конечно же, нужно найти простые пути. Вот пример кода, который я использую:

paths = list(nx.all_simple_paths(G, startnode, endnode)) 

Вот ошибка, при которой консоль отображает:

Traceback (most recent call last): 
File "run_duc.py", line 130, in <module> 
main() 
File "run_duc.py", line 78, in main 
m1.main() 
File "C:\Users\User\Desktop\all_model_run_script\abstractive_ilp\main.py", line 119, in main 
paths = mygraph.generate_graph(mytext, mystartnode, myendnode, financial_corpus) 
File "C:\Users\User\Desktop\all_model_run_script\abstractive_ilp\graph_node.py", line 241, in generate_graph 
paths = self.find_paths(G, self.START, self.END, financial_corpus) 
File "C:\Users\User\Desktop\all_model_run_script\abstractive_ilp\graph_node.py", line 153, in find_paths 
paths = list(nx.all_simple_paths(G, startnode, endnode)) 
MemoryError 

Answer 1

Я думаю, это потому, что ваш график слишком большой. Смотрите documentation for all_simple_paths():

Этот алгоритм использует модифицированную поиска в глубину, чтобы генерировать пути. Один путь можно найти в O(V+E), но число простых путей на графике может быть очень большим, например, . O(n!) в полный график порядка n.

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

Вы можете попробовать тот же метод с уменьшением количества ребер в вашем графике, используя remove_edges_from():

In [20]: import networkx as nx 

In [21]: g = nx.Graph() 

In [22]: g.add_path(range(20)) 

In [23]: g.edges() 
Out[23]: 
[(0, 1), (1, 2), (2, 3), (3, 4), (4, 5), (5, 6), (6, 7), (7, 8), (8, 9), (9, 10), (10, 11), (11, 12), (12, 13), (13, 14), (14, 15), (15, 16), (16, 17), (17, 18), (18, 19)] 

In [24]: g.remove_edges_from(g.edges()[0:10]) 

In [25]: g.edges() 
Out[25]: 
[(10, 11), (11, 12), (12, 13), (13, 14), (14, 15), (15, 16), (16, 17), (17, 18), (18, 19)] 

Если он работает с меньшим количеством ребер, то это означает, что вы не имеете достаточно памяти в первую очередь ,