# Source code for menpo.shape.graph

import numpy as np
from scipy.sparse import csgraph, csr_matrix, triu

from . import PointCloud

class Graph(object):
r"""
Abstract class for Graph definitions and manipulation.

Parameters
----------
adjacency_matrix : (n_vertices, n_vertices) ndarray or csr_matrix
The adjacency matrix of the graph in which the rows represent source
vertices and columns represent destination vertices. The non-edges must
be represented with zeros and the edges can have a weight value.

The adjacency matrix of an undirected graph must be symmetric.
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 one vertex.
ValueError
adjacency_matrix must be square (n_vertices, n_vertices, ),
ValueError
The adjacency matrix of an undirected graph must be symmetric.

Examples
--------
The adjacency matrix of 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]])

or ::

from scipy.sparse import 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))

The adjacency matrix of the following directed graph ::

|-->0<--|
|       |
|       |
1<----->2
|       |
v       v
3------>4
|
v
5

can be represented as ::

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

or ::

from scipy.sparse import csr_matrix
adjacency_matrix = csr_matrix(([1] * 8, ([1, 2, 1, 2, 1, 2, 3, 3],
[0, 0, 2, 1, 3, 4, 4, 5])),
shape=(6, 6))

Finally, 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]])

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))
"""

# check if adjacency_matrix is numpy.ndarray or scipy.sparse.csr_matrix
# it is numpy.ndarray, thus convert it to scipy.sparse.csr_matrix
elif not (
):
raise ValueError(
"adjacency_matrix must be either a numpy.ndarray"
"or a scipy.sparse.csr_matrix."
)

if not skip_checks:
# check that adjacency_matrix has expected shape
raise ValueError("Graph must have at least one vertex.")
raise ValueError(
"(n_vertices, n_vertices, ), ({}, {}) given "
)
)

# check if adjacency matrix of undirected graph is symmetric
if not self._directed and not _is_symmetric(adjacency_matrix):
raise ValueError(
"The adjacency matrix of an undirected graph " "must be symmetric."
)

if copy:
else:

@classmethod
def init_from_edges(cls, edges, n_vertices, skip_checks=False):
r"""
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 and n_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)

The following directed graph ::

|-->0<--|
|       |
|       |
1<----->2
|       |
v       v
3------>4
|
v
5

can be represented as ::

from menpo.shape import DirectedGraph
import numpy as np
edges = np.array([[1, 0], [2, 0], [1, 2], [2, 1], [1, 3], [2, 4],
[3, 4], [3, 5]])
graph = DirectedGraph.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)

"""

@property
def vertices(self):
r"""
Returns the list of vertices.

:type: list
"""

@property
def n_vertices(self):
r"""
Returns the number of vertices.

:type: int
"""

@property
def edges(self):
r"""
Returns the ndarray of edges, i.e. all the pairs of vertices that are
connected with an edge.

:type: (n_edges, 2, ) ndarray
"""
pass

@property
def n_edges(self):
r"""
Returns the number of edges.

:type: int
"""
return self.edges.shape[0]

def isolated_vertices(self):
r"""
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.
"""

def has_isolated_vertices(self):
r"""
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.
"""
return len(self.isolated_vertices()) > 0

r"""
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.
"""
# initialize list with empty lists
adjacency_list = [[] for _ in range(self.n_vertices)]

# get rows/columns of edges

# store them accordingly
for i in range(rows.shape[0]):
from_v = rows[i]
to_v = cols[i]

def is_edge(self, vertex_1, vertex_2, skip_checks=False):
r"""
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}.
"""
if not skip_checks:
self._check_vertex(vertex_1)
self._check_vertex(vertex_2)

def find_path(self, start, end, method="bfs", skip_checks=False):
r"""
Returns a list with the first path (without cycles) found from the
start vertex to the end vertex. It can employ either depth-first

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.
"""
# checks
if not skip_checks:
self._check_vertex(start)
self._check_vertex(end)

# search
if method == "bfs":
start,
directed=self._directed,
return_predecessors=True,
)
elif method == "dfs":
nodes, predecessors = csgraph.depth_first_order(
start,
directed=self._directed,
return_predecessors=True,
)
else:
raise ValueError("Method must be either bfs or dfs.")

# get path
if predecessors[end] == -9999:
path = []
else:
path = [end]
i = None
while i != start:
i = predecessors[path[-1]]
path.append(i)
path.reverse()
return path

def find_all_paths(self, start, end, path=[]):
r"""
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.
"""
if path is None:
path = []
path = path + [start]
if start == end:
return [path]
if start > self.n_vertices - 1 or start < 0:
return []
paths = []
if v not in path:
newpaths = self.find_all_paths(v, end, path)
for newpath in newpaths:
paths.append(newpath)
return paths

def n_paths(self, start, end):
r"""
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.
"""
return len(self.find_all_paths(start, end))

def find_all_shortest_paths(self, algorithm="auto", unweighted=False):
r"""
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 costs and predecessors of all shortest paths
return csgraph.shortest_path(
directed=self._directed,
method=algorithm,
unweighted=unweighted,
return_predecessors=True,
)

def find_shortest_path(
self, start, end, algorithm="auto", unweighted=False, skip_checks=False
):
r"""
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.
"""
# checks
if not skip_checks:
self._check_vertex(start)
self._check_vertex(end)

# find distances and predecessors of all shortest paths
(distances, predecessors) = self.find_all_shortest_paths(
algorithm=algorithm, unweighted=unweighted
)

# retrieve shortest path and its distance
if predecessors[start, end] < 0:
path = []
distance = np.inf
else:
path = [end]
distance = 0
i = None
while i != start:
i = predecessors[start, path[-1]]
path.append(i)
distance += distances[start, path[-1]]
path.reverse()
return path, distance

def has_cycles(self):
r"""
Checks if the graph has at least one cycle.

Returns
-------
has_cycles : bool
True if the graph has cycles.
"""

def is_tree(self):
r"""
Checks if the graph is tree.

Returns
-------
is_true : bool
If the graph is a tree.
"""
return not self.has_cycles() and self.n_edges == self.n_vertices - 1

def _check_vertex(self, vertex):
r"""
Checks that a given vertex is valid.

Parameters
----------
vertex : int
Index of a given vertex.

Raises
------
ValueError
The vertex must be between 0 and {n_vertices-1}.
"""
if vertex > self.n_vertices - 1 or vertex < 0:
raise ValueError(
"The vertex must be between " "0 and {}.".format(self.n_vertices - 1)
)

[docs]class UndirectedGraph(Graph):
r"""
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, 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, ),
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]])

or ::

from scipy.sparse import 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))

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]])

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))
"""

self._directed = False
super(UndirectedGraph, self).__init__(
)

[docs]    @classmethod
def init_from_edges(cls, edges, n_vertices, skip_checks=False):
r"""
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 and n_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)

"""
edges, n_vertices
)

@property
def edges(self):

[docs]    def neighbours(self, vertex, skip_checks=False):
r"""
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}.
"""
# check given vertex
if not skip_checks:
self._check_vertex(vertex)

[docs]    def n_neighbours(self, vertex, skip_checks=False):
r"""
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}.
"""
return len(self.neighbours(vertex, skip_checks=skip_checks))

[docs]    def minimum_spanning_tree(self, root_vertex):
r"""
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 : :map:Tree
The computed minimum spanning tree.

