convert flat structure into hierarchical one

[Ksenia Marasanova]

I get this kind of list from a database. (The tuple structure is: id,
name, parent_id)

[(1, 'grandparent', None), (2, 'parent', 1), (3, 'otherparent', 1), (4,
'child', 3)]

I would like to transfer it (in Python) into a tree structure. I don't
care much about format, as long as I'll be able to get all the
information, based on one id. For example, if I have id=3, I want to
get
- name ('otherparent')
- children (one child, with id=4, name='child')
- parent id

Any tips? Recipes? ;-)


Thanks,
Ksenia.

 

[Dan Perl]

I started writing a script that would implement a solution to your problem,
but it turned out that it is not so trivial. You have all kind of issues,
depending on whether your structure is sparse or not, and what especially
made me give up (I may still try it later, but right now I don't have the
time) is that you may retrieve a child before its parent, so either you
create a dummy that you update later, or you recursively retrieve all the
ancestors in the tree up to the root of the tree.

Here is my suggestion in brief, though. Implement a class for the tree and
a class for the tree nodes. The 'tree' class keeps a list of instances of
the 'tree node' class. Depending on the sparsity of the tree, you can have
a list indexed by the id's of the nodes (with None for empty spaces), or an
arbitrary list and you do the search for the node in the list that has the
particular id.

The 'tree node' class would have 4 attributes: id, name, parent_id, and
children. 'children' would be a list. BTW, this attribute is not
mandatory, but it is more efficient having it if it is rarely updated but
often accessed.

The 'tree' class would also have a method 'addNode'. In it, create a new
instance of the 'tree node class', add it to the list in the tree and update
the node matching the parent_id. Here is where the complication come in.
You may have to pad the list with 'None' and you may not yet have a node
matching the parent in the 'tree' list. Override the __getitem__ method in
the 'tree' class to retrieve the node based on its id.

Hope this helps.

Dan

 

[Dennis Lee Bieber]

I get this kind of list from a database. (The tuple structure is: id,
name, parent_id)

[(1, 'grandparent', None), (2, 'parent', 1), (3, 'otherparent', 1), (4,
'child', 3)]

Note that your data has "parent" and "otherparent" both linked
to the one "grandparent"... I hope this isn't supposed to represent a

I would like to transfer it (in Python) into a tree structure. I don't
care much about format, as long as I'll be able to get all the
information, based on one id. For example, if I have id=3, I want to
get
- name ('otherparent')
- children (one child, with id=4, name='child')
- parent id

If you truly want it as a tree in Python memory, you'll have to
traverse the tree in other to find any particular node -- especially if
the number of children per node is variable (meaning you can't reserve
ID#s for them -- Genealogical /ancestor/ reporting schemes using
ahnentafel numbering can be computed; for node-n, father is node-n*2,
mother is node-n*2 + 1).

For general usage I'd forget using a literal tree. Stuff the
data in a dictionary using the ID# as the key, and the related data
being the name, parent ID#, list of child ID#s

{3"otherparent", 1, [4])}

--

 

[Ksenia Marasanova]

Thanks to all for helpfull suggestions!
I think I'll use the tree class as Dan suggested, but instead of
creating the list of node instances in advance, will do it on demand.
I'll use the function of Mike in the constructor of the tree, and will
use the resulting data for internal tree searching and node generation.
I think it's much faster then creating all the node instances from the
beginning, and I actually seldom need a whole three, only parts of it.

And no, it's not a genealogical structure .. I used words as 'parent'
and 'child' just to explain the tree structure better. It's for a
website, where all navigation parts are stored in one tree. Until now,
I had a recursive SQL function in PostgreSQL, but with the growing of
the tree (hey, it's alive! ;-) the function is getting slower, so I
want to move it to Python.

Ksenia.