Tree¶

class menpo.shape.Tree(adjacency_array, root_vertex, copy=True)[source]¶

Bases: DirectedGraph

Class for Tree definitions and manipulation.

Parameters:

adjacency_array ((n_edges, 2, ) ndarray) –

The Adjacency Array of the tree, i.e. an array containing the sets of the tree’s edges. The numbering of vertices is assumed to start from 0.

We assume that the vertices in the first column of the adjacency_array are the parents and the vertices in the second column of the adjacency_array are the children, for example:

      0            adjacency_array = ndarray([[0, 1],
      |                                       [0, 2],
   ___|___                                    [1, 3],
  1       2                                   [1, 4],
  |       |                                   [2, 5],
 _|_      |                                   [3, 6],
3   4     5                                   [4, 7],
|   |     |                                   [5, 8]])
|   |     |
6   7     8

root_vertex (int) – The vertex that will be considered as root.
copy (bool, optional) – If False, the adjacency_list will not be copied on assignment.

Raises:

ValueError – The provided edges do not represent a tree.
ValueError – The root_vertex must be in the range [0, n_vertices - 1].

children(vertex)¶

Returns the children of the selected vertex.

Parameters:	vertex (int) – The selected vertex.
Returns:	children (list) – The list of children.
Raises:	`ValueError` – The vertex must be between 0 and {n_vertices-1}.

depth_of_vertex(vertex)[source]¶

Returns the depth of the specified vertex.

Parameters:	vertex (int) – The selected vertex.
Returns:	depth (int) – The depth of the selected vertex.
Raises:	`ValueError` – The vertex must be in the range `[0, n_vertices - 1]`.

find_all_paths(start, end, path=[])¶

Returns a list of lists with all the paths (without cycles) found from start vertex to end vertex.

Parameters:	start (int) – The vertex from which the paths start. end (int) – The vertex from which the paths end. path (list, optional) – An existing path to append to.
Returns:	paths (list of list) – The list containing all the paths from start to end.

find_path(start, end, path=None)¶

Returns a list with the first path (without cycles) found from start vertex to end vertex.

Parameters:	start (int) – The vertex from which the path starts. end (int) – The vertex from which the path ends. path (list, optional) – An existing path to append to.
Returns:	path (list) – The path’s vertices.

find_shortest_path(start, end, path=None)¶

Returns a list with the shortest path (without cycles) found from start vertex to end vertex.

Parameters:	start (int) – The vertex from which the path starts. end (int) – The vertex from which the path ends. path (list, optional) – An existing path to append to.
Returns:	path (list) – The shortest path’s vertices.

get_adjacency_matrix()¶

Returns the Adjacency Matrix of the graph, i.e. the boolean ndarray that is True and False if there is an edge connecting the two vertices or not respectively.

Type:	`(n_vertices, n_vertices, )` ndarray

has_cycles()¶

Whether the graph has at least on cycle.

Returns:	has_cycles (bool) – `True` if it has at least one cycle.

is_edge(parent, child)¶

Returns whether there is an edge between the provided vertices.

Parameters:	parent (int) – The first selected vertex which is considered as the parent. child (int) – The second selected vertex which is considered as the child.
Returns:	is_edge (bool) – True if there is an edge.
Raises:	`ValueError` – The vertex must be in the range `[0, n_vertices - 1]`.

is_leaf(vertex)[source]¶

Returns whether the vertex is a leaf.

Parameters:	vertex (int) – The selected vertex.
Returns:	is_leaf (bool) – If True, then selected vertex is a leaf.
Raises:	`ValueError` – The vertex must be in the range `[0, n_vertices - 1]`.

is_tree()¶

Checks if the graph is tree.

Returns:	is_true (bool) – If the graph is a tree.

n_children(vertex)¶

Returns the number of children of the selected vertex.

Parameters:	vertex (int) – The selected vertex.
Returns:	n_children (int) – The number of children.
Raises:	`ValueError` – The vertex must be in the range `[0, n_vertices - 1]`.

n_parent(vertex)¶

Returns the number of parents of the selected vertex.

Parameters:	vertex (int) – The selected vertex.
Returns:	n_parent (int) – The number of parents.
Raises:	`ValueError` – The vertex must be in the range `[0, n_vertices - 1]`.

n_paths(start, end)¶

Returns the number of all the paths (without cycles) existing from start vertex to end vertex.

Parameters:	start (int) – The vertex from which the paths start. end (int) – The vertex from which the paths end.
Returns:	paths (int) – The paths’ numbers.

n_vertices_at_depth(depth)[source]¶

Returns the number of vertices at the specified depth.

Parameters:	depth (int) – The selected depth.
Returns:	n_vertices (int) – The number of vertices that lie in the specified depth.

parent(vertex)[source]¶

Returns the parent of the selected vertex.

Parameters:	vertex (int) – The selected vertex.
Returns:	parent (int) – The parent vertex.
Raises:	`ValueError` – The vertex must be in the range `[0, n_vertices - 1]`.

vertices_at_depth(depth)[source]¶

Returns a list of vertices at the specified depth.

Parameters:	depth (int) – The selected depth.
Returns:	vertices (list) – The vertices that lie in the specified depth.

leaves¶

Returns a list with the all leaves of the tree.

Type:	list

maximum_depth¶

Returns the maximum depth of the tree.

Type:	int

n_edges¶

Returns the number of the graph edges.

Type:	int

n_leaves¶

Returns the number of leaves of the tree.

Type:	int

n_vertices¶

Returns the number of the graph vertices.

Type:	int