如何使用改进的DFS算法遍历循环有向图

Question

概述

我正在尝试使用某种DFS迭代算法遍历有向循环图。这是我目前实现的一个小型mcve版本（它不处理循环）：

class Node(object):

    def __init__(self, name):
        self.name = name

    def start(self):
        print '{}_start'.format(self)

    def middle(self):
        print '{}_middle'.format(self)

    def end(self):
        print '{}_end'.format(self)

    def __str__(self):
        return "{0}".format(self.name)


class NodeRepeat(Node):

    def __init__(self, name, num_repeats=1):
        super(NodeRepeat, self).__init__(name)
        self.num_repeats = num_repeats


def dfs(graph, start):
    """Traverse graph from start node using DFS with reversed childs"""

    visited = {}
    stack = [(start, "")]
    while stack:
        # To convert dfs -> bfs
        # a) rename stack to queue
        # b) pop becomes pop(0)
        node, parent = stack.pop()
        if parent is None:
            if visited[node] < 3:
                node.end()
            visited[node] = 3
        elif node not in visited:
            if visited.get(parent) == 2:
                parent.middle()
            elif visited.get(parent) == 1:
                visited[parent] = 2

            node.start()
            visited[node] = 1

            stack.append((node, None))

            # Maybe you want a different order, if it's so, don't use reversed
            childs = reversed(graph.get(node, []))
            for child in childs:
                if child not in visited:
                    stack.append((child, node))


if __name__ == "__main__":
    Sequence1 = Node('Sequence1')
    MtxPushPop1 = Node('MtxPushPop1')
    Rotate1 = Node('Rotate1')
    Repeat1 = NodeRepeat('Repeat1', num_repeats=2)

    Sequence2 = Node('Sequence2')
    MtxPushPop2 = Node('MtxPushPop2')
    Translate = Node('Translate')
    Rotate2 = Node('Rotate2')
    Rotate3 = Node('Rotate3')
    Scale = Node('Scale')
    Repeat2 = NodeRepeat('Repeat2', num_repeats=3)
    Mesh = Node('Mesh')

    cyclic_graph = {
        Sequence1: [MtxPushPop1, Rotate1],
        MtxPushPop1: [Sequence2],
        Rotate1: [Repeat1],
        Sequence2: [MtxPushPop2, Translate],
        Repeat1: [Sequence1],
        MtxPushPop2: [Rotate2],
        Translate: [Rotate3],
        Rotate2: [Scale],
        Rotate3: [Repeat2],
        Scale: [Mesh],
        Repeat2: [Sequence2]
    }

    dfs(cyclic_graph, Sequence1)

    print '-'*80

    a = Node('a')
    b = Node('b')
    dfs({
        a : [b],
        b : [a]
    }, a)

上面的代码正在测试一些情况，第一个是下面图表的某种表示形式：

第二种情况是一个图包含一个“无限”循环的最简单情况 {a->b, b->a}

要求

• 不存在类似"无限循环"的事情，当找到一个"无限循环"时，将有一个最大阈值（全局变量）来指示何时停止围绕这些"伪无限循环"进行循环
• 所有图节点都能创建循环，但是会存在一个特殊节点叫做Repeat，你可以在其中指定循环迭代的次数
• 我发布的上面的mcve是遍历算法的迭代版本，不知道如何处理循环图。理想情况下，解决方案也应该是迭代的，但是如果存在更好的递归解决方案，那就太棒了
• 我们在这里谈论的数据结构实际上不应该被称为"有向无环图"，因为在这种情况下，每个节点都有其子节点排序，而在图中节点连接没有顺序。
• 编辑器中可以任意连接任何内容。您将能够执行任何块组合，唯一的限制是执行计数器，如果您制作了永不结束的循环或太多迭代，则会溢出。
• 该算法将像上面的代码片段一样保留开始/中间/后续节点的方法执行

问题

请问是否有解决方案可以遍历无限/有限循环？

参考资料

如果现在问题还不清楚，您可以在文章中阅读更多关于这个问题的内容，整个想法是使用遍历算法来实现类似于该文章中展示的工具。

