libbe.util.tree

Define Tree, a traversable tree structure.

class libbe.util.tree.Tree

A traversable tree structure.

Examples

Construct:

  +-b---d-g
a-+   +-e
  +-c-+-f-h-i

with

>>> i = Tree();       i.n = "i"
>>> h = Tree([i]);    h.n = "h"
>>> f = Tree([h]);    f.n = "f"
>>> e = Tree();       e.n = "e"
>>> c = Tree([f,e]);  c.n = "c"
>>> g = Tree();       g.n = "g"
>>> d = Tree([g]);    d.n = "d"
>>> b = Tree([d]);    b.n = "b"
>>> a = Tree();       a.n = "a"
>>> a.append(c)
>>> a.append(b)

Get the longest branch length with

>>> a.branch_len()
5

Sort the tree recursively. Here we sort longest branch length first.

>>> a.sort(key=lambda node : -node.branch_len())
>>> "".join([node.n for node in a.traverse()])
'acfhiebdg'

And here we sort shortest branch length first.

>>> a.sort(key=lambda node : node.branch_len())
>>> "".join([node.n for node in a.traverse()])
'abdgcefhi'

We can also do breadth-first traverses.

>>> "".join([node.n for node in a.traverse(depth_first=False)])
'abcdefghi'

Serialize the tree with depth marking branches.

>>> for depth,node in a.thread():
...     print "%*s" % (2*depth+1, node.n)
a
  b
    d
      g
  c
    e
    f
      h
        i

Flattening the thread disables depth increases except at branch splits.

>>> for depth,node in a.thread(flatten=True):
...     print "%*s" % (2*depth+1, node.n)
a
  b
  d
  g
c
  e
f
h
i

We can also check if a node is contained in a tree.

>>> a.has_descendant(g)
True
>>> c.has_descendant(g)
False
>>> a.has_descendant(a)
False
>>> a.has_descendant(a, match_self=True)
True

Methods

append	L.append(object) – append object to end
branch_len()	Return the largest number of nodes from root to leaf (inclusive).
count(...)
extend	L.extend(iterable) – extend list by appending elements from the iterable
has_descendant(descendant[, depth_first, ...])	Check if a node is contained in a tree.
index((value, [start, ...)	Raises ValueError if the value is not present.
insert	L.insert(index, object) – insert object before index
pop(...)	Raises IndexError if list is empty or index is out of range.
remove	L.remove(value) – remove first occurrence of value.
reverse	L.reverse() – reverse IN PLACE
sort(*args, **kwargs)	Sort the tree recursively.
thread([flatten])	Generate a (depth, node) tuple for every node in the tree.
traverse([depth_first])	Generate all the nodes in a tree, starting with the root node.

branch_len()

Return the largest number of nodes from root to leaf (inclusive).

For the tree:

  +-b---d-g
a-+   +-e
  +-c-+-f-h-i

this method returns 5.

Notes

Exhaustive search every time == slow.

Use only on small trees, or reimplement by overriding child-addition methods to allow accurate caching.

has_descendant(descendant, depth_first=True, match_self=False)

Check if a node is contained in a tree.

Parameters :

descendant : Tree

The potential descendant.

depth_first : bool

The search order. Set this if you feel depth/breadth would be a faster search.

match_self : bool

Set to True for:

x.has_descendant(x, match_self=True) -> True

sort(*args, **kwargs)

Sort the tree recursively.

This method extends list.sort() to Trees.

Notes

This method can be slow, e.g. on a branch_len() sort, since a node at depth N from the root has it’s branch_len() method called N times.

thread(flatten=False)

Generate a (depth, node) tuple for every node in the tree.

When flatten is False, the depth of any node is one greater than the depth of its parent. That way the inheritance is explicit, but you can end up with highly indented threads.

When flatten is True, the depth of any node is only greater than the depth of its parent when there is a branch, and the node is not the last child. This can lead to ancestry ambiguity, but keeps the total indentation down. For example:

  +-b                  +-b-c
a-+-c        and     a-+
  +-d-e-f              +-d-e-f

would both produce (after sorting by branch_len()):

(0, a)
(1, b)
(1, c)
(0, d)
(0, e)
(0, f)

traverse(depth_first=True)

Generate all the nodes in a tree, starting with the root node.

Parameters :

depth_first : bool

Depth first by default, but you can set depth_first to False for breadth first ordering. Siblings are returned in the order they are stored, so you might want to sort() your tree first.