treelib package

Module contents

treelib - Python 2/3 Tree Implementation

treelib is a Python module with two primary classes: Node and Tree. Tree is a self-contained structure with some nodes and connected by branches. A tree owns merely a root, while a node (except root) has some children and one parent.

Note: To solve string compatibility between Python 2.x and 3.x, treelib follows the way of porting Python 3.x to 2/3. That means, all strings are manipulated as unicode and you do not need u’’ prefix anymore. The impacted functions include str(), show() and save2file() routines. But if your data contains non-ascii characters and Python 2.x is used, you have to trigger the compatibility by declaring unicode_literals in the code:

>>> from __future__ import unicode_literals

Submodules

treelib.node module

Node structure in treelib.

A Node object contains basic properties such as node identifier, node tag, parent node, children nodes etc., and some operations for a node.

class treelib.node.Node(tag=None, identifier=None, expanded=True, data=None)

Bases: object

Nodes are elementary objects that are stored in the _nodes dictionary of a Tree. Use data attribute to store node-specific data.

ADD = 0

Mode constants for routine update_fpointer().

DELETE = 1

Mode constants for routine update_fpointer().

INSERT = 2

Mode constants for routine update_fpointer().

REPLACE = 3

Mode constants for routine update_fpointer().

bpointer

The parent ID of a node. This attribute can be accessed and modified with . and = operator respectively.

data = None

User payload associated with this node.

expanded = None

boolean

fpointer

With a getting operator, a list of IDs of node’s children is obtained. With a setting operator, the value can be list, set, or dict. For list or set, it is converted to a list type by the package; for dict, the keys are treated as the node IDs.

identifier

The unique ID of a node within the scope of a tree. This attribute can be accessed and modified with . and = operator respectively.

is_leaf()

Return true if current node has no children.

is_root()

Return true if self has no parent, i.e. as root.

tag

The readable node name for human. This attribute can be accessed and modified with . and = operator respectively.

update_bpointer(nid)

Set the parent (indicated by the nid parameter) of a node.

update_fpointer(nid, mode=0, replace=None)

Update the children list with different modes: addition (Node.ADD or Node.INSERT) and deletion (Node.DELETE).

treelib.tree module

Tree structure in treelib.

The Tree object defines the tree-like structure based on Node objects. A new tree can be created from scratch without any parameter or a shallow/deep copy of another tree. When deep=True, a deepcopy operation is performed on feeding tree parameter and more memory is required to create the tree.

class treelib.tree.Tree(tree=None, deep=False, node_class=None)

Bases: object

Tree objects are made of Node(s) stored in _nodes dictionary.

DEPTH = 1

ROOT, DEPTH, WIDTH, ZIGZAG constants :

ROOT = 0

ROOT, DEPTH, WIDTH, ZIGZAG constants :

WIDTH = 2

ROOT, DEPTH, WIDTH, ZIGZAG constants :

ZIGZAG = 3

ROOT, DEPTH, WIDTH, ZIGZAG constants :

add_node(node, parent=None)

Add a new node object to the tree and make the parent as the root by default.

The ‘node’ parameter refers to an instance of Class::Node.

all_nodes()

Return all nodes in a list

all_nodes_itr()

Returns all nodes in an iterator. Added by William Rusnack

children(nid)

Return the children (Node) list of nid. Empty list is returned if nid does not exist

contains(nid)

Check if the tree contains node of given id

create_node(tag=None, identifier=None, parent=None, data=None)

Create a child node for given @parent node. If identifier is absent, a UUID will be generated automatically.

depth(node=None)

Get the maximum level of this tree or the level of the given node.

@param node Node instance or identifier @return int @throw NodeIDAbsentError

expand_tree(nid=None, mode=1, filter=None, key=None, reverse=False, sorting=True)

Python generator to traverse the tree (or a subtree) with optional node filtering and sorting.

