Velocity Reviews - Computer Hardware Reviews

Velocity Reviews > Newsgroups > Programming > Python > Recursive structures

Reply
Thread Tools

Recursive structures

 
 
bearophileHUGS@lycos.com
Guest
Posts: n/a
 
      12-20-2004
(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

 
Reply With Quote
 
 
 
 
Fredrik Lundh
Guest
Posts: n/a
 
      12-20-2004
<(E-Mail Removed)> 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>



 
Reply With Quote
 
 
 
 
Thomas Guettler
Guest
Posts: n/a
 
      12-20-2004
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/


 
Reply With Quote
 
Scott David Daniels
Guest
Posts: n/a
 
      12-20-2004

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[0] is the looping object
return False


--Scott David Daniels
http://www.velocityreviews.com/forums/(E-Mail Removed)
 
Reply With Quote
 
bearophileHUGS@lycos.com
Guest
Posts: n/a
 
      12-20-2004
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 = [0]
m = [l, l]
print m
print isrecursive(m)

Gives:
[[0], [0]]
1

m contains a shared reference, but not a recursive one.
Thank you Fredrik Lundh too,
bear hugs,
Bearophile

 
Reply With Quote
 
Steven Bethard
Guest
Posts: n/a
 
      12-20-2004
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
 
Reply With Quote
 
Leif K-Brooks
Guest
Posts: n/a
 
      12-20-2004
(E-Mail Removed) 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
 
Reply With Quote
 
bearophileHUGS@lycos.com
Guest
Posts: n/a
 
      12-20-2004
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

 
Reply With Quote
 
 
 
Reply

Thread Tools

Posting Rules
You may not post new threads
You may not post replies
You may not post attachments
You may not edit your posts

BB code is On
Smilies are On
[IMG] code is On
HTML code is Off
Trackbacks are On
Pingbacks are On
Refbacks are Off


Similar Threads
Thread Thread Starter Forum Replies Last Post
Recursive structures and Quartus? dgreig VHDL 6 12-10-2009 11:48 AM
Recursive functions Vs Non-recursive functions - performance aspect vamsi C Programming 21 03-09-2009 10:53 PM
Two recursive calls inside of a recursive function n00m C++ 12 03-13-2008 03:18 PM
structures, structures and more structures (questions about nestedstructures) Alfonso Morra C Programming 11 09-24-2005 07:42 PM
Type Casting IPv4 and IPv6 structures to Generic Structures tweak C Programming 14 06-11-2004 02:43 PM



Advertisments