Raises
------
ValueError
Cannot compute minimum spanning tree of a graph with isolated
vertices
"""
# check if graph has isolated vertices
if self.has_isolated_vertices():
raise ValueError(
"Cannot compute minimum spanning tree of a graph "
"with isolated vertices."
)
# Compute MST. It returns an undirected graph.
# Get directed tree from the above undirected graph using DFS.
)

def __str__(self):
isolated = ""
if self.has_isolated_vertices():
isolated = " ({} isolated)".format(len(self.isolated_vertices()))
return "Undirected graph of {} vertices{} and {} " "edges.".format(
self.n_vertices, isolated, self.n_edges
)

[docs]class DirectedGraph(Graph):
r"""
Class for Directed Graph definition and manipulation.

Parameters
----------
adjacency_matrix : (n_vertices, n_vertices, ) ndarray or csr_matrix
The adjacency matrix of the graph in which the rows represent source
vertices and columns represent destination vertices. The non-edges must
be represented with zeros and the edges can have a weight value.
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, ),

Examples
--------
The following directed graph ::

|-->0<--|
|       |
|       |
1<----->2
|       |
v       v
3------>4
|
v
5

can be defined as ::

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

or ::

from scipy.sparse import csr_matrix
adjacency_matrix = csr_matrix(([1] * 8, ([1, 2, 1, 2, 1, 2, 3, 3],
[0, 0, 2, 1, 3, 4, 4, 5])),
shape=(6, 6))

The following graph with isolated vertices ::

0<--|
|
|
1       2
|
v
3------>4

5

can be defined as ::

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

or ::

from scipy.sparse import csr_matrix
adjacency_matrix = csr_matrix(([1] * 3, ([2, 2, 3], [0, 4, 4])),
shape=(6, 6))
"""

self._directed = True
super(DirectedGraph, self).__init__(
)

@property
def edges(self):

[docs]    def children(self, vertex, skip_checks=False):
r"""
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}.
"""
if not skip_checks:
self._check_vertex(vertex)

[docs]    def n_children(self, vertex, skip_checks=False):
r"""
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].
"""
return len(self.children(vertex, skip_checks=skip_checks))

[docs]    def parents(self, vertex, skip_checks=False):
r"""
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].
"""
if not skip_checks:
self._check_vertex(vertex)

[docs]    def n_parents(self, vertex, skip_checks=False):
r"""
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].
"""
return len(self.parents(vertex, skip_checks=skip_checks))

def __str__(self):
isolated = ""
if self.has_isolated_vertices():
isolated = " ({} isolated)".format(len(self.isolated_vertices()))
return "Directed graph of {} vertices{} and {} " "edges.".format(
self.n_vertices, isolated, self.n_edges
)

[docs]class Tree(DirectedGraph):
r"""
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, ),
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]])

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))
"""

def __init__(self, adjacency_matrix, root_vertex, copy=True, skip_checks=False):

if not skip_checks:
# check if the provided tree has isolated vertices
if self.has_isolated_vertices():
raise ValueError("A tree cannot have isolated vertices.")
# check if provided adjacency_matrix represents a tree
if not self.is_tree():
raise ValueError("The provided edges do not represent a tree.")
# check if root_vertex is valid
self._check_vertex(root_vertex)
# check if the tree is properly defined given the root
if not np.allclose(
).nonzero(),
):
raise ValueError(
"The combination of adjacency matrix and root "
"vertex is not valid. BFS returns a different "
"tree."
)

# store root and predecessors list
self.root_vertex = root_vertex
self.predecessors_list = self._get_predecessors_list()

[docs]    @classmethod
def init_from_edges(
cls, edges, n_vertices, root_vertex, copy=True, skip_checks=False
):
r"""
Construct a :map: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)
"""
return cls(
root_vertex=root_vertex,
copy=copy,
skip_checks=skip_checks,
)

def _get_predecessors_list(self):
r"""
Returns the predecessors list of the tree, i.e. a list of length
n_vertices that stores the parent for each vertex. The value of the
root vertex is None.

:type: list of length n_vertices
"""
# initialize list with None
predecessors_list = [None] * self.n_vertices

# get rows/columns of edges

# store them accordingly
for i in range(children.shape[0]):
parent = parents[i]
child = children[i]
predecessors_list[child] = parent
return predecessors_list

[docs]    def depth_of_vertex(self, vertex, skip_checks=False):
r"""
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].
"""
if not skip_checks:
self._check_vertex(vertex)
parent = vertex
depth = 0
while not parent == self.root_vertex:
current = parent
parent = self.predecessors_list[current]
depth += 1
return depth

@property
def maximum_depth(self):
r"""
Returns the maximum depth of the tree.

:type: int
"""
all_depths = [self.depth_of_vertex(v) for v in range(self.n_vertices)]
return np.max(all_depths)

[docs]    def vertices_at_depth(self, depth):
r"""
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.
"""
ver = []
for v in range(self.n_vertices):
if self.depth_of_vertex(v) == depth:
ver.append(v)
return ver

[docs]    def n_vertices_at_depth(self, depth):
r"""
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.
"""
n_ver = 0
for v in range(self.n_vertices):
if self.depth_of_vertex(v) == depth:
n_ver += 1
return n_ver

[docs]    def is_leaf(self, vertex, skip_checks=False):
r"""
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].
"""
if not skip_checks:
self._check_vertex(vertex)
return len(self.children(vertex)) == 0

@property
def leaves(self):
r"""
Returns a list with the all leaves of the tree.

:type: list
"""
leaves = []
for v in range(self.n_vertices):
if self.is_leaf(v):
leaves.append(v)
return leaves

@property
def n_leaves(self):
r"""
Returns the number of leaves of the tree.

:type: int
"""
return len(self.leaves)

[docs]    def parent(self, vertex, skip_checks=False):
r"""
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].
"""
if not skip_checks:
self._check_vertex(vertex)
return self.predecessors_list[vertex]

def __str__(self):
return "Tree of depth {} with {} vertices and {} leaves.".format(
self.maximum_depth, self.n_vertices, self.n_leaves
)

class PointGraph(Graph, PointCloud):
r"""
Class for defining a Graph with geometry.

Parameters
----------
points : (n_vertices, n_dims, ) ndarray
The array of point locations.
adjacency_matrix : (n_vertices, n_vertices) ndarray or csr_matrix
The adjacency matrix of the graph in which the rows represent source
vertices and columns represent destination vertices. The non-edges must
be represented with zeros and the edges can have a weight value.

The adjacency matrix of an undirected graph must be symmetric.
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, ),
ValueError
The adjacency matrix of an undirected graph must be symmetric.
ValueError
A point for each graph vertex needs to be passed. Got {} points instead
of {}

Examples
--------
The adjacency matrix of 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]])

or ::

from scipy.sparse import 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))

The adjacency matrix of the following directed graph ::

|-->0<--|
|       |
|       |
1<----->2
|       |
v       v
3------>4
|
v
5

can be represented as ::

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

or ::

from scipy.sparse import csr_matrix
adjacency_matrix = csr_matrix(([1] * 8, ([1, 2, 1, 2, 1, 2, 3, 3],
[0, 0, 2, 1, 3, 4, 4, 5])),
shape=(6, 6))

