Python中的路径查找效率

我编写了一些代码,找到树枝状流网络中给定覆盖范围上游的所有路径.例如,如果我代表以下网络:

     4 -- 5 -- 8
    / 
   2 --- 6 - 9 -- 10
  /           \ 
 1              -- 11
  \
   3 ----7

作为一组父子对:

{(11, 9), (10, 9), (9, 6), (6, 2), (8, 5), (5, 4), (4, 2), (2, 1), (3, 1), (7, 3)}

它将返回节点上游的所有路径,例如:

get_paths(h, 1)  # edited, had 11 instead of 1 in before
[[Reach(2), Reach(6), Reach(9), Reach(11)], [Reach(2), Reach(6), Reach(9), Reach(10)], [Reach(2), Reach(4), Reach(5), Reach(8)], [Reach(3), Reach(7)]]

代码包含在下面.

我的问题是:我将这个应用于一个非常大的(例如,新英格兰)地区的每个范围,任何给定的范围可能有数百万条路径.可能没有办法避免这是一个非常长的操作,但有没有一种pythonic方式来执行此操作,以便每次运行都不会生成全新的路径？

例如,如果我运行get_paths(h,2)并找到2上游的所有路径,我以后可以运行get_paths(h,1)而不回溯2中的所有路径吗？

import collections

# Object representing a stream reach.  Used to construct a hierarchy for accumulation function
class Reach(object):
    def __init__(self):
        self.name = None
        self.ds = None
        self.us = set()

    def __repr__(self):
        return "Reach({})".format(self.name)


def build_hierarchy(flows):
    hierarchy = collections.defaultdict(lambda: Reach())
    for reach_id, parent in flows:
        if reach_id:
            hierarchy[reach_id].name = reach_id
            hierarchy[parent].name = parent
            hierarchy[reach_id].ds = hierarchy[parent]
            hierarchy[parent].us.add(hierarchy[reach_id])
    return hierarchy

def get_paths(h, start_node):
    def go_up(n):
        if not h[n].us:
            paths.append(current_path[:])
        for us in h[n].us:
            current_path.append(us)
            go_up(us.name)
        if current_path:
            current_path.pop()
    paths = []
    current_path = []
    go_up(start_node)
    return paths

test_tree = {(11, 9), (10, 9), (9, 6), (6, 2), (8, 5), (5, 4), (4, 2), (2, 1), (3, 1), (7, 3)}
h = build_hierarchy(test_tree)
p = get_paths(h, 1)

编辑:几个星期前,我问了一个类似的问题,关于在网络中找到"ALL"上游网站并收到一个非常快的答案:

class Node(object):

    def __init__(self):
        self.name = None
        self.parent = None
        self.children = set()
        self._upstream = set()

    def __repr__(self):
        return "Node({})".format(self.name)

    @property
    def upstream(self):
        if self._upstream:
            return self._upstream
        else:
            for child in self.children:
                self._upstream.add(child)
                self._upstream |= child.upstream
            return self._upstream

import collections

edges = {(11, 9), (10, 9), (9, 6), (6, 2), (8, 5), (5, 4), (4, 2), (2, 1), (3, 1), (7, 3)}
nodes = collections.defaultdict(lambda: Node())

for node, parent in edges:
    nodes[node].name = node
    nodes[parent].name = parent
    nodes[node].parent = nodes[parent]
    nodes[parent].children.add(nodes[node])

我注意到def upstream():这段代码的一部分按顺序添加了上游节点,但由于它是一个迭代函数,我找不到将它们附加到单个列表的好方法.也许有一种方法可以修改保留订单的代码.