448,677 Members | 1,217 Online Need help? Post your question and get tips & solutions from a community of 448,677 IT Pros & Developers. It's quick & easy.

# Recursive structures

 P: n/a (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 =  m = [l, l] assert isrecursive(m) == False assert not isrecursive([[[]]]) h =  h = h print h assert isrecursive(h) n = 2000 v =  * n for i in range(n): v[i] =  for i in range(n): v[i] = 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 = h assert isrecursive(h) h =  h = 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 Jul 18 '05 #1
7 Replies

 P: n/a 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 =  m = [l, l] assert isrecursive(m) == False assert not isrecursive([[[]]]) h =  h = h print h assert isrecursive(h) n = 2000 v =  * n for i in range(n): v[i] =  for i in range(n): v[i] = 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 = h assert isrecursive(h) h =  h = 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...) Jul 18 '05 #2

 P: n/a Am Mon, 20 Dec 2004 04:22:24 -0800 schrieb bearophileHUGS: 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 Hi, does this help you? from types import * def isrecursive(obj, dict=None): if dict==None: dict={} mytype=type(obj) if mytype in [GeneratorType, SliceType]: obj=list(obj) mytype=ListType l=[] MethodWrapperType=type(l.__delattr__) if type(obj) in [NoneType, TypeType, BooleanType, IntType, LongType, FloatType, ComplexType, StringType, UnicodeType, FunctionType, CodeType, ClassType, MethodType, UnboundMethodType, BuiltinMethodType, BuiltinFunctionType, ModuleType, FileType, XRangeType, EllipsisType, TracebackType, FrameType, BufferType, StringType, MethodWrapperType, MethodWrapperType]: return 0 myid=id(obj) if dict.has_key(myid): return 1 dict[myid]=1 for attr in dir(obj): value=getattr(obj, attr) if isrecursive(value, dict): return 1 try: for item in obj: if isrecursive(item, dict): return 1 except TypeError: pass try: for key, value in obj.items(): if isrecursive(value, dict): return 1 except AttributeError: pass return 0 def test_isrecursive(): s="sdf" assert(not isrecursive(s)) l=[] assert(not isrecursive(l)) l.append(l) assert(isrecursive(l)) print "OK" d={} assert(not isrecursive(d)) d["foo"]=() assert(not isrecursive(d)) d["foo2"]="foo2" assert(not isrecursive(d)) d["foo3"]=d assert(isrecursive(d)) if __name__=="__main__": test_isrecursive() -- Thomas Güttler, http://www.thomas-guettler.de/ Jul 18 '05 #3

 P: n/a Thomas Guettler wrote: code to do the test The following transformation of his code shows how exceptions can be used to make code read more clearly. There are a few issues (such as AVOIDITER) to decide on, and usually you are inquiring about your own data structures (which you'll know more about). Recursive data structures, like deepcopy, are matters of interpretation of data, and cannot really be answered without knowing what you mean by your data (and possibly why you are inquiring). I have also done a few things to speed up the code (my premature optimization sin) such as lifting constant expressions to module load time. from types import * MethodWrapperType = type([].__delattr__) LEAVES = set([NoneType, TypeType, BooleanType, IntType, LongType, FloatType, ComplexType, StringType, UnicodeType, FunctionType, CodeType, ClassType, MethodType, UnboundMethodType, BuiltinMethodType, BuiltinFunctionType, ModuleType, FileType, XRangeType, EllipsisType, TracebackType, FrameType, BufferType, StringType, MethodWrapperType, MethodWrapperType]) FORCELIST = set([GeneratorType, SliceType]) # these are dicey: can cause lots of side-effects AVOIDITER = set() # Here go things like itertools.count -- infinite generators class RecursionFoundError(Exception): pass def walks(obj, seen): identity = id(obj) if identity in seen: raise RecursionFoundError, obj mytype = type(obj) if mytype in LEAVES: return seen = seen.copy() # (obj, obj) is not recursive, so new copy seen.add(identity) if mytype in FORCELIST: obj = list(obj) # this is a new obj, so not in the structure mytype = ListType for attr in dir(obj): walks(getattr(obj, attr), seen) if mytype not in AVOIDITER: try: for item in obj: walks(item, seen) except TypeError: pass try: for key, value in obj.items(): walks(key, seen) # Key might be object w/ hash method walks(value, seen) except AttributeError: pass def isrecursive(obj): try: walks(obj, set()) except RecursionFoundError, err: return True # err.args is the looping object return False --Scott David Daniels Sc***********@Acm.Org Jul 18 '05 #4

 P: n/a Thank you very much Thomas Güttler for you quick answer, but I think your program doesn't contain an algorithm to spot cycles (like the usual cyclic graph algorithm). In my first post there was an assert to spot this problem: l =  m = [l, l] print m print isrecursive(m) Gives: [, ] 1 m contains a shared reference, but not a recursive one. Thank you Fredrik Lundh too, bear hugs, Bearophile Jul 18 '05 #5

 P: n/a Scott David Daniels wrote: if mytype not in AVOIDITER: try: for item in obj: walks(item, seen) except TypeError: pass try: for key, value in obj.items(): walks(key, seen) # Key might be object w/ hash method walks(value, seen) except AttributeError: pass You might also write this section something like: if mytype not in AVOIDITER: try: itr = iter(obj) except TypeError: pass else: for item in itr: walks(item, seen) try: walks(obj[item], seen) except TypeError: pass This should allow you to support any mapping type that supports iter() over the keys and the __getitem__ protocol. Steve Jul 18 '05 #6

 P: n/a be************@lycos.com wrote: 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? http://python.org/doc/current/lib/mo...t.html#l2h-749 Jul 18 '05 #7

 P: n/a Leif K-Brooks:http://python.org/doc/current/lib/mo...t.html#l2h-749 Thank you very much, I see that the function is already there, even with the same name :-) I've seen that it doesn't work for all my tests, like this one with n = 3000: from pprint import isrecursive from time import clock n = 950 print "n =", n l = [] for i in xrange(n): l = [n-i, l] if n < 30: print l t = clock() assert not isrecursive(l) print round(clock()-t, 3), "s" In the function _safe_repr of the pprint.py module there is a recursive call: orepr, oreadable, orecur = _safe_repr(o, context, maxlevels, level) Probably this _safe_repr function can be modified (with a lot of work?) to be iterative (using a list as a stack) to avoid such stack overflows (the list too can overflow, but its capacity is enough for most purposes). Python doesn't have C-like unsafe buffer overrun, so using a list as stack probably improves security a little, and probably makes _safe_repr faster. See you, Bearophile Jul 18 '05 #8

### This discussion thread is closed

Replies have been disabled for this discussion.

### Similar topics

Browse more Python Questions on Bytes 