On Apr 4, 9:06 am, Duncan Booth <duncan.bo...@invalid.invalid> wrote: > Do you have any carniverous apes? If so it's a directed acyclic graph.
Well, since he has a root node, he's really only described the *use* of this data structure implementation for a rooted tree. As you point out, the implementation itself is more general than a rooted tree, and could be used for any DAG. But you don't go far enough. This particular implementation could be used for any directed graph -- there is nothing (other than the problem domain) requiring that data in this dict be acyclic. In fact, there are sometimes good reasons for using this sort of structure for cyclic data. Having a name for each node, and always indirectly referring to the node by its name, can sometimes greatly simplify the implementation of problems requiring a cyclic graph (starting with the really basic problem of wanting to dump the whole structure out in a reasonable fashion for debugging). The primary differences between this structure and just haphazardly wiring up random objects into a directed graph are that (1) there may be some performance differences (but when the garbage collector has to figure out how to break cycles, these difference might or might not be in the direction you expect) and (2) with this structure, every object needs a globally unique name for indexing purposes. Having said all that, I don't know what the proper name for this data structure is, either :-) However, in determining the name, I would probably focus on the data structure being represented (in Steven's case, a tree), and the data structure used to represent it (a Python dict), and *why/how* the underlying structure is used. So I would probably call it something like an "associatively addressed tree". Regards, Pat -- http://mail.python.org/mailman/listinfo/python-list
