使用python中的networkx以有效的方式生成所有路径 [英] Generate all paths in an efficient way using networkx in python
问题描述
我正在尝试在一个相当大的网络(20,000个以上的弧)中生成从每个起点到每个目的地最多具有6个节点的所有路径.我正在使用networkx和python 2.7.对于小型网络,它运行良好,但是我需要在整个网络中运行它.我想知道是否有更有效的方法可以在python中做到这一点.我的代码包含一个递归函数(见下文).我正在考虑将某些路径保留在内存中,以便不再为其他路径创建它们,但是我不确定如何快速完成它.现在,即使几天之内也无法完成. 3-4小时对我的项目来说应该没问题.
I am trying to generate all paths with at most 6 nodes from every origin to every destination in a fairly large network (20,000+ arcs). I am using networkx and python 2.7. For small networks, it works well but I need to run this for the whole network. I was wondering if there is a more efficient way to do this in python. My code contains a recursive function (see below). I am thinking about keeping some of the paths in memory so that I don't create them again for other paths but I am not sure how I can accomplish it fast. right now it can't finish even within a few days. 3-4 hours should be fine for my project.
这是我创建的示例.我出于说明目的添加了打印功能,请随意忽略它们.这也是示例输入文件. 输入
Here is a sample that I created. Feel free to ignore print functions as I added them for illustration purposes. Also here is the sample input file. 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)
我将非常感谢您的帮助.
I would really appreciate any help.
推荐答案
I actually asked this question previously about optimizing an algorithm I wrote previously using networkx. Essentially what you'll want to do is move away from a recursive function, and towards a solution that uses memoization like I did.
您可以在此处进行进一步的优化,例如使用多个内核,或选择根据度数等标准遍历的下一个节点.
From here you can do further optimizations like using multiple cores, or picking the next node to traverse based on criteria such as degree.
这篇关于使用python中的networkx以有效的方式生成所有路径的文章就介绍到这了,希望我们推荐的答案对大家有所帮助,也希望大家多多支持IT屋!