How to traverse cyclic directed graphs with modified DFS algorithm
<p><strong>OVERVIEW</strong></p>

<p>I'm trying to figure out how to traverse <strong>directed cyclic graphs</strong> 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):</p>

<pre><code>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 -&gt; bfs
        # a) rename stack to queue
        # b) pop becomes pop(0)
        node, parent = stack.pop()
        if parent is None:
            if visited[node] &lt; 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)
</code></pre>

<p>The above code is testing a couple of cases, the first would be some sort of representation of the below graph:</p>

<p><a href="http://i.stack.imgur.com/s2DSc.png"><img src="http://i.stack.imgur.com/s2DSc.png" alt="enter image description here"></a></p>

<p>The second one is the simplest case of one graph containing one "infinite" loop <code>{a-&gt;b, b-&gt;a}</code></p>

<p><strong>REQUIREMENTS</strong></p>

<ul>
<li>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"</li>
<li>All graph nodes are able to create cycles but there will exist a special node called <code>Repeat</code> where you can indicate how many iterations to loop around the cycle</li>
<li>The above mcve I've posted is an iterative version of the traversal algorithm which <strong>doesn't know how to deal with cyclic graphs</strong>. Ideally the solution would be also iterative but if there exists a much better recursive solution, that'd be great</li>
<li>The data structure we're talking about here shouldn't be called "directed acyclic graphs" really because in this case, <strong>each node has its children ordered</strong>, and in graphs node connections have no order. </li>
<li>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.</li>
<li>The algorithm will preserve start/middle/after node's method execution similarly than the above snippet</li>
</ul>

<p><strong>QUESTION</strong></p>

<p>Could anyone provide some sort of solution which knows how to traverse infinite/finite cycles?</p>

<p><strong>REFERENCES</strong></p>

<p>If question is not clear yet at this point, you can read this more about this problem on this <a href="http://www.bitfellas.org/e107_plugins/content/content.php?content.674">article</a>, the whole idea will be using the traversal algorithm to implement a similar tool like the shown in that article. </p>

<p>Here's a screenshot showing up the whole power of this type of data structure I want to figure out how to traverse&amp;run:</p>

<p><a href="http://i.stack.imgur.com/N2OtM.jpg"><img src="http://i.stack.imgur.com/N2OtM.jpg" alt="enter image description here"></a></p>

<p>Before I start, <a href="http://www.codeskulptor.org/#user42_MYuqELNPFl_7.py" rel="nofollow">Run the code on CodeSkulptor!</a> I also hope that the comments elaborate what I have done enough. If you need more explanation, look at my explanation of the <em>recursive</em> approach below the code.</p>

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

MAX_THRESHOLD = 10
INF = 1 &lt;&lt; 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 &gt;= 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) &lt; MAX_THRESHOLD and visits.get(neighbor, 0) &lt; 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 &gt;= 1:
            node.middle()

        if visits.get(neighbor, 0) &lt; MAX_THRESHOLD and visits.get(neighbor, 0) &lt; 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)
</code></pre>

<p>The input and (well formatted and indented) output can be found <a href="http://www.hastebin.com/etedihayay.py" rel="nofollow">here</a>. If you want to see <em>how</em> I formatted the output, please refer to the code, which can also be <a href="http://www.codeskulptor.org/#user42_MYuqELNPFl_7.py" rel="nofollow">found on CodeSkulptor</a>.</p>

<hr>

<p>Right, on to the explanation. The easier to understand but much more inefficient recursive solution, which I'll use to help explain, follows:</p>

<pre><code>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 &gt;= 1:
            node.middle()

        if visits.get(neighbor, 0) &lt; MAX_THRESHOLD and visits.get(neighbor, 0) &lt; repeat_count:
            dfs_rec(graph, neighbor, repeat_count, visits)

    node.end()  
    visits[node] = 0
</code></pre>

<ol>
<li>The first thing we do is visit the node. We do this by incrementing the number of visits of the node in the dictionary.</li>
<li>We then raise the <code>start</code> event of the node.</li>
<li>We do a simple check to see if the node is a childless (leaf) node or not. If it is, we raise the <code>end</code> event and return.</li>
<li>Now that we've established that the node has neighbors, we iterate through each neighbor. <strong>Side Note:</strong> I reverse the neighbor list (by using <code>graph[node][::-1]</code>) in the recursive version to maintain the same order (right to left) of traversal of neighbors as in the iterative version.

<ol>
<li>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 <em>unless</em> the <em>neighbor</em> contains a repeat count value.</li>
<li>We raise the <code>middle</code> event of the current node (<strong>not</strong> the neighbor) if the second (or greater) neighbor is being processed.</li>
<li>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) <code>MAX_THRESHOLD</code> times (for pseudo-infinite cycles) and b) the above calculated repeat count times.</li>
</ol></li>
<li>We're now done with this node; raise the <code>end</code> 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.</li>
</ol>

python algorithm python-2.7 depth-first-search demoscene