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
>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
More information about the Python-list
mailing list