Loosely based on an algorithm from ‘Essential LISP’ by John R. Anderson, Albert T. Corbett, and Brian J. Reiser, page 239-241.

Parameters:

• nid – Node identifier from which tree traversal will start. If None tree root will be used
• mode – Traversal mode, may be either DEPTH, WIDTH or ZIGZAG
• filter – the @filter function is performed on Node object during traversing. In this manner, the traversing will NOT visit the node whose condition does not pass the filter and its children.
• key – the @key and @reverse are present to sort nodes at each level. If @key is None sorting is performed on node tag.
• reverse – if True reverse sorting
• sorting – if True perform node sorting, if False return nodes in original insertion order. In latter case @key and @reverse parameters are ignored.

Returns:

Node IDs that satisfy the conditions

Return type:

generator object

filter_nodes(func)

Filters all nodes by function.

Parameters:func – is passed one node as an argument and that node is included if function returns true, Returns:a filter iterator of the node in python 3 or a list of the nodes in python 2.

Added by William Rusnack.

get_node(nid)

Get the object of the node with ID of nid.

An alternative way is using ‘[]’ operation on the tree. But small difference exists between them: get_node() will return None if nid is absent, whereas ‘[]’ will raise KeyError.

is_ancestor(ancestor, grandchild)

Check if the @ancestor the preceding nodes of @grandchild.

Parameters:

• ancestor – the node identifier
• grandchild – the node identifier

Returns:

True or False

is_branch(nid)

Return the children (ID) list of nid. Empty list is returned if nid does not exist

leaves(nid=None)

Get leaves of the whole tree or a subtree.

level(nid, filter=None)

Get the node level in this tree. The level is an integer starting with ‘0’ at the root. In other words, the root lives at level ‘0’;

Update: @filter params is added to calculate level passing exclusive nodes.

link_past_node(nid)

Delete a node by linking past it.

For example, if we have a -> b -> c and delete node b, we are left with a -> c.

move_node(source, destination)

Move node @source from its parent to another parent @destination.

node_class

alias of treelib.node.Node

nodes

Return a dict form of nodes in a tree: {id: node_instance}.

parent(nid)

Get parent Node object of given id.

paste(nid, new_tree, deep=False)

Paste a @new_tree to the original one by linking the root of new tree to given node (nid).

Update: add @deep copy of pasted tree.

paths_to_leaves()

Use this function to get the identifiers allowing to go from the root nodes to each leaf.

Returns:a list of list of identifiers, root being not omitted.

For example:

Harry
|___ Bill
|___ Jane
|    |___ Diane
|         |___ George
|              |___ Jill
|         |___ Mary
|    |___ Mark

Expected result:

[['harry', 'jane', 'diane', 'mary'],
 ['harry', 'jane', 'mark'],
 ['harry', 'jane', 'diane', 'george', 'jill'],
 ['harry', 'bill']]

remove_node(identifier)

Remove a node indicated by ‘identifier’; all the successors are removed as well.

Return the number of removed nodes.

remove_subtree(nid)

Get a subtree with nid being the root. If nid is None, an empty tree is returned.

For the original tree, this method is similar to remove_node(self,nid), because given node and its children are removed from the original tree in both methods. For the returned value and performance, these two methods are different:

• remove_node returns the number of deleted nodes;
• remove_subtree returns a subtree of deleted nodes;

You are always suggested to use remove_node if your only to delete nodes from a tree, as the other one need memory allocation to store the new tree.

Returns:a Tree object.

root = None

Get or set the identifier of the root. This attribute can be accessed and modified with . and = operator respectively.

rsearch(nid, filter=None)

Traverse the tree branch along the branch from nid to its ancestors (until root).

Parameters:filter – the function of one variable to act on the Node object.

save2file(filename, nid=None, level=0, idhidden=True, filter=None, key=None, reverse=False, line_type='ascii-ex', data_property=None)

Save the tree into file for offline analysis.

