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
property value
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

__reduce__()

Helper for pickle.

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

Iterator over all vertices adjacent to the given vertex.

ancestors(self: higra.higram.Tree, node: int) → numpy.ndarray[numpy.int64]

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) → numpy.ndarray[numpy.int64]

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]) -> numpy.ndarray[numpy.uint64]

Return the degree of the given vertices.

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

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

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

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[tuple]

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]) -> numpy.ndarray[numpy.uint64]

Return the in degree of the given vertices.

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

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

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

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

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]) -> numpy.ndarray[bool]

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]) -> numpy.ndarray[bool]

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

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

leaves(self: higra.higram.Tree) → Iterator[int]

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[int]

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]) -> numpy.ndarray[numpy.uint64]

Return the out degree of the given vertices.

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

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

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

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

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]) -> numpy.ndarray[numpy.int64]

Get the parent of each vertex in the given array.

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

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

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

parents(self: higra.higram.Tree) → numpy.ndarray[numpy.int64]

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[int]

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()

to_undirected_graph(include_leaves=True)

Convert the tree to an undirected graph.

If include_leaves is True, the leaves of the tree are also included in the graph and there is a direct mapping between the nodes of the tree and the vertices of the graph and between the edges of the tree and the edges of the graph (node/edge in the tree and its corresponding vertex/edge in the graph have the same index). Otherwise, the leaves of the tree are not included in the graph and the first `tree.num_leaves() edges from the tree are also discarded (those including a leaf). The mapping between the nodes of the tree and the vertices of the graph is then shifted by `tree.num_leaves() (a vertex/edge in the graph of index `i` corresponds to a node/edge in the tree of index `i + tree.num_leaves()`).

Example:

>>> t = Tree((5, 5, 6, 6, 6, 7, 7, 7))
>>> g = t.to_undirected_graph()
>>> type(g)
<class 'higra.higram.UndirectedGraph'>
>>> g.num_vertices()
8
>>> g.num_edges()
7
>>> g.edge_list()
(array([0, 1, 2, 3, 4, 5, 6]), array([5, 5, 6, 6, 6, 7, 7]))

>>> g = t.to_undirected_graph(include_leaves=False)
>>> type(g)
<class 'higra.higram.UndirectedGraph'>
>>> g.num_vertices()
3
>>> g.num_edges()
2
>>> g.edge_list()
(array([0, 2]), array([1, 2]))
Parameters:

include_leaves – if True, the leaves of the tree are also included in the graph

Returns:

an undirected graph whose vertices are the nodes of the tree and whose edges are the parent relation of the tree

vertices(self: higra.higram.Tree) → Iterator[int]

Iterator over all vertices of the graph.