Graph algorithms - DFS, generators callbacks, and optimisation

[Bengt Richter]

On Sat, 29 Nov 2003 10:54:49 +0000, Paul Moore <pf_moore at yahoo.co.uk> wrote:

>I'm trying to check a graph (represented in the usual Python adjacency
>list format) for loops. This is dead simple - you use a depth-first
>search, and look out for "back edges" (edges from a vertex "back" to
>one you've already seen).
>
>I already have a DFS algorithm which generates each edge in turn. It's
>great for what it does, but it ignores back edges.
>
>def DFS(graph, start, seen = None):
>    if not seen:
>	seen = {start: 1}
>    for v in graph[start]:
>	if v not in seen:
>	    seen[v] = 1
>	    yield start, v
>	    if v in graph:
>		for e in DFS(graph, v, seen):
>		    yield e
>
>I could code a variation on this, just for this one problem, but that
>sort of cut and paste coding offends me (and DFS is *just* fiddly
>enough that I'm not confident of getting it right each time I
>reimplement it). So what I'd rather do is enhance my existing code to
>be a bit more general.
>
Not very tested, but how about (borrowing Robin's example data):

====< PaulMoore.py >=============================================
def DFS2(graph, start, rlevel=0, seen = None):
    if seen is None: seen = {}
    seen[start] = 1 # allow for jumping into arbitrary subtrees with
                    # same seen dict in new generator ?
    for v in graph[start]:
        is_back = v in seen
        seen[v] = True # ok if redundant
        yield (start, v), is_back, rlevel
	if not is_back:
	    if v in graph:
		for e in DFS2(graph, v, rlevel+1, seen):
		    yield e

if __name__ == '__main__':
    G = {
            1:      (2,3),
            2:      (3,5),
            3:      (4,),
            4:      (6,),
            5:      (2,6),
            6:      (1,),
            }
    for e, is_back, level in DFS2(G, 1):
        print '%s%s -> %s%s' %(level*'     ',e[0], e[1], ('',' (back)')[is_back])
=================================================================

The output is:

[15:15] C:\pywk\clp>PaulMoore.py
1 -> 2
     2 -> 3
          3 -> 4
               4 -> 6
                    6 -> 1 (back)
     2 -> 5
          5 -> 2 (back)
          5 -> 6 (back)
1 -> 3 (back)

>
>Can anybody think of a good way of making the DFS code above a little 
>more generic, without losing the efficient and simple (from the
>caller's POV) approach of the current version?
>
My .02 above ;-)

Regards,
Bengt Richter