我使用下面的算法来完成〜900个节点的图形高达10路长全路径数据是成功的。 但是，我想将其放大到更大的图形，如果有进一步的优化，我可以做我不知道。 到目前为止，我有：
- 后一个节点已经完成了它的DFS路径被保存到一个哈希表。 应该说，节点会遇到，从哈希表的路径被追加所以工作就不重复了。
- 节点由它们的程度（从高到低）排序。 这样，节点最有可能遇到的将已经在哈希表。
在具体的算法：建立化学品（节点）和反应（边缘）的一个网络，所以它可在以后被搜索的理论路径快得多，这些以后可以实验测试创建路径。
该算法中是基于networkx all_simple_paths算法：
def _all_simple_paths_graph(DG, cutoff):
memorizedPaths = {}
nlist = []
#sorts nodes into highest -> lowest degree order
degreelist = sorted(DG.degree_iter(),key=itemgetter(1),reverse=True)
for i in degreelist:
t = re.findall("'\s*([^\"]*)\s*'",str(i))
nlist.extend(t)
with open ('PythonOutput.txt', "wb") as csvfile:
writer = csv.writer(csvfile, delimiter=' ', quotechar='|')
numberdone = 0
#for each node start a new DFS
for source in nlist:
print source
print numberdone
numberdone += 1
uniqueTreePaths = []
if cutoff < 1:
return
visited = [source]
stack = [iter(DG[source])]
while stack:
children = stack[-1]
child = next(children, None)
if child is None:
stack.pop()
visited.pop()
#If a node has been searched before, append its paths
elif child in memorizedPaths:
for path in memorizedPaths[child]:
newPath = (tuple(visited) + tuple(path))
if (len(newPath) <= cutoff) and (len(set(visited) & set(path)) == 0):
uniqueTreePaths.append(newPath)
continue
elif len(visited) < cutoff:
if child not in visited:
visited.append(child)
stack.append(iter(DG[child]))
if visited not in uniqueTreePaths:
uniqueTreePaths.append(tuple(visited))
else: #len(visited) == cutoff:
if (visited not in uniqueTreePaths) and (child not in visited):
uniqueTreePaths.append(tuple(visited + [child]))
stack.pop()
visited.pop()
#for each node, write to disk to save RAM
for path in uniqueTreePaths:
writer.writerow(path)
#add paths for each node to the hash table
memorizedPaths[source] = uniqueTreePaths
如果任何人有进一步的优化算法任何建议，将不胜感激。
