Tree traversal
Contents
Traversing the tree and synchronized iteration
Once you have a tree you are happy with, you may want to iterate through it to parse all nodes. The problem is that since a tree is not a linear array, there are more than one way to do so.
The first way is to iterate depth-first. That is, when you meet a node, you are sure that you will parse all of its children and sub-children before parsing its siblings. So you go from the root through the first branch, going as deep as you can until you reach the leaf of that branch. Then you go up just a level, and repeat.
With the tree class, you generate the sequence of indices that will walk you through the tree in a single call:
lineage = tree.example; t = lineage.subtree(19); iterator = t.depthfirstiterator; disp(iterator)
1 2 3 4 5 6 7 8 9 10 11
You see here that we get a line vector of indices. This allows for a simplified syntax for the iteration. Suppose we want to generate a tree that would keep track of the iteration order. A way to do that is the following:
df_order = tree(t, 'clear'); % Generate an empty synchronized tree iterator = t.depthfirstiterator; % Doesn't matter whether you call this on |t| or |df_order| index = 1; for i = iterator df_order = df_order.set(i, index); index = index + 1; end disp(df_order.tostring)
1
+------+--+
| |
2 5
++-+ +---+--+
| | | |
3 4 6 9
++-+ +-+-+
| | | |
7 8 10 11
A second way to traverse the tree is breadth-first. With this iterator, you parse all the nodes of a given depth before going any deeper, regardless of any children a node can have:
bf_order = tree(t, 'clear'); iterator = t.breadthfirstiterator; index = 1; for i = iterator bf_order = bf_order.set(i, index); index = index + 1; end disp(bf_order.tostring)
1
+------+--+
| |
2 3
++-+ +---+--+
| | | |
4 5 6 7
++-+ +-+-+
| | | |
8 9 10 11
The last way available is a dummy one: it simple output the order in which the nodes have been added to the tree at construction time.
na_order = tree(t, 'clear'); iterator = t.nodeorderiterator; index = 1; for i = iterator na_order = na_order.set(i, index); index = index + 1; end disp(na_order.tostring)
1
+------+--+
| |
2 5
++-+ +---+--+
| | | |
3 4 6 9
++-+ +-+-+
| | | |
7 8 10 11
Note that in all cases we generated the whole iterating sequence, then used it to actually iterate. If between the call and the iteration you add or remove nodes to the tree, you will completely mess up the calculated iteration order or generate an error. Look above for the section about synchronized tree for the forbidden methods.
Another important perk is that the iteration sequence is the same for synchronized trees, a simple consequence of using copy trees. That is useful and important for trees depicting multiple properties of a common object.
[ lineage, duration ] = tree.example; % 1st one is made of strings only, 2nd one of integers iterator = lineage.breadthfirstiterator; for i = iterator(1:7) % print only he first 7 cells fprintf('The cell %s has an interphase duration of %d minutes.\n', ... lineage.get(i), ... duration.get(i)) end
The cell Zygote has an interphase duration of 13 minutes. The cell AB has an interphase duration of 10 minutes. The cell P1 has an interphase duration of 17 minutes. The cell AB.a has an interphase duration of 16 minutes. The cell AB.p has an interphase duration of 1 minutes. The cell P2 has an interphase duration of 16 minutes. The cell EMS has an interphase duration of 14 minutes.
Of course, two plain arrays could have yielded the same result. But for this problem, the hierarchy is important, and this is the benefit of using trees. For instance:
slin = lineage.subtree(19); % Work on a subset sdur = duration.subtree(19); resTree = tree(slin, 'clear'); iterator = resTree.depthfirstiterator; for i = iterator resTree = resTree.set(i, sprintf('%s: (%d min)', ... slin.get(i), ... sdur.get(i))); end disp(resTree.tostring)
EMS: (14 min)
+------------------------------+---------------+
| |
MS: (1 min) E: (2 min)
+------+-------+ +---------------+---------------+
| | | |
MS.a: (1 min) MS.p: (10 min) E.a: (16 min) E.p: (3 min)
+-------+-------+ +-------+-------+
| | | |
E.al: (16 min) E.ar: (14 min) E.pl: (13 min) E.pr: (10 min)
Finding the shortest path between two nodes
Path finding is classic problems in graphs where you have two nodes and want to find the path to reach one from the other. The path is simply the ordered sequence of the nodes to traverse.
For our tree class, do not expect anything fancy like Dijkstra algorithm: the tree is a very simple specialization of a graph. The findpath method is the only one available right now, and return the shortest path in terms of number of edges:
% Find the path between node 'ABplp' and node 'Ca' lineage = tree.example; n1 = find(lineage.strcmp('AB.plp')); n2 = find(lineage.strcmp('C.a')); path = lineage.findpath(n1, n2) %#ok<NOPTS> pt = tree(lineage, 'clear'); index = 1; for i = path pt = pt.set(i, index); index = index + 1; end disp(pt.tostring)
path =
14 11 4 2 1 17 18 21 22
5
+------------------+------------+
| |
4 6
+-----+-----+ +-------+----------+
| | | |
ø 3 7 ø
+--+--+ +--+--+ +----+----+ +-----+--+
| | | | | | | |
ø ø 2 ø ø 8 ø ø
++-+ ++-+ ++-+ ++-+ ++---+ +--+--+ ++-+ +--+--+
| | | | | | | | | | | | | | | |
ø ø ø ø ø 1 ø ø ø ø 9 ø ø ø ø ø
++-+ ++-+ ++-+ ++-+ ++-+
| | | | | | | | | |
ø ø ø ø ø ø ø ø ø ø
Orienting yourself in the tree
When traversing a tree, a few methods will help you to know where you are:
- getparent(node) return the index of the parent node. The root node has a parent index equals to 0.
- getchildren(node) return the list of the children of this node. Leaf nodes get an empty list. The list is returned as a line vector.
- isleaf(node) return true is this node is a leaf node.
Back to main page.