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)] 

如果用更少的邊緣工作，那麼就意味着你沒有足夠的內存在首位。