UndirectedGraph

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

Bases: Graph

Class for Undirected 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. For example:

  |---0---|        adjacency_array = ndarray([[0, 1],
  |       |                                   [0, 2],
  |       |                                   [1, 2],
  1-------2                                   [1, 3],
  |       |                                   [2, 4],
  |       |                                   [3, 4],
  3-------4                                   [3, 5]])
  |
  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.

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(vertex_1, vertex_2)

Returns whether there is an edge between the provided vertices.

Parameters:

• vertex_1 (int) – The first selected vertex.
• vertex_2 (int) – The second selected vertex.

Returns:

is_edge (bool) – True if there is an edge.

Raises:

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

is_tree()

Checks if the graph is tree.

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

minimum_spanning_tree(weights, root_vertex)

Returns the minimum spanning tree given weights to the graph’s edges using Kruskal’s algorithm.

Parameters:

• weights ((n_vertices, n_vertices, ) ndarray) – A matrix of the same size as the adjacency matrix that attaches a weight to each edge of the undirected graph.
• root_vertex (int) – The vertex that will be set as root in the output MST.

Returns:

mst (Tree) – The computed minimum spanning tree.

Raises:

• ValueError – Provided graph is not an UndirectedGraph.
• ValueError – Asymmetric weights provided.

n_neighbours(vertex)

Returns the number of neighbours of the selected vertex.

Parameters:vertex (int) – The selected vertex. Returns:n_neighbours (int) – The number of neighbours. Raises:ValueError – The vertex must be between 0 and {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.

neighbours(vertex)

Returns the neighbours of the selected vertex.

Parameters:vertex (int) – The selected vertex. Returns:neighbours (list) – The list of neighbours. Raises:ValueError – The vertex must be between 0 and {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