这里是一张屏幕截图，展示了我想要遍历和运行的这种数据结构的全部功能：

- BPL

---

你在开发一个渲染引擎吗？看起来很不错。 - EvilTak

你给出的第一个示例的预期输出是什么？请只展示访问节点的顺序，并描述所需的重复次数。 - EvilTak

你只是想访问每个节点，还是节点被访问的顺序很重要？例如，为什么广度优先搜索对你不起作用？ - ead

@EvilTak 关于访问具有所需重复的节点的顺序，我需要在编辑器中插入您的遍历算法后确认您的答案。我将在本周创建编辑器，并测试此处发布的所有可能的解决方案。在本周末，一旦我测试了它们所有，我将发布我获得的性能结果，并判断哪个值得奖励（性能+优雅）。为了表彰您的努力，让我们开始给您+1。 - BPL

不清楚您想让MAX_THRESHOLD做什么。如果您不希望出现无限循环，只是想避免崩溃，那么您应该使用Brent的循环查找算法，它可以轻松地适应于在DFS中检测循环：https://en.wikipedia.org/wiki/Cycle_detection#Brent.27s_algorithm。 - Matt Timmermans

Answer 1

在开始之前，请在CodeSkulptor上运行代码!我也希望评论足够详细地解释了我所做的事情。如果您需要更多解释，请查看代码下方关于递归方法的解释。

# If you don't want global variables, remove the indentation procedures
indent = -1

MAX_THRESHOLD = 10
INF = 1 << 63

def whitespace():
    global indent
    return '|  ' * (indent)

class Node:
    def __init__(self, name, num_repeats=INF):
        self.name = name
        self.num_repeats = num_repeats

    def start(self):
        global indent
        if self.name.find('Sequence') != -1:
            print whitespace()
            indent += 1
        print whitespace() + '%s_start' % self.name

    def middle(self):
        print whitespace() + '%s_middle' % self.name

    def end(self):
        global indent
        print whitespace() + '%s_end' % self.name
        if self.name.find('Sequence') != -1:
            indent -= 1
            print whitespace()

def dfs(graph, start):
    visits = {}
    frontier = [] # The stack that keeps track of nodes to visit

    # Whenever we "visit" a node, increase its visit count
    frontier.append((start, start.num_repeats))
    visits[start] = visits.get(start, 0) + 1

    while frontier:
        # parent_repeat_count usually contains vertex.repeat_count
        # But, it may contain a higher value if a repeat node is its ancestor
        vertex, parent_repeat_count = frontier.pop()

        # Special case which signifies the end
        if parent_repeat_count == -1:
            vertex.end()
            # We're done with this vertex, clear visits so that 
            # if any other node calls us, we're still able to be called
            visits[vertex] = 0
            continue

        # Special case which signifies the middle
        if parent_repeat_count == -2:
            vertex.middle()
            continue  

        # Send the start message
        vertex.start()

        # Add the node's end state to the stack first
        # So that it is executed last
        frontier.append((vertex, -1))

        # No more children, continue
        # Because of the above line, the end method will
        # still be executed
        if vertex not in graph:
            continue

        ## Uncomment the following line if you want to go left to right neighbor
        #### graph[vertex].reverse()

        for i, neighbor in enumerate(graph[vertex]):
            # The repeat count should propagate amongst neighbors
            # That is if the parent had a higher repeat count, use that instead
            repeat_count = max(1, parent_repeat_count)
            if neighbor.num_repeats != INF:
                repeat_count = neighbor.num_repeats

            # We've gone through at least one neighbor node
            # Append this vertex's middle state to the stack
            if i >= 1:
                frontier.append((vertex, -2))

            # If we've not visited the neighbor more times than we have to, visit it
            if visits.get(neighbor, 0) < MAX_THRESHOLD and visits.get(neighbor, 0) < repeat_count:
                frontier.append((neighbor, repeat_count))
                visits[neighbor] = visits.get(neighbor, 0) + 1

