<[EMAIL PROTECTED]> 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>
--
http://mail.python.org/mailman/listinfo/python-list