Finally, 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]])

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))
"""

def __init__(self, points, adjacency_matrix, copy=True, skip_checks=False):
if not skip_checks:
# check the number of points
PointCloud.__init__(self, points, copy=copy)

@classmethod
def init_from_edges(cls, points, edges, copy=True, skip_checks=False):
r"""
Construct a PointGraph from edges array.

Parameters
----------
points : (n_vertices, n_dims, ) ndarray
The array of point locations.
edges : (n_edges, 2, ) ndarray
The ndarray of edges, i.e. all the pairs of vertices that are
connected with an edge.
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 undirected graph ::

|---0---|
|       |
|       |
1-------2
|       |
|       |
3-------4
|
|
5

can be defined as ::

from menpo.shape import PointUndirectedGraph
import numpy as np
points = np.array([[10, 30], [0, 20], [20, 20], [0, 10], [20, 10],
[0, 0]])
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 = PointUndirectedGraph.init_from_edges(points, edges)

The following directed graph ::

|-->0<--|
|       |
|       |
1<----->2
|       |
v       v
3------>4
|
v
5

can be represented as ::

from menpo.shape import PointDirectedGraph
import numpy as np
points = np.array([[10, 30], [0, 20], [20, 20], [0, 10], [20, 10],
[0, 0]])
edges = np.array([[1, 0], [2, 0], [1, 2], [2, 1], [1, 3], [2, 4],
[3, 4], [3, 5]])
graph = PointDirectedGraph.init_from_edges(points, edges)

Finally, the following graph with isolated vertices ::

0---|
|
|
1       2
|
|
3-------4

5

can be defined as ::

from menpo.shape import PointUndirectedGraph
import numpy as np
points = np.array([[10, 30], [0, 20], [20, 20], [0, 10], [20, 10],
[0, 0]])
edges = np.array([[0, 2], [2, 0], [2, 4], [4, 2], [3, 4], [4, 3]])
graph = PointUndirectedGraph.init_from_edges(points, edges)

"""

@classmethod
def init_2d_grid(
):
r"""
Create a PointGraph that exists on a regular 2D grid. The first
dimension is the number of rows in the grid and the second dimension
of the shape is the number of columns. spacing optionally allows
the definition of the distance between points (uniform over points).
The spacing may be different for rows and columns.

If no adjacency matrix is provided, the default connectivity will
be a 4-connected lattice.

Parameters
----------
shape : tuple of 2 int
The size of the grid to create, this defines the number of points
across each dimension in the grid. The first element is the number
of rows and the second is the number of columns.
spacing : int or tuple of 2 int, optional
The spacing between points. If a single int is provided, this
is applied uniformly across each dimension. If a tuple is
provided, the spacing is applied non-uniformly as defined e.g.
(2, 3) gives a spacing of 2 for the rows and 3 for the
columns.
adjacency_matrix : (n_vertices, n_vertices) ndarray or csr_matrix, optional
The adjacency matrix of the graph in which the rows represent source
vertices and columns represent destination vertices. The non-edges must
be represented with zeros and the edges can have a weight value.

The adjacency matrix of an undirected graph must be symmetric.
skip_checks : bool, optional
If True, no checks will be performed. Only considered if no

Returns
-------
pgraph : PointGraph
A pointgraph arranged in a grid.
"""
from .graph_predefined import stencil_grid

pc = PointCloud.init_2d_grid(shape, spacing=spacing)
points = pc.points
stencil = np.array([[0, 1, 0], [1, 0, 1], [0, 1, 0]])
# Skip checks if we construct the adjacency.
skip_checks = True
else:

@classmethod
def init_from_depth_image(
):
r"""
Return a 3D point graph from the given depth image. The depth image
is assumed to represent height/depth values and the XY coordinates
are assumed to unit spaced and represent image coordinates. This is
particularly useful for visualising depth values that have been
recovered from images.

If no adjacency matrix is provided, the default connectivity will
be a 4-connected lattice.

Parameters
----------
depth_image : :map:Image or subclass
A single channel image that contains depth values - as commonly
returned by RGBD cameras, for example.
spacing : int or tuple of 2 int, optional
The spacing between points. If a single int is provided, this
is applied uniformly across each dimension. If a tuple is
provided, the spacing is applied non-uniformly as defined e.g.
(2, 3) gives a spacing of 2 for the rows and 3 for the
columns.
adjacency_matrix : (n_vertices, n_vertices) ndarray or csr_matrix, optional
The adjacency matrix of the graph in which the rows represent source
vertices and columns represent destination vertices. The non-edges must
be represented with zeros and the edges can have a weight value.

The adjacency matrix of an undirected graph must be symmetric.
skip_checks : bool, optional
If True, no checks will be performed. Only considered if no

Returns
-------
depth_cloud : type(cls)
A new 3D PointGraph with unit XY coordinates and the given depth
values as Z coordinates.
"""

new_pcloud = cls.init_2d_grid(
depth_image.shape,
spacing=spacing,
skip_checks=skip_checks,
)
return cls(
np.hstack([new_pcloud.points, depth_image.as_vector(keep_channels=True).T]),
copy=False,
skip_checks=True,
)

def tojson(self):
r"""
Convert this PointGraph to a dictionary representation suitable for
inclusion in the LJSON landmark format.

Returns
-------
json : dict
Dictionary with points and connectivity keys.
"""
json_dict = PointCloud.tojson(self)
json_dict["landmarks"]["connectivity"] = self.edges.tolist()
return json_dict

def _view_2d(
self,
figure_id=None,
new_figure=False,
image_view=True,
render_lines=True,
line_colour="r",
line_style="-",
line_width=1.0,
render_markers=True,
marker_style="o",
marker_size=5,
marker_face_colour="k",
marker_edge_colour="k",
marker_edge_width=1.0,
render_numbering=False,
numbers_horizontal_align="center",
numbers_vertical_align="bottom",
numbers_font_name="sans-serif",
numbers_font_size=10,
numbers_font_style="normal",
numbers_font_weight="normal",
numbers_font_colour="k",
render_axes=True,
axes_font_name="sans-serif",
axes_font_size=10,
axes_font_style="normal",
axes_font_weight="normal",
axes_x_limits=None,
axes_y_limits=None,
axes_x_ticks=None,
axes_y_ticks=None,
figure_size=(7, 7),
label=None,
**kwargs,
):
r"""
Visualization of the PointGraph in 2D.

Returns
-------
figure_id : object, optional
The id of the figure to be used.
new_figure : bool, optional
If True, a new figure is created.
image_view : bool, optional
If True the PointGraph will be viewed as if it is in the image
coordinate system.
render_lines : bool, optional
If True, the edges will be rendered.
line_colour : See Below, optional
The colour of the lines.
Example options::

{r, g, b, c, m, k, w}
or
(3, ) ndarray

line_style : {'-', '--', '-.', ':'}, optional
The style of the lines.
line_width : float, optional
The width of the lines.
render_markers : bool, optional
If True, the markers will be rendered.
marker_style : See Below, optional
The style of the markers. Example options ::

{., ,, o, v, ^, <, >, +, x, D, d, s, p, *, h, H, 1, 2, 3, 4, 8}

marker_size : int, optional
The size of the markers in points.
marker_face_colour : See Below, optional
The face (filling) colour of the markers.
Example options ::

{r, g, b, c, m, k, w}
or
(3, ) ndarray

