代码之家 › 专栏 › 技术社区 › Infinity77

Python:有向图中的所有简单路径

networkx python

Infinity77 · 技术社区 · 7 年前

我正在研究(许多)有向图不

我实现了这个递归函数:

import timeit

def all_simple_paths(adjlist, start, end, path):

    path = path + [start]

    if start == end:
        return [path]

    paths = []

    for child in adjlist[start]:

        if child not in path:

            child_paths = all_simple_paths(adjlist, child, end, path)
            paths.extend(child_paths)

    return paths


fid = open('digraph.txt', 'rt')
adjlist = eval(fid.read().strip())

number = 1000
stmnt  = 'all_simple_paths(adjlist, 166, 180, [])'
setup  = 'from __main__ import all_simple_paths, adjlist'
elapsed = timeit.timeit(stmnt, setup=setup, number=number)/number
print 'Elapsed: %0.2f ms'%(1000*elapsed)

在我的电脑上,我每次迭代平均得到1.5毫秒。我知道这是一个小数字,但我必须做这个手术非常

如果您感兴趣,我在这里上传了一个包含邻接列表的小文件:

adjlist

我使用邻接列表作为输入,来自NetworkX有向图表示。

对算法的改进有什么建议(即,它必须是递归的吗?)或者我可能尝试的其他方法非常受欢迎。

非常感谢。

安德里亚。

1 回复 | 直到 7 年前

CtheSky 7 年前

通过在此处缓存共享子问题的结果,可以节省时间而不更改算法逻辑。

all_simple_paths(adjlist, 'A', 'D', []) 在下图中,将计算 all_simple_paths(adjlist, 'D', 'E', []) 多次:

lru_cache 用于此任务。它使用散列来记忆参数,因此您需要更改 adjList 和 path tuple 自从 list 不可散列。

import timeit
import functools

@functools.lru_cache()
def all_simple_paths(adjlist, start, end, path):

    path = path + (start,)

    if start == end:
        return [path]

    paths = []

    for child in adjlist[start]:

        if child not in path:

            child_paths = all_simple_paths(tuple(adjlist), child, end, path)
            paths.extend(child_paths)

    return paths


fid = open('digraph.txt', 'rt')
adjlist = eval(fid.read().strip())

# you can also change your data format in txt
adjlist = tuple(tuple(pair)for pair in adjlist)

number = 1000
stmnt  = 'all_simple_paths(adjlist, 166, 180, ())'
setup  = 'from __main__ import all_simple_paths, adjlist'
elapsed = timeit.timeit(stmnt, setup=setup, number=number)/number
print('Elapsed: %0.2f ms'%(1000*elapsed))

这种方法应该只在有很多共享子问题的情况下才有效。

推荐文章

July · 如何定义数字间隔,然后四舍五入

1 年前

Community wiki · 对象名称前的单下划线和双下划线的含义是什么?

1 年前