Walking an object/reference graph

[MRAB]

Austin Bingham wrote:
> I'm looking for the proper way to "walk" a graph of python objects. My
> specific task is to find all objects of a given type that are referred
> to (transitively) by some starting object. My approach has been to
> loop through the object's attributes, examining each, and then
> recursing on them.
> 
> This approach has immediate problems in that I immediately hit
> infinite recursion due to method-wrappers; I'm not sure *exactly*
> what's going on, but it appears that method-wrappers refer to
> method-wrappers ad infinitum. If I add code to avoid this issue,
> others soon crop up, so before I wrote too much more code, I thought
> I'd check with experts to see if there's a better way.
> 
> So, if I've explained what I'm looking for well enough, does anyone
> know of a proper way to walk a graph of object references? I need to
> support cycles in the graph, so keeping track of visited object IDs or
> something will have to be employed. Also, I need to be able to follow
> references stored in lists, dictionaries, etc...basically any way to
> programatically get from one object to another should be followed by
> the algorithm. I feel like I'm missing something simple, but perhaps
> this is just a tricky problem for python. Any ideas or insight would
> be great. Thanks!
> 
Keep a set of the objects you've visited (that will have to be a set of
the object ids because not all objects are hashable) and a
list/stack/queue of the objects you haven't checked yet, and then
iterate until the list/etc is empty.