How to know node execution (before, middle, after calls) using DFS
<p>Let's say I implemented a simple version of an iterative DFS like this:</p>

<pre><code>import sys
import traceback


def dfs(graph, start):
    visited, stack = [], [start]
    while stack:
        node = stack.pop()

        if node not in visited:
            visited.append(node)
            childs = reversed(graph.get(node, list()))
            stack.extend([item for item in childs if item not in visited])

    return visited

if __name__ == "__main__":
    graphs = [
        {
            'A': ['B', 'C'],
            'B': ['D']
        }
    ]

    for i, g in enumerate(graphs):
        try:
            print "{0}Graph {1}{2}".format('-' * 40, i, '-' * 33)

            for f in [dfs]:
                print f.__name__, '--&gt;', f(g, 'A')
                print '-' * 80
        except Exception as e:
            print "Exception in user code: {0}".format(e)
            print '-' * 60
            traceback.print_exc(file=sys.stdout)
            print '-' * 60
</code></pre>

<p>The output of the above snippet is this:</p>

<pre><code>----------------------------------------Graph 0---------------------------------
dfs --&gt; ['A', 'B', 'D', 'C']
--------------------------------------------------------------------------------
</code></pre>

<p>Now, I'm trying to figure out how to get the following output (instead running node's method just printing is fine):</p>

<pre><code>A_start, B_start, D_start, D_end, B_end, A_middle, C_start, C_end, A_end
</code></pre>

<p>*_middle will only be executed between subnodes execution. For instance, if a node doesn't have any subnodes, or has only a single one, it never gets executed. That's why my desired output only has A_middle (none of the B_middle, C_middle, D_middle) in the above example.</p>

<p>How can I do this?</p>

<p><strong>EDIT:</strong></p>

<p>Trying to find the recursive solution to my problem:</p>

<pre><code>def dfs(graph, node):
    if node not in graph:
        return

    print '{0}_start'.format(node)

    for i, node in enumerate(graph[node]):
        if i &gt; 0:
            print '{0}_middle'.format(node)

        dfs(graph, node)

    print '{0}_end'.format(node)

if __name__ == "__main__":
    graphs = [
        {
            'A': ['B', 'C'],
            'B': ['D']
        }
    ]

    for i, g in enumerate(graphs):
        try:
            print "{0}Graph {1}{2}".format('-' * 40, i, '-' * 33)

            for f in [dfs]:
                print f.__name__, '--&gt;'
                f(g, 'A')
                print '-' * 80
        except Exception as e:
            print "Exception in user code: {0}".format(e)
            print '-' * 60
            traceback.print_exc(file=sys.stdout)
            print '-' * 60
</code></pre>

<p>Will give me the wrong output:</p>

<pre><code>----------------------------------------Graph 0---------------------------------
dfs --&gt;
A_start
B_start
D_end
C_middle
C_end
--------------------------------------------------------------------------------
</code></pre>

<p><strong>EDIT2:</strong></p>

<p>I will explain the reasons about my validated answer. First of all, I do really appreciate the effort from all you guys, @Gerrat, @ffledgling and @Blckknght</p>

<p>1) Gerrrat's -> It meets the requirements and it <strong>was the first answer</strong>. At first of my post I had only posted the iterative version but then I edited my question and said a recursive one would be good enough. One little note, when dealing with graphs containing cycles will spawn <code>maximum recursion depth exceeded</code> though. It wouldn't be a bad thing whether I could iterate/repeat infinitely over the graph, take a look to the nodes called <code>repeat</code> of this <a href="http://www.bitfellas.org/e107_plugins/content/content.php?content.674" rel="nofollow">tool</a></p>

<p>2) ffledgling -> It doesn't meet the requirements, it's giving this output <code>A_start, B_start, D_start, D_end, B_middle, B_end, A_middle, C_start, C_end, A_middle, A_end</code> and it should give <code>A_start, B_start, D_start, D_end, B_end, A_middle, C_start, C_end, A_end</code> instead</p>

<p>3) Blckknght -> It meets the requirements. It answers the first version I had posted and it won't crash with cyclic graphs, even if it has been the last answer, I think it deserves to be validated.</p>

<p>NS: It's not an easy decission to validate answers like these ones when they've shown a good effort, I've upvoted all of them though. In case of any concern, please let me know. </p>

<p>I suspect this does what you want.</p>

<pre><code>graphs = [
        {
            'A': ['B', 'C'],
            'B': ['D']
        }
    ]

def dfs(graph, start):
    print '{}_start'.format(start)
    try:
        for child in graph[start]:
            dfs(graph, child)
            print '{}_middle'.format(start)
    except KeyError:
        # We found a leaf node, it has no children.
        pass
    print '{}_end'.format(start)   

# Test it for one graph
dfs(graphs[0], 'A')

# Output:

# A_start
# B_start
# D_start
# D_end
# B_middle
# B_end
# A_middle
# C_start
# C_end
# A_middle
# A_end
</code></pre>

python depth-first-search