Tree

class menpo.shape.Tree(adjacency_matrix, root_vertex, copy=True, skip_checks=False)[source]

Bases: DirectedGraph

Class for Tree definitions and manipulation.

Parameters
  • adjacency_matrix ((n_vertices, n_vertices, ) ndarray or csr_matrix) –

    The adjacency matrix of the tree in which the rows represent parents and columns represent children. The non-edges must be represented with zeros and the edges can have a weight value.

    Note

    A tree must not have isolated vertices.

  • root_vertex (int) – The vertex to be set as root.

  • copy (bool, optional) – If False, the adjacency_matrix will not be copied on assignment.

  • skip_checks (bool, optional) – If True, no checks will be performed.

Raises
  • ValueError – adjacency_matrix must be either a numpy.ndarray or a scipy.sparse.csr_matrix.

  • ValueError – Graph must have at least two vertices.

  • ValueError – adjacency_matrix must be square (n_vertices, n_vertices, ), ({adjacency_matrix.shape[0]}, {adjacency_matrix.shape[1]}) given instead.

  • ValueError – The provided edges do not represent a tree.

  • ValueError – The root_vertex must be in the range [0, n_vertices - 1].

  • ValueError – The combination of adjacency matrix and root vertex is not valid. BFS returns a different tree.

Examples

The following tree

      0
      |
   ___|___
  1       2
  |       |
 _|_      |
3   4     5
|   |     |
|   |     |
6   7     8

can be defined as

import numpy as np
adjacency_matrix = np.array([[0, 1, 1, 0, 0, 0, 0, 0, 0],
                             [0, 0, 0, 1, 1, 0, 0, 0, 0],
                             [0, 0, 0, 0, 0, 1, 0, 0, 0],
                             [0, 0, 0, 0, 0, 0, 1, 0, 0],
                             [0, 0, 0, 0, 0, 0, 0, 1, 0],
                             [0, 0, 0, 0, 0, 0, 0, 0, 1],
                             [0, 0, 0, 0, 0, 0, 0, 0, 0],
                             [0, 0, 0, 0, 0, 0, 0, 0, 0],
                             [0, 0, 0, 0, 0, 0, 0, 0, 0]])
tree = Tree(adjacency_matrix, root_vertex=0)

or

from scipy.sparse import csr_matrix
adjacency_matrix = csr_matrix(([1] * 8, ([0, 0, 1, 1, 2, 3, 4, 5],
                                         [1, 2, 3, 4, 5, 6, 7, 8])),
                              shape=(9, 9))
tree = Tree(adjacency_matrix, root_vertex=0)
children(vertex, skip_checks=False)

Returns the children of the selected vertex.

Parameters
  • vertex (int) – The selected vertex.

  • skip_checks (bool, optional) – If False, the given vertex will be checked.

Returns

children (list) – The list of children.

Raises

ValueError – The vertex must be between 0 and {n_vertices-1}.

depth_of_vertex(vertex, skip_checks=False)[source]

Returns the depth of the specified vertex.

Parameters
  • vertex (int) – The selected vertex.

  • skip_checks (bool, optional) – If False, the given vertex will be checked.

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_all_shortest_paths(algorithm='auto', unweighted=False)

Returns the distances and predecessors arrays of the graph’s shortest paths.

Parameters
  • algorithm ('str', see below, optional) –

    The algorithm to be used. Possible options are:

    ’dijkstra’

    Dijkstra’s algorithm with Fibonacci heaps

    ’bellman-ford’

    Bellman-Ford algorithm

    ’johnson’

    Johnson’s algorithm

    ’floyd-warshall’

    Floyd-Warshall algorithm

    ’auto’

    Select the best among the above

  • unweighted (bool, optional) – If True, then find unweighted distances. That is, rather than finding the path between each vertex such that the sum of weights is minimized, find the path such that the number of edges is minimized.

Returns

  • distances ((n_vertices, n_vertices,) ndarray) – The matrix of distances between all graph vertices. distances[i,j] gives the shortest distance from vertex i to vertex j along the graph.

  • predecessors ((n_vertices, n_vertices,) ndarray) – The matrix of predecessors, which can be used to reconstruct the shortest paths. Each entry predecessors[i, j] gives the index of the previous vertex in the path from vertex i to vertex j. If no path exists between vertices i and j, then predecessors[i, j] = -9999.

find_path(start, end, method='bfs', skip_checks=False)

Returns a list with the first path (without cycles) found from the start vertex to the end vertex. It can employ either depth-first search or breadth-first search.

Parameters
  • start (int) – The vertex from which the path starts.

  • end (int) – The vertex to which the path ends.

  • method ({bfs, dfs}, optional) – The method to be used.

  • skip_checks (bool, optional) – If True, then input arguments won’t pass through checks. Useful for efficiency.

Returns

path (list) – The path’s vertices.

Raises

ValueError – Method must be either bfs or dfs.

