Python中的路径查找效率

Question

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

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

Answer 1

是的，你可以这样做。我不完全确定你的限制是什么；但是，这应该会让您走上正轨。最坏情况下的运行时间是 O(|E|+|V|)，唯一的区别是，在 中p.dfsh，我们缓存了先前评估的路径，而 中p.dfs则没有。

\n\n

这会增加额外的空间开销，因此请注意权衡 \xe2\x80\x93 你将节省许多迭代（取决于你的数据集），但无论如何都会占用更多内存。不幸的是，缓存并不能改善增长顺序，只能改善实际运行时间：

\n\n

points = set([\n    (11, 9),\n    (10, 9), \n    (9, 6), \n    (6, 2), \n    (8, 5), \n    (5, 4), \n    (4, 2), \n    (2, 1), \n    (3, 1),\n    (7, 3),\n])\n\nclass PathFinder(object):\n\n    def __init__(self, points):\n        self.graph  = self._make_graph(points)\n        self.hierarchy = {}\n\n    def _make_graph(self, points):\n        graph = {}\n        for p in points:\n            p0, p1 = p[0], p[1]\n            less, more = min(p), max(p)\n\n            if less not in graph:\n                graph[less] = set([more])\n            else:\n                graph[less].add(more)\n\n        return graph\n\n    def dfs(self, start):\n        visited = set()\n        stack = [start]\n\n        _count = 0\n        while stack:\n            _count += 1\n            vertex = stack.pop()\n            if vertex not in visited:\n                visited.add(vertex)\n                if vertex in self.graph:\n                    stack.extend(v for v in self.graph[vertex])\n\n        print "Start: {s} | Count: {c} |".format(c=_count, s=start),\n        return visited\n\n    def dfsh(self, start):\n        visited = set()\n        stack = [start]\n\n        _count = 0\n        while stack:\n            _count += 1\n\n            vertex = stack.pop()\n            if vertex not in visited:\n                if vertex in self.hierarchy:\n                    visited.update(self.hierarchy[vertex])\n                else:\n                    visited.add(vertex)\n                    if vertex in self.graph:\n                        stack.extend([v for v in self.graph[vertex]])\n        self.hierarchy[start] = visited\n\n        print "Start: {s} | Count: {c} |".format(c=_count, s=start),\n        return visited\n\np = PathFinder(points)\nprint p.dfsh(1)\nprint p.dfsh(2)\nprint p.dfsh(9)\nprint p.dfsh(6)\nprint p.dfsh(2)\nprint \nprint p.dfs(1)\nprint p.dfs(2)\nprint p.dfs(9)\nprint p.dfs(6)\nprint p.dfs(2)\n

\n\n

其输出p.dfsh如下：

\n\n

Start: 1 | Count: 11 | set([1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11])\nStart: 2 | Count: 8 | set([2, 4, 5, 6, 8, 9, 10, 11])\nStart: 9 | Count: 3 | set([9, 10, 11])\nStart: 6 | Count: 2 | set([9, 10, 11, 6])\nStart: 2 | Count: 1 | set([2, 4, 5, 6, 8, 9, 10, 11])\n

\n\n

常规的输出p.dfs是：

\n\n

Start: 1 | Count: 11 | set([1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11])\nStart: 2 | Count: 8 | set([2, 4, 5, 6, 8, 9, 10, 11])\nStart: 9 | Count: 3 | set([9, 10, 11])\nStart: 6 | Count: 4 | set([9, 10, 11, 6])\nStart: 2 | Count: 8 | set([2, 4, 5, 6, 8, 9, 10, 11])\n

\n\n

正如您所看到的，我进行了 DFS，但我在合理范围内跟踪了之前的迭代。我不想跟踪所有可能的先前路径，因为如果您在大型数据集上使用它，它将占用大量内存。

\n\n

在输出中，您可以看到 go 的迭代计数从 8 到 1。同样，由于之前计算 ，p.dfsh(2)因此 的计数也下降到 2 。与标准 DFS 相比，这是一个适度的运行时改进，尤其是在非常大的数据集上。p.dfsh(6)p.dfsh(9)

\n