(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
--
http://mail.python.org/mailman/listinfo/python-list
