Graph algorithms - DFS, generators callbacks, and optimisation

[Robin Becker]

Well in this case couldn't you make seen do the detection for you.
If I understand your analysis you could make the seen dictionary a
special kind of dictionary.

ie

class DFSSeen(dict):
        def __contains__(self,x):
                r = super(DFSSeen,self).__contains__(x)
                if r:
                        print 'back link to',x
                return r



G = {
        1:      (2,3),
        2:      (3,5),
        3:      (4,),
        4:      (6,),
        5:      (2,6),
        6:      (1,),
        }
for v in DFS(G,1,DFSSeen({1:1})):
        print v

using the above I get
C:\tmp>dfs.py
(1, 2)
(2, 3)
(3, 4)
(4, 6)
back link to 1
(2, 5)
back link to 2
back link to 6
back link to 3

so cycle detection is possible without altering the original code, but
it probably isn't sufficient for your purposes in that we don't have the
start vertex.

In article <oeuvcume.fsf at yahoo.co.uk>, Paul Moore <pf_moore at yahoo.co.uk>
writes


>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.
>
>I have a C++ reference which implements a highly general DFS
>algorithm, using the visitor pattern (pass a visitor object to the
>function, and various callback methods are called at points in the
>algorithm - there are discover_vertex, discover_edge, back_edge, etc
>callbacks).
>
>I could code something like this (the pseudocode for the algorithm is
>almost executable in Python!) but it doesn't feel particularly
>"pythonic". Having to write a visitor class for each use case feels
>unwieldy (as well as being perceptibly slower than the generator
>implementation). Having the various callbacks as arguments (pass a
>callable or None) isn't much faster or cleaner.
>
>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?
>
>Paul.

-- 
Robin Becker