# Tree Graph¶

Tree graphs represent trees as undirected rooted graphs.

 TreeCategory Category of hierarchies. Tree An optimized static tree structure with nodes stored linearly in topological order (from leaves to root).
class TreeCategory

Category of hierarchies.

Members:

ComponentTree

PartitionTree

ComponentTree = <TreeCategory.ComponentTree: 0>
PartitionTree = <TreeCategory.PartitionTree: 1>
property name
class Tree

An optimized static tree structure with nodes stored linearly in topological order (from leaves to root).

__init__(*args, **kwargs)

Overloaded function.

1. __init__(self: higra.higram.Tree, parent_relation: numpy.ndarray[numpy.int8], category: higra.higram.TreeCategory = <TreeCategory.PartitionTree: 1>) -> None

Create a tree from the given parent relation.

1. __init__(self: higra.higram.Tree, parent_relation: numpy.ndarray[numpy.uint8], category: higra.higram.TreeCategory = <TreeCategory.PartitionTree: 1>) -> None

2. __init__(self: higra.higram.Tree, parent_relation: numpy.ndarray[numpy.int16], category: higra.higram.TreeCategory = <TreeCategory.PartitionTree: 1>) -> None

3. __init__(self: higra.higram.Tree, parent_relation: numpy.ndarray[numpy.uint16], category: higra.higram.TreeCategory = <TreeCategory.PartitionTree: 1>) -> None

4. __init__(self: higra.higram.Tree, parent_relation: numpy.ndarray[numpy.int32], category: higra.higram.TreeCategory = <TreeCategory.PartitionTree: 1>) -> None

5. __init__(self: higra.higram.Tree, parent_relation: numpy.ndarray[numpy.uint32], category: higra.higram.TreeCategory = <TreeCategory.PartitionTree: 1>) -> None

6. __init__(self: higra.higram.Tree, parent_relation: numpy.ndarray[numpy.int64], category: higra.higram.TreeCategory = <TreeCategory.PartitionTree: 1>) -> None

7. __init__(self: higra.higram.Tree, parent_relation: numpy.ndarray[numpy.uint64], category: higra.higram.TreeCategory = <TreeCategory.PartitionTree: 1>) -> None

adjacent_vertices(self: higra.higram.Tree, vertex: int) → Iterator

Iterator over all vertices adjacent to the given vertex.

ancestors(self: higra.higram.Tree, node: int) → xt::xtensor

Get the list of ancestors of the given node in topological order (starting from the given node included).

category(self: higra.higram.Tree) → higra.higram.TreeCategory

Get the tree category (see enumeration TreeCategory)

child(index, vertex=None)

Get the index-th (starting at 0) child of the given vertex/array of vertices.

If vertex is None, the function will return the index-th child of every non leaf node of the tree.

Parameters
• index – positive integer

• vertex – a vertex index or a 1d array of vertex indices (default to np.arange(self.num_leaves(), self.num_vertices())

Returns

a vertex index or a 1d array of vertex indices

children(self: higra.higram.Tree, node: int) → xt::xtensor

Get a copy of the list of children of the given node.

clear_children(self: higra.higram.Tree) → None

Remove the children relation if it has already been computed. May free memory but only useful if you are sure that this relation won’t be required by further processing).

degree(*args, **kwargs)

Overloaded function.

1. degree(self: higra.higram.Tree, vertex: int) -> int

Return the degree of the given vertex.

1. degree(self: higra.higram.Tree, vertices_array: numpy.ndarray[numpy.int32]) -> xt::xtensor

Return the degree of the given vertices.

1. degree(self: higra.higram.Tree, vertices_array: numpy.ndarray[numpy.uint32]) -> xt::xtensor

2. degree(self: higra.higram.Tree, vertices_array: numpy.ndarray[numpy.int64]) -> xt::xtensor

3. degree(self: higra.higram.Tree, vertices_array: numpy.ndarray[numpy.uint64]) -> xt::xtensor

edge_from_index(self: higra.higram.Tree, edge_index: int) → tuple

Get an edge from its index.

edge_list()

Returns a tuple of two arrays (sources, targets) defining all the edges of the graph.

Example

>>> t = Tree((5, 5, 6, 6, 6, 7, 7, 7))
>>> t.edge_list()
(array([0, 1, 2, 3, 4, 5, 6]), array([5, 5, 6, 6, 6, 7, 7]))

Returns

pair of two 1d arrays

edges(self: higra.higram.Tree) → Iterator

Iterator over all edges of the graph.

find_region(vertex, level, altitudes)

