Recursive structures

[Fredrik Lundh]

<bearophileHUGS at lycos.com> wrote:

> (This is a repost from another python newsgroup).
> While using some nested data structures, I've seen that I'd like to
> have a function that tells me if a given data structure contains one or
> more cyclic references (a way to recognise a cycle in a graph is to do
> a depth-first search, marking vertices along the way. An already marked
> vertex means a cycle.)
> Do you know where I can find a function like this?
> To be more explicit about this function purpose, here are some asserts,
> that call an hypothetical "isrecursive" function (I've added some
> examples of big structures because I'd like such function to be fast
> for them too):
>
> l = [0]
> m = [l, l]
> assert isrecursive(m) == False
>
> assert not isrecursive([[[[1]]]])
>
> h = [0]
> h[0] = h
> print h
> assert isrecursive(h)
>
> n = 2000
> v = [0] * n
> for i in range(n):
> v[i] = [0]
> for i in range(n):
> v[i][0] = v[i]
> assert not (False in map(isrecursive, v) )
>
> n = 10**5
> h = range(n)
> assert not isrecursive(h)
> h[-1] = h
> assert isrecursive(h)
> h[0] = h
> assert isrecursive(h)
>
> h = [0]
> h[0] = h
> h = tuple(h)
> print h
> assert isrecursive(h)
>
> d1 = {"a": 1}
> d1["a"] = d1
> print d1
> assert isrecursive(d1)
>
> # I presume that dict keys cannot be recursive

how about:

def isrecursive(x):
     return "..." in repr(x)

(won't work if the structures can contain arbitrary strings, though...)

</F>