marker_edge_colour : See Below, optional
The edge colour of the markers.
Example options ::

{r, g, b, c, m, k, w}
or
(3, ) ndarray

marker_edge_width : float, optional
The width of the markers' edge.
render_numbering : bool, optional
If True, the landmarks will be numbered.
numbers_horizontal_align : {center, right, left}, optional
The horizontal alignment of the numbers' texts.
numbers_vertical_align : {center, top, bottom, baseline}, optional
The vertical alignment of the numbers' texts.
numbers_font_name : See Below, optional
The font of the numbers. Example options ::

{serif, sans-serif, cursive, fantasy, monospace}

numbers_font_size : int, optional
The font size of the numbers.
numbers_font_style : {normal, italic, oblique}, optional
The font style of the numbers.
numbers_font_weight : See Below, optional
The font weight of the numbers.
Example options ::

{ultralight, light, normal, regular, book, medium, roman,
semibold, demibold, demi, bold, heavy, extra bold, black}

numbers_font_colour : See Below, optional
The font colour of the numbers.
Example options ::

{r, g, b, c, m, k, w}
or
(3, ) ndarray

render_axes : bool, optional
If True, the axes will be rendered.
axes_font_name : See Below, optional
The font of the axes.
Example options ::

{serif, sans-serif, cursive, fantasy, monospace}

axes_font_size : int, optional
The font size of the axes.
axes_font_style : {normal, italic, oblique}, optional
The font style of the axes.
axes_font_weight : See Below, optional
The font weight of the axes.
Example options ::

{ultralight, light, normal, regular, book, medium, roman,
semibold, demibold, demi, bold, heavy, extra bold, black}

axes_x_limits : float or (float, float) or None, optional
The limits of the x axis. If float, then it sets padding on the
right and left of the PointGraph as a percentage of the PointGraph's
width. If tuple or list, then it defines the axis limits. If
None, then the limits are set automatically.
axes_y_limits : (float, float) tuple or None, optional
The limits of the y axis. If float, then it sets padding on the
top and bottom of the PointGraph as a percentage of the PointGraph's
height. If tuple or list, then it defines the axis limits. If
None, then the limits are set automatically.
axes_x_ticks : list or tuple or None, optional
The ticks of the x axis.
axes_y_ticks : list or tuple or None, optional
The ticks of the y axis.
figure_size : (float, float) tuple or None, optional
The size of the figure in inches.
label : str, optional
The name entry in case of a legend.

Returns
-------
viewer : :map:PointGraphViewer2d
The viewer object.
"""
from menpo.visualize import PointGraphViewer2d

renderer = PointGraphViewer2d(figure_id, new_figure, self.points, self.edges)
renderer.render(
image_view=image_view,
render_lines=render_lines,
line_colour=line_colour,
line_style=line_style,
line_width=line_width,
render_markers=render_markers,
marker_style=marker_style,
marker_size=marker_size,
marker_face_colour=marker_face_colour,
marker_edge_colour=marker_edge_colour,
marker_edge_width=marker_edge_width,
render_numbering=render_numbering,
numbers_horizontal_align=numbers_horizontal_align,
numbers_vertical_align=numbers_vertical_align,
numbers_font_name=numbers_font_name,
numbers_font_size=numbers_font_size,
numbers_font_style=numbers_font_style,
numbers_font_weight=numbers_font_weight,
numbers_font_colour=numbers_font_colour,
render_axes=render_axes,
axes_font_name=axes_font_name,
axes_font_size=axes_font_size,
axes_font_style=axes_font_style,
axes_font_weight=axes_font_weight,
axes_x_limits=axes_x_limits,
axes_y_limits=axes_y_limits,
axes_x_ticks=axes_x_ticks,
axes_y_ticks=axes_y_ticks,
figure_size=figure_size,
label=label,
)
return renderer

def _view_landmarks_2d(
self,
group=None,
with_labels=None,
without_labels=None,
figure_id=None,
new_figure=False,
image_view=True,
render_lines=True,
line_colour="k",
line_style="-",
line_width=2,
render_markers=True,
marker_style="s",
marker_size=7,
marker_face_colour="k",
marker_edge_colour="k",
marker_edge_width=1.0,
render_lines_lms=True,
line_colour_lms=None,
line_style_lms="-",
line_width_lms=1,
render_markers_lms=True,
marker_style_lms="o",
marker_size_lms=5,
marker_face_colour_lms=None,
marker_edge_colour_lms=None,
marker_edge_width_lms=1.0,
render_numbering=False,
numbers_horizontal_align="center",
numbers_vertical_align="bottom",
numbers_font_name="sans-serif",
numbers_font_size=10,
numbers_font_style="normal",
numbers_font_weight="normal",
numbers_font_colour="k",
render_legend=False,
legend_title="",
legend_font_name="sans-serif",
legend_font_style="normal",
legend_font_size=10,
legend_font_weight="normal",
legend_marker_scale=None,
legend_location=2,
legend_bbox_to_anchor=(1.05, 1.0),
legend_n_columns=1,
legend_horizontal_spacing=None,
legend_vertical_spacing=None,
legend_border=True,
legend_rounded_corners=False,
render_axes=False,
axes_font_name="sans-serif",
axes_font_size=10,
axes_font_style="normal",
axes_font_weight="normal",
axes_x_limits=None,
axes_y_limits=None,
axes_x_ticks=None,
axes_y_ticks=None,
figure_size=(7, 7),
):
"""
Visualize the landmarks. This method will appear on the PointGraph as
view_landmarks.

Parameters
----------
group : str orNone optional
The landmark group to be visualized. If None and there are more
than one landmark groups, an error is raised.
with_labels : None or str or list of str, optional
If not None, only show the given label(s). Should **not** be
used with the without_labels kwarg.
without_labels : None or str or list of str, optional
If not None, show all except the given label(s). Should **not**
be used with the with_labels kwarg.
figure_id : object, optional
The id of the figure to be used.
new_figure : bool, optional
If True, a new figure is created.
image_view : bool, optional
If True the PointCloud will be viewed as if it is in the image
coordinate system.
render_lines : bool, optional
If True, the edges will be rendered.
line_colour : See Below, optional
The colour of the lines.
Example options::

{r, g, b, c, m, k, w}
or
(3, ) ndarray

line_style : {-, --, -., :}, optional
The style of the lines.
line_width : float, optional
The width of the lines.
render_markers : bool, optional
If True, the markers will be rendered.
marker_style : See Below, optional
The style of the markers. Example options ::

{., ,, o, v, ^, <, >, +, x, D, d, s, p, *, h, H, 1, 2, 3, 4, 8}

marker_size : int, optional
The size of the markers in points.
marker_face_colour : See Below, optional
The face (filling) colour of the markers.
Example options ::

{r, g, b, c, m, k, w}
or
(3, ) ndarray

marker_edge_colour : See Below, optional
The edge colour of the markers.
Example options ::

{r, g, b, c, m, k, w}
or
(3, ) ndarray

marker_edge_width : float, optional
The width of the markers' edge.
render_lines_lms : bool, optional
If True, the edges of the landmarks will be rendered.
line_colour_lms : See Below, optional
The colour of the lines of the landmarks.
Example options::

{r, g, b, c, m, k, w}
or
(3, ) ndarray