find_shortest_path(start, end, algorithm='auto', unweighted=False, skip_checks=False)

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 to which the path ends.

  • algorithm ('str', see below, optional) –

    The algorithm to be used. Possible options are:

    ’dijkstra’

    Dijkstra’s algorithm with Fibonacci heaps

    ’bellman-ford’

    Bellman-Ford algorithm

    ’johnson’

    Johnson’s algorithm

    ’floyd-warshall’

    Floyd-Warshall algorithm

    ’auto’

    Select the best among the above

  • unweighted (bool, optional) – If True, then find unweighted distances. That is, rather than finding the path such that the sum of weights is minimized, find the path such that the number of edges is minimized.

  • skip_checks (bool, optional) – If True, then input arguments won’t pass through checks. Useful for efficiency.

Returns

  • path (list) – The shortest path’s vertices, including start and end. If there was not path connecting the vertices, then an empty list is returned.

  • distance (int or float) – The distance (cost) of the path from start to end.

get_adjacency_list()

Returns the adjacency list of the graph, i.e. a list of length n_vertices that for each vertex has a list of the vertex neighbours. If the graph is directed, the neighbours are children.

Returns

adjacency_list (list of list of length n_vertices) – The adjacency list of the graph.

has_cycles()

Checks if the graph has at least one cycle.

Returns

has_cycles (bool) – True if the graph has cycles.

has_isolated_vertices()

Whether the graph has any isolated vertices, i.e. vertices with no edge connections.

Returns

has_isolated_vertices (bool) – True if the graph has at least one isolated vertex.

classmethod init_from_edges(edges, n_vertices, root_vertex, copy=True, skip_checks=False)[source]

Construct a Tree from edges array.

Parameters
  • edges ((n_edges, 2, ) ndarray) – The ndarray of edges, i.e. all the pairs of vertices that are connected with an edge.

  • n_vertices (int) – The total number of vertices, assuming that the numbering of vertices starts from 0. edges and n_vertices can be defined in a way to set isolated vertices.

  • root_vertex (int) – That vertex that will be set as root.

  • copy (bool, optional) – If False, the adjacency_matrix will not be copied on assignment.

  • skip_checks (bool, optional) – If True, no checks will be performed.

Examples

The following tree

      0
      |
   ___|___
  1       2
  |       |
 _|_      |
3   4     5
|   |     |
|   |     |
6   7     8

can be defined as

from menpo.shape import PointTree
import numpy as np
points = np.array([[30, 30], [10, 20], [50, 20], [0, 10], [20, 10],
                   [50, 10], [0, 0], [20, 0], [50, 0]])
edges = np.array([[0, 1], [0, 2], [1, 3], [1, 4], [2, 5], [3, 6],
                  [4, 7], [5, 8]])
tree = PointTree.init_from_edges(points, edges, root_vertex=0)
is_edge(vertex_1, vertex_2, skip_checks=False)

Whether there is an edge between the provided vertices.

Parameters
  • vertex_1 (int) – The first selected vertex. Parent if the graph is directed.

  • vertex_2 (int) – The second selected vertex. Child if the graph is directed.

  • skip_checks (bool, optional) – If False, the given vertices will be checked.

Returns

is_edge (bool) – True if there is an edge connecting vertex_1 and vertex_2.

Raises

ValueError – The vertex must be between 0 and {n_vertices-1}.

is_leaf(vertex, skip_checks=False)[source]

Whether the vertex is a leaf.

Parameters
  • vertex (int) – The selected vertex.

  • skip_checks (bool, optional) – If False, the given vertex will be checked.

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.

isolated_vertices()

Returns the isolated vertices of the graph (if any), i.e. the vertices that have no edge connections.

Returns

isolated_vertices (list) – A list of the isolated vertices. If there aren’t any, it returns an empty list.

n_children(vertex, skip_checks=False)

Returns the number of children of the selected vertex.

Parameters

vertex (int) – The selected vertex.

Returns

  • n_children (int) – The number of children.

  • skip_checks (bool, optional) – If False, the given vertex will be checked.

Raises

ValueError – The vertex must be in the range [0, n_vertices - 1].

n_parents(vertex, skip_checks=False)

Returns the number of parents of the selected vertex.

Parameters
  • vertex (int) – The selected vertex.

  • skip_checks (bool, optional) – If False, the given vertex will be checked.

Returns

n_parents (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, skip_checks=False)[source]

Returns the parent of the selected vertex.

Parameters
  • vertex (int) – The selected vertex.

  • skip_checks (bool, optional) – If False, the given vertex will be checked.

Returns

parent (int) – The parent vertex.

Raises

ValueError – The vertex must be in the range [0, n_vertices - 1].

parents(vertex, skip_checks=False)

Returns the parents of the selected vertex.

Parameters
  • vertex (int) – The selected vertex.

  • skip_checks (bool, optional) – If False, the given vertex will be checked.

Returns

parents (list) – The list of parents.

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.

property edges

Returns the ndarray of edges, i.e. all the pairs of vertices that are connected with an edge.

Type

(n_edges, 2, ) ndarray

property leaves

Returns a list with the all leaves of the tree.

Type

list

property maximum_depth

Returns the maximum depth of the tree.

Type

int

property n_edges

Returns the number of edges.

Type

int

property n_leaves

Returns the number of leaves of the tree.

Type

int

property n_vertices

Returns the number of vertices.

Type

int

property vertices

Returns the list of vertices.

Type

list