Trees

[Brian van den Broek]

Alex Le Dain said unto the world upon 2005-02-27 19:54:
>  > Would this be for a GUI toolkit or maybe using a standard
>  > class scheme?
> 
> Sorry, yes I should have been more specific. I meant a non-GUI, standard 
> class scheme. I want to use the scheme to hold a structure in memory and 
> retrieve/add information to it.
> 
> I've had a couple of goes myself but get a bit confuesd about whether I 
> should use recursion to be able to get the children (and all 
> "sub"-children) of a/the parent.
> 
> cheers, Alex.
> 

Hi Alex,

I've been working on a set of tools for dealing with a tree structure.
I am no python expert -- in fact, the program I am working on is my
first serious us of classes. Anyway, though I've not been following
your thread, I also think that perhaps you might find the code I have
of some use. Use caution though; newbie code below :-)

I am working with a data format from a shareware application that puts
the tree in a flat text file, where each node has a header section,
including a unique node id and a level indicator. (Level 0 for the
root, level 1 for the roots children, etc.) My code is a work in
progress and not heavily tested, but it seems to work :-) I've a class
Tree_file with a .nodes attribute which is a list of Node objects (in
top-down tree order). It has a method:

.# leading periods to preserve indentation
.def update_family(self):
.    '''Starting from node, updates each nodes .children and
descendants set.'''
.    for node in self.nodes:
.        node.get_children(self)
.    for node in self.nodes:
.        node.get_descendants()

My Node class has methods giving each node object a node.id and
node.level (both ints). The other relevant attributes are
node.children, and node.descendants (both sets).
(I've got reasons to often process just a node's children, rather than
  all descendants; thus, it makes sense for my program to have the two
attributes.)

The two relevant methods are:

.def get_children(self, parent_file):
.    '''Sets the node's .children set attribute.
.
.    Scans the list of Node objects in parent_file.nodes until self
.    node is found (by comparison of node.id attributes). Then the
.    capture_children flag is set to True, and, for each node exactly
.    one node.level deeper, that deeper node is added to the
.    self.children set. This goes on until the first node not below
.    the self node is found.
.    '''
.    capture_children = False
.    children = set()
.
.    for node in parent_file.nodes:
.        if capture_children and not node.level > self.level:
.            break
.        if capture_children and node.level == self.level + 1:
.            children.add(node)
.        if self.id == node.id:
.            capture_children = True
.
.    self.children = children

and

.def get_descendants(self):
.    '''Updates each nodes .descendants set to current value.
.
.    Recursive call of get_descendants on a node's children, adding
.    all to the .descendants set (of the target node).
.    '''
.    descendants = self.children.copy()
.    for node in self.children:
.        node.get_descendants()
.        for n in node.descendants:
.            descendants.add(n)
.    self.descendants = descendants

Anyway, all caveats notwithstanding, I hope that is of some use to
you. Best,

Brian vdB