line_style_lms : {-, --, -., :}, optional
The style of the lines of the landmarks.
line_width_lms : float, optional
The width of the lines of the landmarks.
render_markers : bool, optional
If True, the markers of the landmarks will be rendered.
marker_style : See Below, optional
The style of the markers of the landmarks. Example options ::

{., ,, o, v, ^, <, >, +, x, D, d, s, p, *, h, H, 1, 2, 3, 4, 8}

marker_size : int, optional
The size of the markers of the landmarks in points.
marker_face_colour : See Below, optional
The face (filling) colour of the markers of the landmarks.
Example options ::

{r, g, b, c, m, k, w}
or
(3, ) ndarray

marker_edge_colour : See Below, optional
The edge colour of the markers of the landmarks.
Example options ::

{r, g, b, c, m, k, w}
or
(3, ) ndarray

marker_edge_width : float, optional
The width of the markers' edge of the landmarks.
render_numbering : bool, optional
If True, the landmarks will be numbered.
numbers_horizontal_align : {center, right, left}, optional
The horizontal alignment of the numbers' texts.
numbers_vertical_align : {center, top, bottom, baseline}, optional
The vertical alignment of the numbers' texts.
numbers_font_name : See Below, optional
The font of the numbers. Example options ::

{serif, sans-serif, cursive, fantasy, monospace}

numbers_font_size : int, optional
The font size of the numbers.
numbers_font_style : {normal, italic, oblique}, optional
The font style of the numbers.
numbers_font_weight : See Below, optional
The font weight of the numbers.
Example options ::

{ultralight, light, normal, regular, book, medium, roman,
semibold, demibold, demi, bold, heavy, extra bold, black}

numbers_font_colour : See Below, optional
The font colour of the numbers.
Example options ::

{r, g, b, c, m, k, w}
or
(3, ) ndarray

render_legend : bool, optional
If True, the legend will be rendered.
legend_title : str, optional
The title of the legend.
legend_font_name : See below, optional
The font of the legend. Example options ::

{serif, sans-serif, cursive, fantasy, monospace}

legend_font_style : {normal, italic, oblique}, optional
The font style of the legend.
legend_font_size : int, optional
The font size of the legend.
legend_font_weight : See Below, optional
The font weight of the legend.
Example options ::

{ultralight, light, normal, regular, book, medium, roman,
semibold, demibold, demi, bold, heavy, extra bold, black}

legend_marker_scale : float, optional
The relative size of the legend markers with respect to the original
legend_location : int, optional
The location of the legend. The predefined values are:

=============== ==
'best'          0
'upper right'   1
'upper left'    2
'lower left'    3
'lower right'   4
'right'         5
'center left'   6
'center right'  7
'lower center'  8
'upper center'  9
'center'        10
=============== ==

legend_bbox_to_anchor : (float, float) tuple, optional
The bbox that the legend will be anchored.
legend_border_axes_pad : float, optional
The pad between the axes and legend border.
legend_n_columns : int, optional
The number of the legend's columns.
legend_horizontal_spacing : float, optional
The spacing between the columns.
legend_vertical_spacing : float, optional
The vertical space between the legend entries.
legend_border : bool, optional
If True, a frame will be drawn around the legend.
legend_border_padding : float, optional
The fractional whitespace inside the legend border.
legend_shadow : bool, optional
If True, a shadow will be drawn behind legend.
legend_rounded_corners : bool, optional
If True, the frame's corners will be rounded (fancybox).
render_axes : bool, optional
If True, the axes will be rendered.
axes_font_name : See Below, optional
The font of the axes. Example options ::

{serif, sans-serif, cursive, fantasy, monospace}

axes_font_size : int, optional
The font size of the axes.
axes_font_style : {normal, italic, oblique}, optional
The font style of the axes.
axes_font_weight : See Below, optional
The font weight of the axes.
Example options ::

{ultralight, light, normal, regular, book, medium, roman,
semibold,demibold, demi, bold, heavy, extra bold, black}

axes_x_limits : float or (float, float) or None, optional
The limits of the x axis. If float, then it sets padding on the
right and left of the PointCloud as a percentage of the PointCloud's
width. If tuple or list, then it defines the axis limits. If
None, then the limits are set automatically.
axes_y_limits : (float, float) tuple or None, optional
The limits of the y axis. If float, then it sets padding on the
top and bottom of the PointCloud as a percentage of the PointCloud's
height. If tuple or list, then it defines the axis limits. If
None, then the limits are set automatically.
axes_x_ticks : list or tuple or None, optional
The ticks of the x axis.
axes_y_ticks : list or tuple or None, optional
The ticks of the y axis.
figure_size : (float, float) tuple or None optional
The size of the figure in inches.

Raises
------
ValueError
If both with_labels and without_labels are passed.
ValueError
If the landmark manager doesn't contain the provided group label.
"""
if not self.has_landmarks:
raise ValueError(
"PointGraph does not have landmarks attached, "
"unable to view landmarks."
)
self_view = self.view(
figure_id=figure_id,
new_figure=new_figure,
image_view=image_view,
figure_size=figure_size,
render_markers=render_markers,
marker_style=marker_style,
marker_size=marker_size,
marker_face_colour=marker_face_colour,
marker_edge_colour=marker_edge_colour,
marker_edge_width=marker_edge_width,
render_lines=render_lines,
line_colour=line_colour,
line_style=line_style,
line_width=line_width,
)
# correct group label in legend
if group is None:
group = self.landmarks.group_labels[0]
landmark_view = self.landmarks[group].view(
with_labels=with_labels,
without_labels=without_labels,
figure_id=self_view.figure_id,
new_figure=False,
group=group,
image_view=image_view,
render_lines=render_lines_lms,
line_colour=line_colour_lms,
line_style=line_style_lms,
line_width=line_width_lms,
render_markers=render_markers_lms,
marker_style=marker_style_lms,
marker_size=marker_size_lms,
marker_face_colour=marker_face_colour_lms,
marker_edge_colour=marker_edge_colour_lms,
marker_edge_width=marker_edge_width_lms,
render_numbering=render_numbering,
numbers_horizontal_align=numbers_horizontal_align,
numbers_vertical_align=numbers_vertical_align,
numbers_font_name=numbers_font_name,
numbers_font_size=numbers_font_size,
numbers_font_style=numbers_font_style,
numbers_font_weight=numbers_font_weight,
numbers_font_colour=numbers_font_colour,
render_legend=render_legend,
legend_title=legend_title,
legend_font_name=legend_font_name,
legend_font_style=legend_font_style,
legend_font_size=legend_font_size,
legend_font_weight=legend_font_weight,
legend_marker_scale=legend_marker_scale,
legend_location=legend_location,
legend_bbox_to_anchor=legend_bbox_to_anchor,
legend_n_columns=legend_n_columns,
legend_horizontal_spacing=legend_horizontal_spacing,
legend_vertical_spacing=legend_vertical_spacing,
legend_border=legend_border,
legend_rounded_corners=legend_rounded_corners,
render_axes=render_axes,
axes_font_name=axes_font_name,
axes_font_size=axes_font_size,
axes_font_style=axes_font_style,
axes_font_weight=axes_font_weight,
axes_x_limits=axes_x_limits,
axes_y_limits=axes_y_limits,
axes_x_ticks=axes_x_ticks,
axes_y_ticks=axes_y_ticks,
figure_size=figure_size,
)

return landmark_view

def _view_3d(
self,
figure_id=None,
new_figure=True,
render_lines=True,
line_colour="r",
line_width=2,
render_markers=True,
marker_style="sphere",
marker_size=None,
marker_colour="k",
marker_resolution=8,
step=None,
alpha=1.0,
render_numbering=False,
numbers_colour="k",
numbers_size=None,
):
r"""
Visualization of the PointGraph in 3D.

