Prev: vars().has_key() question about how working .
Next: local variable referenced before assignment
From: Steven D'Aprano on 4 Apr 2010 08:10
I have a hierarchical structure something like a directory tree or a
nested tree structure:

Mammal
+-- Ape
: +-- Chimpanzee
: +-- Gorilla
: +-- Human
+-- Carnivore
: +-- Cat
: +-- Tiger
Reptile
+-- Lizard
+-- Snake
+-- Cobra
+-- Python

This is a forest because each top-level element (Mammal, Reptile) is
itself a tree. By adding a root to the (former) top-level elements, I
turn it into a single tree.

I can implement this tree using a flat dict:

root = object()
data = {root: ['Mammal', 'Reptile'],
'Mammal': ['Ape', 'Carnivore'],
'Ape': ['Chimpanzee', 'Gorilla', 'Human'],
'Reptile': ['Lizard', 'Snake'],
# fill in the rest yourself...
}


Is there a particular name for this structure? I've been calling it a
dict-based flattened tree, but I can't shake the feeling that there is
another name for it...



--
Steven
From: Alf P. Steinbach on 4 Apr 2010 08:34
* Steven D'Aprano:
> I have a hierarchical structure something like a directory tree or a
> nested tree structure:
>
> Mammal
> +-- Ape
> : +-- Chimpanzee
> : +-- Gorilla
> : +-- Human
> +-- Carnivore
> : +-- Cat
> : +-- Tiger
> Reptile
> +-- Lizard
> +-- Snake
> +-- Cobra
> +-- Python
>
> This is a forest because each top-level element (Mammal, Reptile) is
> itself a tree. By adding a root to the (former) top-level elements, I
> turn it into a single tree.
>
> I can implement this tree using a flat dict:
>
> root = object()
> data = {root: ['Mammal', 'Reptile'],
> 'Mammal': ['Ape', 'Carnivore'],
> 'Ape': ['Chimpanzee', 'Gorilla', 'Human'],
> 'Reptile': ['Lizard', 'Snake'],
> # fill in the rest yourself...
> }
>
>
> Is there a particular name for this structure? I've been calling it a
> dict-based flattened tree, but I can't shake the feeling that there is
> another name for it...

The only difference from an ordinary tree is that you have a provided a way to
access non-root nodes (with strings as keys) that doesn't work for the root node.

Still, all nodes can be accessed with objects as keys.

So, you have just introduced some ambiguity that allows both views: it's a tree,
and it's a forest, depending on what point of view one chooses.

In passing, this terminology is the one used in programming and computer science.

Donald Knuth notes that for e.g. a binary tree, if one (impractically) adopted
the terminology of some authors on graph theory then one would have to say
"topological bifurcating arborescence" instead of "binary tree"...


Cheers & hth.,

- Alf
From: Duncan Booth on 4 Apr 2010 10:06
Steven D'Aprano <steve(a)REMOVE-THIS-cybersource.com.au> wrote:

> I have a hierarchical structure something like a directory tree or a
> nested tree structure:
>
> Mammal
> +-- Ape
>: +-- Chimpanzee
>: +-- Gorilla
>: +-- Human
> +-- Carnivore
>: +-- Cat
>: +-- Tiger
> Reptile
> +-- Lizard
> +-- Snake
> +-- Cobra
> +-- Python
>
....snip...
> Is there a particular name for this structure? I've been calling it a
> dict-based flattened tree, but I can't shake the feeling that there is
> another name for it...
>
Do you have any carniverous apes? If so it's a directed acyclic graph.
From: Stefan Behnel on 4 Apr 2010 11:18
Steven D'Aprano, 04.04.2010 14:10:
> I have a hierarchical structure something like a directory tree or a
> nested tree structure:
>
> Mammal
> +-- Ape
> : +-- Chimpanzee
> : +-- Gorilla
> : +-- Human
> +-- Carnivore
> : +-- Cat
> : +-- Tiger
> Reptile
> +-- Lizard
> +-- Snake
> +-- Cobra
> +-- Python

Maybe not quite what you asked for, but given the names in the example
above I would call this an ontology.

Stefan

From: Patrick Maupin on 4 Apr 2010 11:41
On Apr 4, 9:06 am, Duncan Booth <duncan.bo...(a)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
 |  Next  |  Last
Pages: 1 2
Prev: vars().has_key() question about how working .
Next: local variable referenced before assignment