概述
我试图弄清楚如何使用某种 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 是遍历算法的迭代版本，它不知道如何处理循环图。理想情况下，解决方案也是迭代的，但如果存在更好的递归解决方案，那就太好了
- 我们在这里谈论的数据结构不应该被称为“有向无环图”，因为在这种情况下，每个节点都有其子节点，并且在图中节点连接没有顺序。
- 一切都可以连接到编辑器中的任何东西。您将能够执行任何块组合，唯一的限制是执行计数器，如果您进行无休止的循环或过多的迭代，它将溢出。
- 该算法将保留节点的方法执行的开始/中间/之后，类似于上面的代码片段
问题
谁能提供某种知道如何遍历无限/有限循环的解决方案？
参考
如果此时问题还不清楚，你可以在这篇文章中阅读更多关于这个问题的内容，整个想法将使用遍历算法来实现类似文章中所示的工具。
这是一个屏幕截图，显示了这种数据结构的全部功能，我想弄清楚如何遍历和运行：