Searches for the largest node of altitude lower than the given level and containing the given vertex. If no such node exists the given vertex is returned.

Parameters
• vertex – a vertex or a 1d array of vertices

• level – a level or a 1d array of levels (should have the same dtype as altitudes)

• altitudes – altitudes of the nodes of the tree

Returns

a vertex or a 1d array of vertices

in_degree(*args, **kwargs)

Overloaded function.

1. in_degree(self: higra.higram.Tree, vertex: int) -> int

Return the in degree of the given vertex.

1. in_degree(self: higra.higram.Tree, vertices_array: numpy.ndarray[numpy.int32]) -> xt::xtensor

Return the in degree of the given vertices.

1. in_degree(self: higra.higram.Tree, vertices_array: numpy.ndarray[numpy.uint32]) -> xt::xtensor

2. in_degree(self: higra.higram.Tree, vertices_array: numpy.ndarray[numpy.int64]) -> xt::xtensor

3. in_degree(self: higra.higram.Tree, vertices_array: numpy.ndarray[numpy.uint64]) -> xt::xtensor

in_edges(self: higra.higram.Tree, vertex: int) → Iterator

Iterator over all in edges from ‘vertex’. An in edge is a tuple ‘(adjacent_vertex, vertex)’.

index(self: higra.higram.Tree, edge: tuple) → detail::accessor<detail::accessor_policies::tuple_item>

Get the index of an edge.

is_leaf(*args, **kwargs)

Overloaded function.

1. is_leaf(self: higra.higram.Tree, vertex: int) -> bool

Returns true if the given node is a leaf of true and false otherwise.

1. is_leaf(self: higra.higram.Tree, vertices: numpy.ndarray[numpy.int32]) -> xt::xtensor

Indicates if each vertex in the given array is a leaf or not.

1. is_leaf(self: higra.higram.Tree, vertices: numpy.ndarray[numpy.uint32]) -> xt::xtensor

2. is_leaf(self: higra.higram.Tree, vertices: numpy.ndarray[numpy.int64]) -> xt::xtensor

3. is_leaf(self: higra.higram.Tree, vertices: numpy.ndarray[numpy.uint64]) -> xt::xtensor

leaves(self: higra.higram.Tree) → Iterator

Returns an iterator on leaves of the tree.

leaves_to_root_iterator(self: higra.higram.Tree, include_leaves: bool = True, include_root: bool = True) → Iterator

Returns an iterator on the node indices going from the leaves to the root of the tree.

lowest_common_ancestor(vertices1, vertices2)

Compute the lowest common ancestor between pairs of vertices defined by vertices1 and vertices2.

vertices1 and vertices2 must be either:

• two positive integers strictly smaller than the number of vertices in the tree;

• two 1d arrays of positive integers strictly smaller than the number of vertices in the tree and of the same size.

Complexity

The worst case time complexity is $$\mathcal{O}(qn)$$ with $$q$$ the number of lowest ancestors to compute and $$n$$ the number of vertices in the tree.

If many lowest ancestors are needed, this time complexity can be reduced to $$\mathcal{O}(q)$$ at the cost of a linearithmic time $$\mathcal{O}(n\log(n))$$ preprocessing by calling the function lowest_common_ancestor_preprocess().

Parameters
• vertices1 – a vertex index or an array of vertex indices

• vertices2 – a vertex index or an array of vertex indices

Returns

the lowest common ancestor(s) of every pair of input vertices (a single index or an array of indices)

lowest_common_ancestor_preprocess(algorithm='sparse_table_block', block_size=1024, force_recompute=False)

Preprocess the tree to obtain a fast constant time $$\mathcal{O}(1)$$ lowest common ancestor query. Once this function has been called on a given tree instance, every following calls to the function lowest_common_ancestor() will use this preprocessing. Calling twice this function does nothing except if force_recompute is True.

Two algorithms are available:

• sparse_table has a preprocessing time and space complexity in $$\mathcal{O}(n\log(n))$$ with $$n$$ the number of vertices in the tree and performs every query in constant time $$\mathcal{O}(1)$$.

• sparse_table_block (default) has a linear preprocessing time and space complexity in $$\mathcal{O}(n)$$ and performs queries in average-case constant time $$\mathcal{O}(1)$$. With this algorithm the user can specify the block size to be used, the general rule of thumb being that larger block size will decrease the pre-processing time but increase the query time.

Parameters
• algorithm – specify the algorithm to be used, can be either sparse_table or sparse_table_block.

• block_size – if algorithm is sparse_table_block, specify the block size to be used (default 1024)

