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="https://i.stack.imgur.com/s2DSc.png" rel="nofollow noreferrer"><img src="https://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" rel="nofollow noreferrer">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="https://i.stack.imgur.com/N2OtM.jpg" rel="nofollow noreferrer"><img src="https://i.stack.imgur.com/N2OtM.jpg" alt="enter image description here"></a></p>