(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

Thank you,

hugs,

Bearophile