• force_recompute – if False (default) calling this function twice won’t re-preprocess the tree, even if the specified algorithm or algorithm parameter have changed.

Returns

An object of type LCA_rmq_sparse_table_block or LCA_rmq_sparse_table

num_children(vertex=None)

Get the the number of children of the given vertices.

If vertex is None, the function will return the number of children of every non leaf node of the tree.

Parameters

vertex – a vertex index or a 1d array of vertex indices (default to np.arange(self.num_leaves(), self.num_vertices())

Returns

an integer or a 1d array of integers

num_edges(self: higra.higram.Tree) → int

Return the number of edges in the graph

num_leaves(self: higra.higram.Tree) → int

Get the number of leaves nodes.

num_vertices(self: higra.higram.Tree) → int

Return the number of vertices in the graph

out_degree(*args, **kwargs)

Overloaded function.

1. out_degree(self: higra.higram.Tree, vertex: int) -> int

Return the out degree of the given vertex.

1. out_degree(self: higra.higram.Tree, vertices_array: numpy.ndarray[numpy.int32]) -> xt::xtensor

Return the out degree of the given vertices.

1. out_degree(self: higra.higram.Tree, vertices_array: numpy.ndarray[numpy.uint32]) -> xt::xtensor

2. out_degree(self: higra.higram.Tree, vertices_array: numpy.ndarray[numpy.int64]) -> xt::xtensor

3. out_degree(self: higra.higram.Tree, vertices_array: numpy.ndarray[numpy.uint64]) -> xt::xtensor

out_edges(self: higra.higram.Tree, vertex: int) → Iterator

Iterator over all out edges from ‘vertex’. An out edge is a tuple ‘(vertex, adjacent_vertex)’.

parent(*args, **kwargs)

Overloaded function.

1. parent(self: higra.higram.Tree, node: int) -> int

Get the parent of the given node.

1. parent(self: higra.higram.Tree, vertices: numpy.ndarray[numpy.int32]) -> xt::xtensor

Get the parent of each vertex in the given array.

1. parent(self: higra.higram.Tree, vertices: numpy.ndarray[numpy.uint32]) -> xt::xtensor

2. parent(self: higra.higram.Tree, vertices: numpy.ndarray[numpy.int64]) -> xt::xtensor

3. parent(self: higra.higram.Tree, vertices: numpy.ndarray[numpy.uint64]) -> xt::xtensor

parents(self: higra.higram.Tree) → xt::xtensor

Get the parents array representing the tree.

root(self: higra.higram.Tree) → int

Get the index of the root node (i.e. self.num_vertices() - 1)

root_to_leaves_iterator(self: higra.higram.Tree, include_leaves: bool = True, include_root: bool = True) → Iterator

Returns an iterator on the node indices going from the root to the leaves of the tree.

source(self: higra.higram.Tree, edge: tuple) → detail::accessor<detail::accessor_policies::tuple_item>

Get the source vertex of an edge.

sources()

Source vertex of every edge of the graph.

Example

>>> t = Tree((5, 5, 6, 6, 6, 7, 7, 7))
>>> t.sources()
array([0, 1, 2, 3, 4, 5, 6])

Returns

a 1d array of size self.num_edges()

sub_tree(root_node)

Extract the sub tree rooted in the given node of the current tree.

The result is a new tree $$st$$ and a node map $$nm$$ such that:

• the node map associates each node of the sub tree $$st$$ to its corresponding node in the original tree

• the order of the nodes of the original tree is preserved in the sub tree: for any vertices $$x$$ and $$y$$ of $$st$$ such that $$x < y$$ then $$nm[x] < nm[y]$$

Complexity

The tree is constructed in linearithmic time $$\mathcal{O}(n\log(n))$$ with $$n$$ the number of vertices in the sub tree.

Example

>>> t = Tree((5, 5, 6, 6, 6, 7, 7, 7))
>>> sub_tree, node_map = t.sub_tree(6)
>>> sub_tree.parents()
array([3, 3, 3, 3])
>>> node_map
array([2, 3, 4, 6])

Parameters

root_node – a vertex of the current tree

Returns

the sub tree rooted in root and the node map

target(self: higra.higram.Tree, edge: tuple) → detail::accessor<detail::accessor_policies::tuple_item>

Get the target vertex of an edge.

targets()

Target vertex of every edge of the graph.

Example

>>> t = Tree((5, 5, 6, 6, 6, 7, 7, 7))
>>> t.targets()
array([5, 5, 6, 6, 6, 7, 7])

Returns

a 1d array of size self.num_edges()

vertices(self: higra.higram.Tree) → Iterator

Iterator over all vertices of the graph.