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>As per <a href="http://stackoverflow.com/questions/39427638/how-to-traverse-cyclic-directed-graphs-with-modified-dfs-algorithm#comment66244567_39427638">comment66244567</a> - reducing the graph to a tree by ignoring links to visited nodes and performing a breadth-first search, as this would produce a more natural-looking (and likely more balanced) tree:</p>

<pre><code>def traverse(graph,node,process):
    seen={node}
    current_level=[node]
    while current_level:
        next_level=[]
        for node in current_level:
            process(node)
            for child in (link for link in graph.get(node,[]) if link not in seen):
                next_level.append(child)
                seen.add(child)
    current_level=next_level
</code></pre>

<p>With your graph and <code>def process(node): print node</code>, this produces:</p>

<pre><code>In [24]: traverse(cyclic_graph,Sequence1,process)
Sequence1
MtxPushPop1
Rotate1
Sequence2
Repeat1
MtxPushPop2
Translate
Rotate2
Rotate3
Scale
Repeat2
Mesh
</code></pre>

<p>The other BFS algorithm, <a href="http://stackoverflow.com/questions/34821242/non-recursive-breadth-first-traversal-without-a-queue/34821397#34821397">iterative deepening DFS</a> (uses less memory at the cost of speed) isn't going to win you anything in this case: since you have to store references to visited nodes, you already consume <em>O(n)</em> memory. Neither you need to produce intermediate results (but you can anyway - e.g. <code>yield</code> something after processing a level).</p>

python algorithm python-2.7 depth-first-search demoscene