Parameters
----------
figure_id : object, optional
The id of the figure to be used.
new_figure : bool, optional
If True, a new figure is created.
render_lines : bool, optional
If True, then the lines will be rendered.
line_colour : See Below, optional
The colour of the lines.
Example options ::

{r, g, b, c, m, k, w}
or
(3, ) ndarray

line_width : float, optional
The width of the lines.
render_markers : bool, optional
If True, then the markers will be rendered.
marker_style : str, optional
The style of the markers.
Example options ::

{2darrow, 2dcircle, 2dcross, 2ddash, 2ddiamond, 2dhooked_arrow,
2dsquare, 2dthick_arrow, 2dthick_cross, 2dtriangle, 2dvertex,
arrow, axes, cone, cube, cylinder, point, sphere}

marker_size : float or None, optional
The size of the markers. This size can be seen as a scale factor
applied to the size markers, which is by default calculated from
the inter-marker spacing. If None, then an optimal marker size
value will be set automatically.
marker_colour : See Below, optional
The colour of the markers.
Example options ::

{r, g, b, c, m, k, w}
or
(3, ) ndarray

marker_resolution : int, optional
The resolution of the markers. For spheres, for instance, this is
the number of divisions along theta and phi.
step : int or None, optional
If int, then one every step vertexes will be rendered.
If None, then all vertexes will be rendered.
alpha : float, optional
Defines the transparency (opacity) of the object.
render_numbering : bool, optional
If True, the points will be numbered.
numbers_colour : See Below, optional
The colour of the numbers.
Example options ::

{r, g, b, c, m, k, w}
or
(3, ) ndarray

numbers_size : float or None, optional
The size of the numbers. This size can be seen as a scale factor
applied to the numbers, which is by default calculated from
the inter-marker spacing. If None, then an optimal numbers size
value will be set automatically.

Returns
-------
renderer : menpo3d.visualize.PointGraphViewer3d
The Menpo3D rendering object.
"""
try:
from menpo3d.visualize import PointGraphViewer3d

renderer = PointGraphViewer3d(
figure_id, new_figure, self.points, self.edges
)
renderer.render(
render_lines=render_lines,
line_colour=line_colour,
line_width=line_width,
render_markers=render_markers,
marker_style=marker_style,
marker_size=marker_size,
marker_colour=marker_colour,
marker_resolution=marker_resolution,
step=step,
alpha=alpha,
render_numbering=render_numbering,
numbers_colour=numbers_colour,
numbers_size=numbers_size,
)
return renderer
except ImportError as e:
from menpo.visualize import Menpo3dMissingError

raise Menpo3dMissingError(e)

[docs]class PointUndirectedGraph(PointGraph, UndirectedGraph):
r"""
Class for defining an Undirected Graph with geometry.

Parameters
----------
points : (n_vertices, n_dims, ) ndarray
The array of point locations.
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, the adjacency_matrix will not be copied on assignment.
skip_checks : bool, optional
If True, no checks will be performed.

Raises
------
ValueError
A point for each graph vertex needs to be passed. Got n_points
points instead of n_vertices.
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, ),
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]])
points = np.array([[10, 30], [0, 20], [20, 20], [0, 10], [20, 10],
[0, 0]])

or ::

from scipy.sparse import 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))
points = np.array([[10, 30], [0, 20], [20, 20], [0, 10], [20, 10],
[0, 0]])

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]])
points = np.array([[10, 30], [0, 20], [20, 20], [0, 10], [20, 10],
[0, 0]])

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))
points = np.array([[10, 30], [0, 20], [20, 20], [0, 10], [20, 10],
[0, 0]])
"""

def __init__(self, points, adjacency_matrix, copy=True, skip_checks=False):
self._directed = False
super(PointUndirectedGraph, self).__init__(
)

[docs]    @classmethod
def init_from_edges(cls, points, edges, copy=True, skip_checks=False):
r"""
Construct a :map:PointUndirectedGraph from edges array.

Parameters
----------
points : (n_vertices, n_dims, ) ndarray
The array of point locations.
edges : (n_edges, 2, ) ndarray
The ndarray of edges, i.e. all the pairs of vertices that are
connected with an edge.
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 undirected graph ::

|---0---|
|       |
|       |
1-------2
|       |
|       |
3-------4
|
|
5

can be defined as ::

from menpo.shape import PointUndirectedGraph
import numpy as np
points = np.array([[10, 30], [0, 20], [20, 20], [0, 10], [20, 10],
[0, 0]])
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 = PointUndirectedGraph.init_from_edges(points, edges)

Finally, the following graph with isolated vertices ::

0---|
|
|
1       2
|
|
3-------4

5

can be defined as ::

from menpo.shape import PointUndirectedGraph
import numpy as np
points = np.array([[10, 30], [0, 20], [20, 20], [0, 10], [20, 10],
[0, 0]])
edges = np.array([[0, 2], [2, 0], [2, 4], [4, 2], [3, 4], [4, 3]])
graph = PointUndirectedGraph.init_from_edges(points, edges)

"""
edges, points.shape[0]
)

"""
A 1D boolean array with the same number of elements as the number of
points in the PointUndirectedGraph. This is then broadcast across
the dimensions of the PointUndirectedGraph and returns a new
PointUndirectedGraph containing only those points that were True

Parameters
----------
mask : (n_vertices,) ndarray
1D array of booleans

Returns
-------
pointgraph : :map:PointUndirectedGraph
A new pointgraph that has been masked.

Raises
------
ValueError
Mask must be a 1D boolean array of the same number of entries as
points in this PointUndirectedGraph.
"""
raise ValueError(
"Mask must be a 1D boolean array of the same "
"number of entries as points in this "
"PointUndirectedGraph."
)

return PointUndirectedGraph(
)
else:
# Get new adjacency_matrix and points
)
return PointUndirectedGraph(
)

[docs]    def minimum_spanning_tree(self, root_vertex):
r"""
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 : :map:PointTree
The computed minimum spanning tree with the points of self.

Raises
------
ValueError
Cannot compute minimum spanning tree of a graph with isolated
vertices
"""
# check if graph has isolated vertices
if self.has_isolated_vertices():
raise ValueError(
"Cannot compute minimum spanning tree of a graph "
"with isolated vertices."
)
# Compute MST. It returns an undirected graph.
# Get directed tree from the above undirected graph using DFS.
)
# remove isolated vertices from the points
return PointTree(
)

def __str__(self):
isolated = ""
if self.has_isolated_vertices():
isolated = " ({} isolated)".format(len(self.isolated_vertices()))
return "{}D undirected graph of {} vertices{} and {} " "edges.".format(
self.n_dims, self.n_vertices, isolated, self.n_edges
)

[docs]class PointDirectedGraph(PointGraph, DirectedGraph):
r"""
Class for defining a directed graph with geometry.

