On 17 December 2012 23:44, Oscar Benjamin <oscar.j.benja...@gmail.com> wrote:
> On 17 December 2012 23:08, MRAB <pyt...@mrabarnett.plus.com> wrote:
>> Wouldn't a set of the id of the visited objects work?
>
> Of course it would. This is just a tree search.
>
> Here's a depth-first-search function:
>
> def dfs(root, childfunc, func):
> '''depth first search on a tree
> calls func(node) once for each node'''
> visited = set()
> visiting = OrderedDict()
> visiting[id(root)] = it = iter([root])
>
> while True:
> try:
> node = next(it)
> except StopIteration:
> try:
> node, it = visiting.popitem()
> except KeyError:
> return
> key = id(node)
> if isinstance(node, dict) and key not in visited:
> func(node)
> visiting[key] = it = iter(childfunc(node))
> visited.add(key)
>
> Now you can do:
>
> dfs(my_dict_tree, lambda x: x.pop('Favicon', None))
Slight correction:
dfs(g, lambda n: n.values(), lambda x: x.pop('Favicon', None))
Oscar
--
http://mail.python.org/mailman/listinfo/python-list
