1

我已经成功地使用以下算法在约 900 个节点的图形上完成了路径长度为 10 的所有路径数据。但是，我想将其扩展到更大的图表，我想知道是否可以做进一步的优化。到目前为止，我有：

  • 在节点完成它的 DFS 后，路径将保存到哈希表中。如果遇到所述节点，则附加来自哈希表的路径，因此不会重复工作。
  • 节点按其程度排序（最高优先）。这样最有可能遇到的节点将已经在哈希表中。

具体算法：构建化学物质（节点）和反应（边缘）网络并创建路径，以便以后可以更快地搜索理论路径，然后可以进行实验测试。

该算法基于 networkxall_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

如果有人对进一步优化算法有任何建议，将不胜感激。

4

1 回答 1

2

首先——测量是你最好的朋友。如果您没有收集有关算法需要多长时间的信息，那么您就无法知道更改是否有帮助。您缓存结果的想法很聪明，但您应该检查有无缓存的时间，以确保它确实有帮助。

特别是您的代码中我可以看到改进空间的一部分是if (visited not in uniqueTreePaths).... 您正在检查列表是否包含在列表列表中。我不确定解决此问题的最佳方法是什么（同样，从您的代码中收集计时数据），但一种可能性是将路径表示为字符串而不是列表，从而允许它们通过哈希存储。

于 2013-09-04T23:19:16.847 回答