def dfs_rec(graph, node, parent_repeat_count=INF, visits={}):
    visits[node] = visits.get(node, 0) + 1

    node.start()

    if node not in graph:
        node.end()
        return

    for i, neighbor in enumerate(graph[node][::-1]):
        repeat_count = max(1, parent_repeat_count)
        if neighbor.num_repeats != INF:
            repeat_count = neighbor.num_repeats

        if i >= 1:
            node.middle()

        if visits.get(neighbor, 0) < MAX_THRESHOLD and visits.get(neighbor, 0) < repeat_count:
            dfs_rec(graph, neighbor, repeat_count, visits)

    node.end()  
    visits[node] = 0

Sequence1 = Node('Sequence1')
MtxPushPop1 = Node('MtxPushPop1')
Rotate1 = Node('Rotate1')
Repeat1 = Node('Repeat1', 2)

Sequence2 = Node('Sequence2')
MtxPushPop2 = Node('MtxPushPop2')
Translate = Node('Translate')
Rotate2 = Node('Rotate2')
Rotate3 = Node('Rotate3')
Scale = Node('Scale')
Repeat2 = Node('Repeat2', 3)
Mesh = Node('Mesh')

cyclic_graph = {
        Sequence1: [MtxPushPop1, Rotate1],
        MtxPushPop1: [Sequence2],
        Rotate1: [Repeat1],
        Sequence2: [MtxPushPop2, Translate],
        Repeat1: [Sequence1],
        MtxPushPop2: [Rotate2],
        Translate: [Rotate3],
        Rotate2: [Scale],
        Rotate3: [Repeat2],
        Scale: [Mesh],
        Repeat2: [Sequence2]
    }

dfs(cyclic_graph, Sequence1)

print '-'*40

dfs_rec(cyclic_graph, Sequence1)

print '-'*40

dfs({Sequence1: [Translate], Translate: [Sequence1]}, Sequence1)

print '-'*40

dfs_rec({Sequence1: [Translate], Translate: [Sequence1]}, Sequence1)

您可以在这里找到输入和（格式良好且缩进）输出。如果您想要看我如何格式化输出，可以参考代码，代码也可以在CodeSkulptor上找到。

---

好的，接下来是解释。更易理解但效率低得多的递归解决方案如下：

def dfs_rec(graph, node, parent_repeat_count=INF, visits={}):
    visits[node] = visits.get(node, 0) + 1

    node.start()

    if node not in graph:
        node.end()
        return

    for i, neighbor in enumerate(graph[node][::-1]):
        repeat_count = max(1, parent_repeat_count)
        if neighbor.num_repeats != INF:
            repeat_count = neighbor.num_repeats

        if i >= 1:
            node.middle()

        if visits.get(neighbor, 0) < MAX_THRESHOLD and visits.get(neighbor, 0) < repeat_count:
            dfs_rec(graph, neighbor, repeat_count, visits)

    node.end()  
    visits[node] = 0

1. 首先，我们访问节点。这是通过在字典中增加节点访问次数来实现的。
2. 然后，我们触发节点的 start 事件。
3. 我们简单地检查节点是否为无子节点 (叶子节点)。如果是，则触发 end 事件并返回。
4. 既然已经确定该节点有邻居，我们就遍历每个邻居。侧边说明: 在递归版本中，我通过使用 graph[node][::-1] 来反转邻居列表以保持与迭代版本相同的遍历顺序(从右到左)。
   1. 对于每个邻居，我们首先计算重复次数。此重复次数将从祖先节点继承，因此除非 邻居 包含重复次数值，否则将使用继承的重复次数。
   2. 如果正在处理第二个或更多邻居，则会触发当前节点 (不是 邻居) 的 middle 事件。
   3. 如果可以访问邻居，则访问邻居。可访问性检查是通过检查邻居是否被访问少于 a) MAX_THRESHOLD 次 (用于伪无限循环) 和 b) 上面计算的重复次数的倍数。
5. 现在我们已完成此节点; 触发 end 事件并清除其在哈希表中的访问次数。这是为了如果其他节点再次调用它，它不会失败于可访问性检查和/或执行小于所需次数。

- EvilTak

---

