Recursive structures

Discussion in 'Python' started by bearophileHUGS@lycos.com, Dec 20, 2004.

  1. Guest

    (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 = [0]
    for i in range(n):
    v[0] = v
    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
    , Dec 20, 2004
    #1
    1. Advertising

  2. <> 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 = [0]
    > for i in range(n):
    > v[0] = v
    > 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>
    Fredrik Lundh, Dec 20, 2004
    #2
    1. Advertising

  3. 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/
    Thomas Guettler, Dec 20, 2004
    #3
  4. 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
    Scott David Daniels, Dec 20, 2004
    #4
  5. Guest

    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
    , Dec 20, 2004
    #5
  6. 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
    Steven Bethard, Dec 20, 2004
    #6
  7. 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/module-pprint.html#l2h-749
    Leif K-Brooks, Dec 20, 2004
    #7
  8. Guest

    Leif K-Brooks:
    >http://python.org/doc/current/lib/module-pprint.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
    , Dec 20, 2004
    #8
    1. Advertising

Want to reply to this thread or ask your own question?

It takes just 2 minutes to sign up (and it's free!). Just click the sign up button to choose a username and then you can ask your own questions on the forum.
Similar Threads
  1. tweak
    Replies:
    14
    Views:
    2,779
    Eric Sosman
    Jun 11, 2004
  2. Alfonso Morra
    Replies:
    11
    Views:
    713
    Emmanuel Delahaye
    Sep 24, 2005
  3. n00m
    Replies:
    12
    Views:
    1,113
  4. vamsi
    Replies:
    21
    Views:
    2,073
    Keith Thompson
    Mar 9, 2009
  5. dgreig
    Replies:
    6
    Views:
    1,075
    dgreig
    Dec 10, 2009
Loading...

Share This Page