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!) in order 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)] 

如果用更少的边缘工作，那么就意味着你没有足够的内存在首位。