你能否在这里发布最终版本而不是CodeSkulptor？你粘贴的那个格式很糟糕。而且在CodeSkulptor中的版本没有考虑MAX_THRESHOLD，所以我不知道该评估哪个版本。顺便说一下，你在CodeSkulptor上的版本使用全局变量来处理缩进，并且没有使用我在我的mcve中使用的相同类（Node＆NodeRepeat）。 - BPL

打印/调试代码是一个小而好玩的额外功能，这就是为什么我没有将其列为要求的原因。我总是更喜欢避免在我的代码中使用全局变量。调试节点执行将有助于添加一些节点分析。顺便说一下，我的编辑器的第一个版本将使用Python代码来渲染场景图，但可能在未来的版本中我会使用C++播放器，编辑器将能够直接创建可执行文件（但这不是本文讨论的范围）。 - BPL

@BPL很有道理。我也会避免使用全局变量。你看过最新的编辑了吗？它们似乎能够满足你的需求。 - EvilTak

是的，我已经检查过了。在我看来，你版本中唯一的小问题是使用了这个 hacky 行 frontier.append((start, start.num_repeats if isinstance(start, NodeRepeat) else 2 << 31)) 和全局变量的使用。除此之外，你的算法似乎符合要求，但是我需要在我的编辑器第一版运行后进行图形化检查。顺便说一句，你的答案看起来很不错！我相信如果你稍微编辑和清理一下，并添加它的递归版本，将有助于获得一些很好的 upvotes，你为此付出了努力，值得肯定。 - BPL

@BPL 老实说，那个不太好的代码行可以通过使用单个“Node”类（我以前做过）来避免，但是你需要两个不同的类来重复节点。那一行肯定可以变得更美观。我没有使用sys.maxint或maxsize，因为CodeSkulptor不支持它:P。递归解决方案应该更加简单，将在几个小时内发布。我只使用了一个全局变量indent变量用于缩进输出，但这也可以重构为IndentedPrinter或类似的东西。特殊情况的hack也可以被删除，但需要更多的代码。 - EvilTak

Answer 2

根据comment66244567的说法 - 通过忽略到已访问节点的链接并执行广度优先搜索将图形缩小为树，因为这将产生更自然（可能更平衡）的树形结构。

def traverse(graph,node,process):
    seen={node}
    current_level=[node]
    while current_level:
        next_level=[]
        for node in current_level:
            process(node)
            for child in (link for link in graph.get(node,[]) if link not in seen):
                next_level.append(child)
                seen.add(child)
        current_level=next_level

使用您的图表和def process(node): print node，这将产生：

In [24]: traverse(cyclic_graph,Sequence1,process)
Sequence1
MtxPushPop1
Rotate1
Sequence2
Repeat1
MtxPushPop2
Translate
Rotate2
Rotate3
Scale
Repeat2
Mesh

另一种BFS算法迭代加深DFS（速度较慢但使用的内存较少）在这种情况下并没有优势：因为您必须存储已访问节点的引用，所以已经消耗了O(n)内存。您也不需要产生中间结果（但是您仍然可以 - 例如，在处理级别后yield something）。

- ivan_pozdeev

---

谢谢你的回答！但我不明白你的版本如何符合要求。例如，开始/中间/结束方法将在哪里执行？ - BPL

不需要重新定义__hash __（），因为那是默认定义。 - EvilTak

@BPL 他们应该在 process() 中。问题是关于遍历图形，你对每个节点做什么与此无关 - 因此遍历将与处理不相交，并且应允许任何处理而不仅仅是你提供的示例。编写必要的 process() 很简单，所以我没有用不必要的细节来混淆答案。 - ivan_pozdeev

@ivan_pozdeev 好的，无论如何感谢你的回答！一旦我本周实现了我的编辑器的基础功能，我将调整和测试您的算法。现在让您知道，迄今为止最适合进行验证和奖励的候选人是 Evil Tak 的答案（如果您关心的话 :)) - BPL

@EvilTak 谢谢，我不知道这一点（文档只是间接提到了这一点）。对于 object 和 instance，默认的 hash() 不是其地址本身，而是 _Py_HashPointer(<address>)。 - ivan_pozdeev

SO的答案也应该对未来的读者有用，而不仅仅是一个人，无关的细节会对这个目标产生负面影响。 - ivan_pozdeev