概述
我正在尝试找出如何遍历有向环图的方法DFS迭代算法。这是我当前实现的一些mcve版本(它不涉及周期):
类Node(对象) : def __init __(self,name): self.name = name def start(self): print'{} _start' .format(自己) def中间(self): print'{} _middle'.format(自己) def结束(self): print'{} _end'.format(self) def __str __(self):返回 {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):使用带有反向子项的DFS从起始节点遍历图 已访问= {} 堆栈= [(开始,)] 而堆栈:#转换dfs-> bfs #a)将堆栈重命名为队列#b)pop成为pop(0)节点,父代= stack.pop()如果父代为None:,如果被访问[节点]< 3: node.end()已访问[节点] = 3 elif节点未访问:如果访问过。get(parent)== 2: parent.middle() elif Visited.get(parent)== 1: Visited [parent] = 2 node.start() Visited [node ] = 1 stack.append((node,None)) #也许您想要不同的顺序,如果是这样,请不要使用反向的 childs = reversed(graph.get(node,[])) for child in child:,如果未访问孩子: stack.append((child,node)) 如果__name__ == __main__: Sequence1 = Node('Sequence1') MtxPushPop1 = Node('MtxPushPop1') Rotate1 = Node(' Rotate1') Repeat1 = NodeRepeat('Repeat1',num_repeats = 2) Sequence2 = Node('Sequence2') MtxPushPop2 = Node('MtxPushPop2')$ b $ T ranslate = Node('Translate') Rotate2 = Node('Rotate2') Rotate3 = Node('Rotate3') Scale = Node('Scale') Repeat2 = NodeRepeat('Repeat2',num_repeats = 3)网格= Node('Mesh') cyclic_graph = { Sequence1:[MtxPushPop1,Rotate1], MtxPushPop1 :[Sequence2], Rotate1:[Repeat1], Sequence2:[MtxPushPop2,Translate], Repeat1:[Sequence1], MtxPushPop2:[Rotate2],翻译:[Rotate3], Rotate2:[Scale], Rotate3:[Repeat2], Scale:[Mesh], Repeat2:[Sequence2] } dfs(cyclic_graph,Sequence1) print'-'* 80 a = Node('a')b =节点('b') dfs({a:[b],b:[a] },a)上面的代码正在测试几种情况,第一种是下面gra的某种表示形式ph:
第二个是最简单的一个包含一个无限循环的图的情况 {a-> b,b-> a}
需求
- 不存在无限循环之类的东西,比如说当一个找到无限循环,将有一个最大阈值(全局变量)来指示何时停止在那些伪无限循环周围循环。
- 所有图节点都可以创建循环,但是将会存在一个名为 Repeat 的特殊节点,您可以在其中指定要在循环中循环多少次迭代
- 我已经完成的上述mcve发布的是遍历算法的迭代版本,不知道如何处理循环图。理想情况下,该解决方案也是迭代的,但是如果存在更好的递归解决方案,那将是很好的
- 我们在此讨论的数据结构不应称为有向非循环图确实是因为在这种情况下,每个节点的子节点都已排序,而在图节点中,节点的连接没有顺序。
- 所有内容都可以连接到编辑器中的任何内容。您将能够执行任何块组合,并且唯一的限制是执行计数器,如果您进行了永无止境的循环或太多的迭代,则执行计数器将溢出。
- 算法将保留开始/中间位置/ after节点的方法执行与上面的代码段类似
问题
谁能提供某种解决方案,知道如何遍历无限/有限循环?
参考
如果目前尚不清楚,您可以在
解决方案在我开始之前,在CodeSkulptor上运行代码!我也希望这些评论能详细说明我已经做的足够。如果需要更多说明,请查看我在代码下方对递归方法的说明。
#如果您不希望使用全局变量,则删除缩进过程 indent = -1 MAX_THRESHOLD = 10 INF = 1< 63 def whitespace():全球缩进 return’| '*(缩进) 类节点:$ b $ b def __init __(self,name,num_repeats = INF): self.name =名称 self.num_repeats = num_repeats def start(self):全局缩进 if self.name.find('Sequence')!= -1: print whitespace()缩进+ = 1 print whitespace()+'%s_start'%self.name def middle(self): print whitespace()+'%s_middle' self.name def end(self):全局缩进 print whitespace()+'%s_end'%self.name (如果self.name)。 find('Sequence')!= -1:缩进-= 1 print whitespace() def dfs(graph,start): visits = { } frontier = []#跟踪访问节点的堆栈 #每当我们访问一个节点时,增加其访问计数 frontier.append(( ,start.num_repeats)) visits [start] = visits.get(start ,0)+ 1 而边疆:#parent_repeat_count通常包含vertex.repeat_count #但是,如果重复节点是其祖先$ b $,则可能包含更高的值b顶点,parent_repeat_count = frontier.pop() #特殊情况,如果parent_repeat_count == -1,则表示结束: vertex.end()#我们已经完成了这个顶点,并进行了清晰的访问,因此#如果有其他节点调用我们,我们仍然可以称为访问[vertex] = 0 继续 #如果parent_repeat_count == -2,则表示中间的特殊情况: vertex.middle() Continue #发送开始消息 vertex.start() #首先将节点的结束状态添加到堆栈中#使其最后执行 frontier.append((vertex,- 1)) #没有更多的孩子,继续#由于上述行,end方法将#如果顶点不在图中,仍将执行:继续 ##如果要从左到右邻居,请取消注释以下行 #### graph [vertex] .reverse() for i,numerate(graph [顶点]):#重复计数应在邻居之间传播#也就是说,如果父对象的重复计数较高,请使用 repeat_count = max(1,parent_repeat_count)如果neighbor.num_repeats!= INF: repeat_count = neighbor.num_repeats #我们已经经历了至少一个邻居节点#将该顶点的中间状态追加到堆栈中如果i> = 1: frontier.append((vertex,-2)) #如果我们访问邻居的次数不超过我们必须访问,如果visits.get(neighbor,0)< MAX_THRESHOLD和visits.get(neighbor,0)< repeat_count: frontier.append((neighbor,repeat_count))次访问[neighbor] = visits.get(neighbor,0)+ 1 def dfs_rec(graph,node, parent_repeat_count = INF,访问次数= {}):次访问[节点] = visits.get(node,0)+ 1 node.start() 如果节点不在图中: node.end()返回 for i,枚举中的邻居(graph [node] [::-1]): repeat_count = max(1,parent_repeat_count)如果neighbor.num_repeats!= INF: repeat_count = neighbor.num_repeats 如果i> = 1:节点.middle() ,如果visits.get(neighbor,0)< MAX_THRESHOLD和visits.get(neighbor,0)< repeat_count: dfs_rec(图形,邻居,repeat_count,访问) node.end() visits [node] = 0 Sequence1 =节点('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')比例尺= 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],翻译:[Rotate3], Rotate2:[Scale], Rotate3:[Repeat2], 比例尺:[网格],重复2:[序列2] } dfs(cyc lic_graph,Sequence1) 打印'-'* 40 dfs_rec(cyclic_graph,Sequence1) 打印'-'* 40 dfs({Sequence1:[Translate],Translate:[Sequence1]},Sequence1) print'-'* 40 dfs_rec({{Sequence1:[翻译],翻译:[Sequence1]},Sequence1)输入和(格式正确且缩进)可以在此处找到输出。如果您想查看如何我格式化了输出,请参阅代码,该代码也可以为在CodeSkulptor上找到。
对,再进行解释。我将用来帮助解释的更容易理解但效率低得多的递归解决方案如下:
def dfs_rec(graph ,节点,parent_repeat_count = INF,访问次数= {}):个访问量[node] = visits.get(node,0)+ 1 node.start() 如果节点不在图中: node.end()返回 for i,枚举中的邻居(graph [node] [::-1]): repeat_count = max(1,parent_repeat_count)如果neighbor.num_repeats!= INF: repeat_count = neighbor.num_repeats 如果i> = 1: node.middle() ,如果visits.get(neighbor,0)< MAX_THRESHOLD和visits.get(neighbor,0)< repeat_count: dfs_rec(图表,邻居,repeat_count,访问次数) node.end()访问次数[node] = 0
OVERVIEW
I'm trying to figure out how to traverse directed cyclic graphs using some sort of DFS iterative algorithm. Here's a little mcve version of what I currently got implemented (it doesn't deal with cycles):
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)The above code is testing a couple of cases, the first would be some sort of representation of the below graph:
The second one is the simplest case of one graph containing one "infinite" loop {a->b, b->a}
REQUIREMENTS
- There won't exist such a thing like "infinite cycles", let's say when one "infinite cycle" is found, there will be a maximum threshold (global var) to indicate when to stop looping around those "pseudo-infinite cycles"
- All graph nodes are able to create cycles but there will exist a special node called Repeat where you can indicate how many iterations to loop around the cycle
- The above mcve I've posted is an iterative version of the traversal algorithm which doesn't know how to deal with cyclic graphs. Ideally the solution would be also iterative but if there exists a much better recursive solution, that'd be great
- The data structure we're talking about here shouldn't be called "directed acyclic graphs" really because in this case, each node has its children ordered, and in graphs node connections have no order.
- Everything can be connected to anything in the editor. You'll be able to execute any block combination and the only limitation is the execution counter, which will overflow if you made neverending loop or too many iterations.
- The algorithm will preserve start/middle/after node's method execution similarly than the above snippet
QUESTION
Could anyone provide some sort of solution which knows how to traverse infinite/finite cycles?
REFERENCES
If question is not clear yet at this point, you can read this more about this problem on this article, the whole idea will be using the traversal algorithm to implement a similar tool like the shown in that article.
Here's a screenshot showing up the whole power of this type of data structure I want to figure out how to traverse&run:
解决方案Before I start, Run the code on CodeSkulptor! I also hope that the comments elaborate what I have done enough. If you need more explanation, look at my explanation of the recursive approach below the code.
# 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)The input and (well formatted and indented) output can be found here. If you want to see how I formatted the output, please refer to the code, which can also be found on CodeSkulptor.
Right, on to the explanation. The easier to understand but much more inefficient recursive solution, which I'll use to help explain, follows:
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
更多推荐
如何使用改进的DFS算法遍历循环有向图
发布评论