DirectedGraph

class menpo.shape.DirectedGraph(adjacency_array, copy=True)

Bases: Graph

Class for Directed Graph definition and manipulation.

Parameters:

• adjacency_array ((n_edges, 2, ) ndarray) –

  The Adjacency Array of the graph, i.e. an array containing the sets of the graph’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([[1, 0],
  |       |                                   [2, 0],
  |       |                                   [1, 2],
  1<----->2                                   [2, 1],
  |       |                                   [1, 3],
  v       v                                   [2, 4],
  3------>4                                   [3, 4],
  |                                           [3, 5]])
  v
  5
  

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

Raises:

• ValueError – You must provide at least one edge.
• ValueError – Adjacency list must contain the sets of connected edges and thus must have shape (n_edges, 2).
• ValueError – The vertices must be numbered starting from 0.

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}.

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_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.

parent(vertex)

Returns the parents of the selected vertex.

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

n_edges

Returns the number of the graph edges.

Type:int

n_vertices

Returns the number of the graph vertices.

Type:int