show(nid=None, level=0, idhidden=True, filter=None, key=None, reverse=False, line_type='ascii-ex', data_property=None)

Print the tree structure in hierarchy style.

You have three ways to output your tree data, i.e., stdout with show(), plain text file with save2file(), and json string with to_json(). The former two use the same backend to generate a string of tree structure in a text graph.

• Version >= 1.2.7a*: you can also specify the line_type parameter, such as ‘ascii’ (default), ‘ascii-ex’, ‘ascii-exr’, ‘ascii-em’, ‘ascii-emv’, ‘ascii-emh’) to the change graphical form.

Parameters:

• nid – the reference node to start expanding.
• level – the node level in the tree (root as level 0).
• idhidden – whether hiding the node ID when printing.
• filter – the function of one variable to act on the Node object. When this parameter is specified, the traversing will not continue to following children of node whose condition does not pass the filter.
• key – the key param for sorting Node objects in the same level.
• reverse – the reverse param for sorting Node objects in the same level.
• line_type –
• data_property – the property on the node data object to be printed.

Returns:

None

siblings(nid)

Return the siblings of given @nid.

If @nid is root or there are no siblings, an empty list is returned.

size(level=None)

Get the number of nodes of the whole tree if @level is not given. Otherwise, the total number of nodes at specific level is returned.

@param level The level number in the tree. It must be between [0, tree.depth].

Otherwise, InvalidLevelNumber exception will be raised.

subtree(nid)

Return a shallow COPY of subtree with nid being the new root. If nid is None, return an empty tree. If you are looking for a deepcopy, please create a new tree with this shallow copy, e.g.,

new_tree = Tree(t.subtree(t.root), deep=True)

This line creates a deep copy of the entire tree.

to_dict(nid=None, key=None, sort=True, reverse=False, with_data=False)

Transform the whole tree into a dict.

to_graphviz(filename=None, shape='circle', graph='digraph')

Exports the tree in the dot format of the graphviz software

to_json(with_data=False, sort=True, reverse=False)

To format the tree in JSON format.

update_node(nid, **attrs)

Update node’s attributes.

Parameters:

• nid – the identifier of modified node
• attrs – attribute pairs recognized by Node object

Returns:

None

treelib.tree.python_2_unicode_compatible(klass)

(slightly modified from: http://django.readthedocs.org/en/latest/_modules/django/utils/encoding.html)

A decorator that defines __unicode__ and __str__ methods under Python 2. Under Python 3 it does nothing.

To support Python 2 and 3 with a single code base, define a __str__ method returning text and apply this decorator to the class.

treelib.plugins module

This is a public location to maintain contributed utilities to extend the basic Tree class.

Deprecated! We prefer a unified processing of Tree object.

treelib.plugins.export_to_dot(tree, filename=None, shape='circle', graph='digraph')

Exports the tree in the dot format of the graphviz software

treelib.exceptions module

exception treelib.exceptions.DuplicatedNodeIdError

Bases: Exception

Exception throwed if an identifier already exists in a tree.

exception treelib.exceptions.InvalidLevelNumber

Bases: Exception

exception treelib.exceptions.LinkPastRootNodeError

Bases: Exception

Exception throwed in Tree.link_past_node() if one attempts to “link past” the root node of a tree.

exception treelib.exceptions.LoopError

Bases: Exception

Exception thrown if trying to move node B to node A’s position while A is B’s ancestor.

exception treelib.exceptions.MultipleRootError

Bases: Exception

Exception throwed if more than one root exists in a tree.

exception treelib.exceptions.NodeIDAbsentError

Bases: treelib.exceptions.NodePropertyError

Exception throwed if a node’s identifier is unknown

exception treelib.exceptions.NodePropertyAbsentError

Bases: treelib.exceptions.NodePropertyError

Exception throwed if a node’s data property is not specified

exception treelib.exceptions.NodePropertyError

Bases: Exception

Basic Node attribute error