Parameters
----------
points : (n_vertices, n_dims) ndarray
The array representing the points.
adjacency_matrix : (n_vertices, n_vertices, ) ndarray or csr_matrix
The adjacency matrix of the graph in which the rows represent source
vertices and columns represent destination vertices. The non-edges must
be represented with zeros and the edges can have a weight value.
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
A point for each graph vertex needs to be passed. Got {n_points} points
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, ),

Examples
--------
The following directed graph ::

|-->0<--|
|       |
|       |
1<----->2
|       |
v       v
3------>4
|
v
5

can be defined as ::

import numpy as np
adjacency_matrix = np.array([[0, 0, 0, 0, 0, 0],
[1, 0, 1, 1, 0, 0],
[1, 1, 0, 0, 1, 0],
[0, 0, 0, 0, 1, 1],
[0, 0, 0, 0, 0, 0],
[0, 0, 0, 0, 0, 0]])
points = np.array([[10, 30], [0, 20], [20, 20], [0, 10], [20, 10],
[0, 0]])

or ::

from scipy.sparse import csr_matrix
adjacency_matrix = csr_matrix(([1] * 8, ([1, 2, 1, 2, 1, 2, 3, 3],
[0, 0, 2, 1, 3, 4, 4, 5])),
shape=(6, 6))
points = np.array([[10, 30], [0, 20], [20, 20], [0, 10], [20, 10],
[0, 0]])

The following graph with isolated vertices ::

0<--|
|
|
1       2
|
v
3------>4

5

can be defined as ::

import numpy as np
adjacency_matrix = np.array([[0, 0, 0, 0, 0, 0],
[0, 0, 0, 0, 0, 0],
[1, 0, 0, 0, 1, 0],
[0, 0, 0, 0, 1, 0],
[0, 0, 0, 0, 0, 0],
[0, 0, 0, 0, 0, 0]])
points = np.array([[10, 30], [0, 20], [20, 20], [0, 10], [20, 10],
[0, 0]])

or ::

from scipy.sparse import csr_matrix
adjacency_matrix = csr_matrix(([1] * 3, ([2, 2, 3], [0, 4, 4])),
shape=(6, 6))
points = np.array([[10, 30], [0, 20], [20, 20], [0, 10], [20, 10],
[0, 0]])
"""

def __init__(self, points, adjacency_matrix, copy=True, skip_checks=False):
self._directed = True
super(PointDirectedGraph, self).__init__(
)

[docs]    def relative_location_edge(self, parent, child):
r"""
Returns the relative location between the provided vertices. That is
if vertex j is the parent and vertex i is its child and vector l
denotes the coordinates of a vertex, then

::

l_i - l_j = [[x_i], [y_i]] - [[x_j], [y_j]] =
= [[x_i - x_j], [y_i - y_j]]

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
-------
relative_location : (2,) ndarray
The relative location vector.

Raises
------
ValueError
Vertices parent and child are not connected with an edge.
"""
if not self.is_edge(parent, child):
raise ValueError(
"Vertices {} and {} are not connected "
"with an edge.".format(parent, child)
)
return self.points[child, ...] - self.points[parent, ...]

[docs]    def relative_locations(self):
r"""
Returns the relative location between the vertices of each edge. If
vertex j is the parent and vertex i is its child and vector l denotes
the coordinates of a vertex, then:

::

l_i - l_j = [[x_i], [y_i]] - [[x_j], [y_j]] =
= [[x_i - x_j], [y_i - y_j]]

Returns
-------
relative_locations : (n_vertexes, 2) ndarray
The relative locations vector.
"""
return self.points[children] - self.points[parents]

"""
A 1D boolean array with the same number of elements as the number of
points in the PointDirectedGraph. This is then broadcast across the
dimensions of the PointDirectedGraph and returns a new
PointDirectedGraph containing only those points that were True in

Parameters
----------
mask : (n_points,) ndarray
1D array of booleans

Returns
-------
pointgraph : :map:PointDirectedGraph
A new pointgraph that has been masked.

Raises
------
ValueError
Mask must be a 1D boolean array of the same number of entries as
points in this PointDirectedGraph.
"""
raise ValueError(
"Mask must be a 1D boolean array of the same "
"number of entries as points in this "
"PointDirectedGraph."
)

return self.copy()
else:
# Get new adjacency_matrix and points
)
return PointDirectedGraph(
)

def __str__(self):
isolated = ""
if self.has_isolated_vertices():
isolated = " ({} isolated)".format(len(self.isolated_vertices()))
return "{}D directed graph of {} vertices{} and {} " "edges.".format(
self.n_dims, self.n_vertices, isolated, self.n_edges
)

[docs]class PointTree(PointDirectedGraph, Tree):
r"""
Class for defining a Tree with geometry.

Parameters
----------
points : (n_vertices, n_dims) ndarray
The array representing the points.
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
A point for each graph vertex needs to be passed. Got {n_points} points
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, ),
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]])
points = np.array([[30, 30], [10, 20], [50, 20], [0, 10], [20, 10],
[50, 10], [0, 0], [20, 0], [50, 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))
points = np.array([[30, 30], [10, 20], [50, 20], [0, 10], [20, 10],
[50, 10], [0, 0], [20, 0], [50, 0]])
"""

def __init__(
self, points, adjacency_matrix, root_vertex, copy=True, skip_checks=False
):
super(PointTree, self).__init__(
)
Tree.__init__(
)

[docs]    @classmethod
def init_from_edges(cls, points, edges, root_vertex, copy=True, skip_checks=False):
r"""
Construct a :map:PointTree from edges array.

Parameters
----------
points : (n_vertices, n_dims, ) ndarray
The array of point locations.
edges : (n_edges, 2, ) ndarray
The ndarray of edges, i.e. all the pairs of vertices that are
connected with an edge.
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)
"""
return cls(
)

[docs]    @classmethod
def init_2d_grid(
cls,
shape,
spacing=None,
root_vertex=None,
skip_checks=False,
):
r"""
Create a pointtree that exists on a regular 2D grid. The first
dimension is the number of rows in the grid and the second dimension
of the shape is the number of columns. spacing optionally allows
the definition of the distance between points (uniform over points).
The spacing may be different for rows and columns.

The default connectivity is the minimum spanning tree formed from
a triangulation of the grid. The default root will be the centre
of the grid.

Parameters
----------
shape : tuple of 2 int
The size of the grid to create, this defines the number of points
across each dimension in the grid. The first element is the number
of rows and the second is the number of columns.
spacing : int or tuple of 2 int, optional
The spacing between points. If a single int is provided, this
is applied uniformly across each dimension. If a tuple is
provided, the spacing is applied non-uniformly as defined e.g.
(2, 3) gives a spacing of 2 for the rows and 3 for the
columns.
adjacency_matrix : (n_vertices, n_vertices) ndarray or csr_matrix, optional
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.
skip_checks : bool, optional
If True, no checks will be performed. Only considered if an

