# Graph algorithms - DFS, generators callbacks, and optimisation

Bengt Richter bokr at oz.net
Sun Nov 30 00:03:37 CET 2003

```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
>
>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

```