UndirectedGraph¶
-
class
menpo.shape.
UndirectedGraph
(adjacency_matrix, copy=True, skip_checks=False)[source]¶ Bases:
Graph
Class for Undirected Graph definition and manipulation.
- Parameters
adjacency_matrix (
(n_vertices, n_vertices, )
ndarray or csr_matrix) –The adjacency matrix of the graph. The non-edges must be represented with zeros and the edges can have a weight value.
- Note
adjacency_matrix
must be symmetric.
copy (bool, optional) – If
False
, theadjacency_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 adjacency matrix of an undirected graph must be symmetric.
Examples
The following undirected graph
|---0---| | | | | 1-------2 | | | | 3-------4 | | 5
can be defined as
import numpy as np adjacency_matrix = np.array([[0, 1, 1, 0, 0, 0], [1, 0, 1, 1, 0, 0], [1, 1, 0, 0, 1, 0], [0, 1, 0, 0, 1, 1], [0, 0, 1, 1, 0, 0], [0, 0, 0, 1, 0, 0]]) graph = UndirectedGraph(adjacency_matrix)
or
from scipy.sparse import csr_matrix adjacency_matrix = csr_matrix( ([1] * 14, ([0, 1, 0, 2, 1, 2, 1, 3, 2, 4, 3, 4, 3, 5], [1, 0, 2, 0, 2, 1, 3, 1, 4, 2, 4, 3, 5, 3])), shape=(6, 6)) graph = UndirectedGraph(adjacency_matrix)
The adjacency matrix of the following graph with isolated vertices
0---| | | 1 2 | | 3-------4 5
can be defined as
import numpy as np adjacency_matrix = np.array([[0, 0, 1, 0, 0, 0], [0, 0, 0, 0, 0, 0], [1, 0, 0, 0, 1, 0], [0, 0, 0, 0, 1, 0], [0, 0, 1, 1, 0, 0], [0, 0, 0, 0, 0, 0]]) graph = UndirectedGraph(adjacency_matrix)
or
from scipy.sparse import csr_matrix adjacency_matrix = csr_matrix(([1] * 6, ([0, 2, 2, 4, 3, 4], [2, 0, 4, 2, 4, 3])), shape=(6, 6)) graph = UndirectedGraph(adjacency_matrix)
-
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 vertexi
to vertexj
along the graph.predecessors (
(n_vertices, n_vertices,)
ndarray) – The matrix of predecessors, which can be used to reconstruct the shortest paths. Each entrypredecessors[i, j]
gives the index of the previous vertex in the path from vertexi
to vertexj
. If no path exists between verticesi
andj
, thenpredecessors[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 theend
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 toend
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
andend
. 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
toend
.
-
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, skip_checks=False)[source]¶ Initialize graph 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
andn_vertices
can be defined in a way to set isolated vertices.skip_checks (bool, optional) – If
True
, no checks will be performed.
Examples
The following undirected graph
|---0---| | | | | 1-------2 | | | | 3-------4 | | 5
can be defined as
from menpo.shape import UndirectedGraph import numpy as np edges = np.array([[0, 1], [1, 0], [0, 2], [2, 0], [1, 2], [2, 1], [1, 3], [3, 1], [2, 4], [4, 2], [3, 4], [4, 3], [3, 5], [5, 3]]) graph = UndirectedGraph.init_from_edges(edges, n_vertices=6)
Finally, the following graph with isolated vertices
0---| | | 1 2 | | 3-------4 5
can be defined as
from menpo.shape import UndirectedGraph import numpy as np edges = np.array([[0, 2], [2, 0], [2, 4], [4, 2], [3, 4], [4, 3]]) graph = UndirectedGraph.init_from_edges(edges, n_vertices=6)
-
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 connectingvertex_1
andvertex_2
.- 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.
-
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.
-
minimum_spanning_tree
(root_vertex)[source]¶ Returns the minimum spanning tree of the graph using Kruskal’s algorithm.
- Parameters
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 – Cannot compute minimum spanning tree of a graph with isolated vertices
-
n_neighbours
(vertex, skip_checks=False)[source]¶ Returns the number of neighbours of the selected vertex.
- Parameters
vertex (int) – The selected vertex.
skip_checks (bool, optional) – If
False
, the given vertex will be checked.
- 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, skip_checks=False)[source]¶ Returns the neighbours of the selected vertex.
- Parameters
vertex (int) – The selected vertex.
skip_checks (bool, optional) – If
False
, the given vertex will be checked.
- Returns
neighbours (list) – The list of neighbours.
- Raises
ValueError – The vertex must be between 0 and {n_vertices-1}.
-
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
n_edges
¶ Returns the number of edges.
- Type
int
-
property
n_vertices
¶ Returns the number of vertices.
- Type
int
-
property
vertices
¶ Returns the list of vertices.
- Type
list