Returns
-------
shape_cls : type(cls)
A PointCloud or subclass arranged in a grid.
"""
if root_vertex is None:
# Centre of the grid
root_vertex = np.ravel_multi_index(np.array(shape) // 2, shape)
# Default tree is a spanning tree. Create a triangular mesh
# because it has a low average degree and is a connected graph.
from .mesh.base import TriMesh

tmesh = TriMesh.init_2d_grid(shape, spacing=spacing).as_pointgraph(
copy=False, skip_checks=True
)
return tmesh.minimum_spanning_tree(root_vertex)
else:
return cls(
PointCloud.init_2d_grid(shape, spacing=spacing).points,
root_vertex,
copy=False,
skip_checks=skip_checks,
)

[docs]    @classmethod
def init_from_depth_image(
cls,
depth_image,
spacing=None,
root_vertex=None,
skip_checks=False,
):
r"""
Return a 3D point cloud from the given depth image. The depth image
is assumed to represent height/depth values and the XY coordinates
are assumed to unit spaced and represent image coordinates. This is
particularly useful for visualising depth values that have been
recovered from images.

The default connectivity is the minimum spanning tree formed from
a triangulation of the grid. The default root will be the centre
of the grid (for an unmasked image), otherwise it will be the
first pixel in the masked are of the image.

Parameters
----------
depth_image : :map:Image or subclass
A single channel image that contains depth values - as commonly
returned by RGBD cameras, for example.
spacing : int or tuple of 2 int, optional
The spacing between points. If a single int is provided, this
is applied uniformly across each dimension. If a tuple is
provided, the spacing is applied non-uniformly as defined e.g.
(2, 3) gives a spacing of 2 for the rows and 3 for the
columns.
adjacency_matrix : (n_vertices, n_vertices) ndarray or csr_matrix, optional
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.
skip_checks : bool, optional
If True, no checks will be performed. Only considered if an

Returns
-------
depth_cloud : type(cls)
A new 3D PointCloud with unit XY coordinates and the given depth
values as Z coordinates.
"""

if root_vertex is None and isinstance(depth_image, MaskedImage):
# If the image is masked then the masked area may not contain the
# default 'centre' root vertex, so we choose the first pixel
root_vertex = np.ravel_multi_index(
depth_image.indices()[0], depth_image.shape
)
elif root_vertex is None:
# Otherwise the default root is the centre of the image
root_vertex = np.ravel_multi_index(
np.array(depth_image.shape) // 2, depth_image.shape
)

# Default tree is a spanning tree. Create a triangular mesh
# because it has a low average degree and is a connected graph.
from .mesh.base import TriMesh

tmesh = TriMesh.init_2d_grid(depth_image.shape, spacing=spacing)
tmesh = tmesh.as_pointgraph(copy=False, skip_checks=True)
# Performing masking before spanning tree to ensure that the
# spanning tree is valid
# Reindex root vertex according to mask
tree_2d = tmesh.minimum_spanning_tree(root_vertex)
else:
points = PointCloud.init_2d_grid(depth_image.shape, spacing=spacing).points
tree_2d = cls(
points,
root_vertex,
copy=False,
skip_checks=skip_checks,
)

return cls(
np.hstack([tree_2d.points, depth_image.as_vector(keep_channels=True).T]),
tree_2d.root_vertex,
copy=False,
skip_checks=True,
)

"""
A 1D boolean array with the same number of elements as the number of
points in the PointTree. This is then broadcast across the dimensions
of the PointTree and returns a new PointTree containing only those
points that were True in the mask.

Parameters
----------
mask : (n_points,) ndarray
1D array of booleans

Returns
-------
pointtree : :map:PointTree
A new pointtree that has been masked.

Raises
------
ValueError
Mask must be a 1D boolean array of the same number of entries as
points in this PointTree.
ValueError
Cannot remove root vertex.
"""
raise ValueError(
"Mask must be a 1D boolean array of the same "
"number of entries as points in this PointTree."
)

return self.copy()
else:
# Impossible to remove root vertex
raise ValueError("Cannot remove root vertex.")
# Get new adjacency_matrix and points
)
root_vertex = self.root_vertex - np.sum(~mask[: self.root_vertex])
# iteratively find isolated vertices and remove them
n_components, labels = csgraph.connected_components(
)
while n_components > 1:
label_to_keep = labels[root_vertex]
)
n_components, labels = csgraph.connected_components(
)
return PointTree(
points,
root_vertex=root_vertex,
copy=True,
skip_checks=False,
)

def __str__(self):
return "{}D tree of depth {} with {} vertices and {} leaves.".format(
self.n_dims, self.maximum_depth, self.n_vertices, self.n_leaves
)

def _is_symmetric(array):
r"""
Check if an array is symmetric.

Parameters
----------
array : ndarray or scipy.sparse.csr_matrix
The array to check.

Returns
-------
is_symmetric : bool
True if the array is symmetric.
"""
return np.allclose(array.transpose().nonzero(), array.nonzero())

r"""
Checks whether the points array and the adjacency_matrix have the
same number of points.

Parameters
----------
points : (n_vertices, n_dims,) ndarray
Points array.
adjacency_matrix : (n_vertices, n_vertices,) ndarray

Raises
------
ValueError
A point for each graph vertex needs to be passed. Got {} points instead
of {}
"""
raise ValueError(
"A point for each graph vertex needs to be passed. "
)

r"""
Function that checks if the provided directed graph has cycles using a Depth
First Search (DFS).

Parameters
----------
adjacency_list : list of list of length n_vertices
The adjacency list of the graph.
directed : bool
Defines if the provided graph is directed or not.

Returns
-------
has_cycles : bool
Whether the graph has cycles.
"""

def dfs(node, entered, exited, tree_edges, back_edges):
if node not in entered:
if y not in entered:
tree_edges[y] = node
elif (
not directed
and tree_edges.get(node, None) != y
or directed
and y not in exited
):
dfs(y, entered, exited, tree_edges, back_edges)
return tree_edges, back_edges

if dfs(x, entered=set(), exited=set(), tree_edges={}, back_edges={})[1]:
return True
else:
return False

r"""

Parameters
----------
mask : (n_vertices,) ndarray
1D array of booleans
adjacency_matrix : (n_vertices, n_vertices,) ndarray
points : (n_vertices, n_dims) ndarray
The array representing the points.

Returns
-------
adjacency_matrix : ndarray
points : ndarray
"""
# Find the indices that have been asked to be removed
# Remove rows and columns from adjacency matrix
# remove rows from points

# find the set difference between {0, 1, ..., n_vertices} and the set
# of rows (columns) that have at least one non-zero element.
return list(rows.intersection(cols))

r"""
Converts an edges array to an adjacency matrix.

Parameters
----------
edges : (n_edges, 2, ) ndarray or None
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.

Returns
-------
adjacency_matrix : (n_vertices, n_vertices, ) csr_matrix
The adjacency matrix of the graph in which the rows represent source
vertices and columns represent destination vertices.
"""
if isinstance(edges, list):
edges = np.array(edges)
if edges is None or edges.shape[0] == 0:
return csr_matrix((n_vertices, n_vertices), dtype=np.int)
else:
return csr_matrix(
([1] * edges.shape[0], (edges[:, 0], edges[:, 1])),
shape=(n_vertices, n_vertices),
)

r"""
Converts an edges array to an adjacency matrix.

Parameters
----------
edges : (n_edges, 2, ) ndarray or None
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.

Returns
-------
adjacency_matrix : (n_vertices, n_vertices, ) csr_matrix
The adjacency matrix of the graph in which the rows represent source
vertices and columns represent destination vertices.
"""
if isinstance(edges, list):
edges = np.array(edges)
if edges is None or edges.shape[0] == 0: