pythonでnetworkxを使用して効率的にすべてのパスを生成

Question

かなり大きなネットワーク（20,000+アーク）のすべての起点からすべての宛先まで、最大6つのノードを持つすべてのパスを生成しようとしています。私はnetworkxとpython 2.7を使用しています。小規模なネットワークではうまくいきますが、ネットワーク全体でこれを実行する必要があります。私はPythonでこれを行うより効率的な方法があるのだろうかと思いました。私のコードには再帰関数が含まれています（下記参照）。私はいくつかのパスをメモリに保存することを考えているので、他のパスのためにパスを作成しないようにしていますが、どのように高速化できるかはわかりません。今は数日でさえ完了できません。 3時間から4時間は私のプロジェクトにとってうまくいくはずです。

ここに私が作成したサンプルがあります。私が説明のために追加した印刷機能を自由に無視してください。サンプル入力ファイルもここにあります。 input

import networkx as nx 
import pandas as pd 
import copy 
import os 

class ODPath(object):  
    def __init__(self,pathID='',transittime=0,path=[],vol=0,OD='',air=False,sortstrat=[],arctransit=[]): 
     self.pathID = pathID 
     self.transittime = transittime 
     self.path = path 
     self.vol = vol 
     self.OD = OD 
     self.air = air 
     self.sortstrat = sortstrat # a list of sort strategies 
     self.arctransit = arctransit # keep the transit time of each arc as a list 
    def setpath(self,newpath): 
     self.path = newpath 
    def setarctransitpath(self,newarctransit): 
     self.arctransit = newarctransit 
    def settranstime(self,newtranstime): 
     self.transittime = newtranstime 
    def setpathID(self,newID): 
     self.pathID = newID 
    def setvol(self,newvol): 
     self.vol = newvol 
    def setOD(self,newOD): 
     self.OD = newOD 
    def setAIR(self,newairTF): 
     self.air = newairTF 
    def setsortstrat(self,newsortstrat): 
     self.sortstrat = newsortstrat 

def find_allpaths(graph, start, end, pathx=ODPath(None,0,[],0,None,False)): 
    path = copy.deepcopy(pathx) #to make sure the original has not been revised 
    newpath = path.path +[start]  
    path.setpath(newpath) 
    if len(path.path) >6: 
     return [] 
    if start == end: 
    return [path] 
    if (start) not in graph: #check if node:start exists in the graph 
     return [] 
    paths = [] 
    for node in graph[start]: #loop over all outbound nodes of starting point 
     if node not in path.path: #makes sure there are no cycles 
      newpaths = find_allpaths(graph,node,end,path) 
      for newpath in newpaths: 
       if len(newpath.path) < 7: #generate only the paths that are with at most 6 hops  
        paths.append(newpath) 
    return paths 
def printallpaths(path_temp): 
map(printapath,path_temp) 
def printapath(path): 
print path.path 

filename='transit_sample1.csv' 
df_t= pd.read_csv(filename,delimiter=',') 
df_t = df_t.reset_index() 
G=nx.from_pandas_dataframe(df_t, 'node1', 'node2', ['Transit Time'],nx.DiGraph()) 
allpaths=find_allpaths(G,'A','S') 
printallpaths(allpaths) 

本当にありがとうございます。

Answer 1

私は実際にnetworkxを使用して以前に書いたアルゴリズムの最適化についてpreviouslyという質問をしました。本質的には、再帰的な関数から離れて、私のように暗記を使用するソリューションに移行することです。

multiple coresを使用するか、次のノードを選んで度などの基準に基づいてトラバースするなど、さらに最適化を行うことができます。