如何使用改进的DFS算法遍历循环有向图 [英] How to traverse cyclic directed graphs with modified DFS algorithm

问题描述

概述

我正在尝试找出如何遍历有向环图的方法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 
  

1. 我们要做的第一件事是访问该节点。我们通过增加字典中节点的访问次数来实现此目的。


2. 然后，我们引发节点的 start 事件。


3. 我们进行了简单的检查，以查看该节点是否为无子（叶）节点。如果是的话，我们引发 end 事件并返回。


4. 现在，我们已经确定该节点具有邻居，我们可以迭代通过每个邻居。 侧面注：：我以递归方式反转邻居列表（通过使用 graph [node] [::-1] ）以保持相同迭代版本中邻居遍历的顺序（从右到左）。
   
   
   
   
   1. 对于每个邻居，我们首先计算重复次数。重复计数从祖先节点传播（继承），因此使用继承的重复计数，除非 邻居包含重复计数值。
   
   
   2. 如果正在处理第二个（或更大）邻居，则引发当前节点（不是邻居）的中间事件
   
   
   3. 如果可以访问邻居，则访问该邻居。可访问性检查是通过检查是否已访问邻居的时间少于a） MAX_THRESHOLD 次（对于伪无限循环）和b）上述计算的重复计数次数来完成的。 / li>
      



5. 我们现在已经完成了此节点；引发 end 事件，并在哈希表中清除其访问。这样做是为了使其他某个节点再次调用它，也不会使可访问性检查失败和/或执行次数少于要求的次数。

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

1. The first thing we do is visit the node. We do this by incrementing the number of visits of the node in the dictionary.
2. We then raise the start event of the node.
3. We do a simple check to see if the node is a childless (leaf) node or not. If it is, we raise the end event and return.
4. Now that we've established that the node has neighbors, we iterate through each neighbor. Side Note: I reverse the neighbor list (by using graph[node][::-1]) in the recursive version to maintain the same order (right to left) of traversal of neighbors as in the iterative version.
   1. For each neighbor, we first calculate the repeat count. The repeat count propagates (is inherited) through from the ancestor nodes, so the inherited repeat count is used unless the neighbor contains a repeat count value.
   2. We raise the middle event of the current node (not the neighbor) if the second (or greater) neighbor is being processed.
   3. If the neighbor can be visited, the neighbor is visited. The visitability check is done by checking whether the neighbor has been visited less than a) MAX_THRESHOLD times (for pseudo-infinite cycles) and b) the above calculated repeat count times.

5. We're now done with this node; raise the end event and clear its visits in the hashtable. This is done so that if some other node calls it again, it does not fail the visitability check and/or execute for less than the required number of times.

这篇关于如何使用改进的DFS算法遍历循环有向图的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！