PointUndirectedGraph

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

Bases: PointGraph, UndirectedGraph

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

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 (PointGraphViewer2d) – The viewer object.

_view_landmarks_2d(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_border_axes_pad=None, legend_n_columns=1, legend_horizontal_spacing=None, legend_vertical_spacing=None, legend_border=True, legend_border_padding=None, legend_shadow=False, 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 or``None`` 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 – If True, the markers of the landmarks will be rendered.

  • marker_style

    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 – The size of the markers of the landmarks in points.

  • marker_face_colour

    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

    The edge colour of the markers of the landmarks. Example options

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

  • marker_edge_width – 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.

as_vector(**kwargs)

Returns a flattened representation of the object as a single vector.

Returns

vector ((N,) ndarray) – The core representation of the object, flattened into a single vector. Note that this is always a view back on to the original object, but is not writable.

bounding_box()

Return a bounding box from two corner points as a directed graph. In the case of a 2D pointcloud, first point (0) should be nearest the origin. In the case of an image, this ordering would appear as:

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

In the case of a pointcloud, the ordering will appear as:

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

In the case of a 3D pointcloud, the first point (0) should be the near closest to the origin and the second point is the far opposite corner.

Returns

bounding_box (PointDirectedGraph) – The axis aligned bounding box of the PointCloud.

bounds(boundary=0)

The minimum to maximum extent of the PointCloud. An optional boundary argument can be provided to expand the bounds by a constant margin.

Parameters

boundary (float) – A optional padding distance that is added to the bounds. Default is 0, meaning the max/min of tightest possible containing square/cube/hypercube is returned.

Returns

  • min_b ((n_dims,) ndarray) – The minimum extent of the PointCloud and boundary along each dimension

  • max_b ((n_dims,) ndarray) – The maximum extent of the PointCloud and boundary along each dimension

centre()

The mean of all the points in this PointCloud (centre of mass).

Returns

centre ((n_dims) ndarray) – The mean of this PointCloud’s points.

centre_of_bounds()

The centre of the absolute bounds of this PointCloud. Contrast with centre(), which is the mean point position.

Returns

centre (n_dims ndarray) – The centre of the bounds of this PointCloud.

constrain_to_bounds(bounds)

Returns a copy of this PointCloud, constrained to lie exactly within the given bounds. Any points outside the bounds will be ‘snapped’ to lie exactly on the boundary.

Parameters

bounds ((n_dims, n_dims) tuple of scalars) – The bounds to constrain this pointcloud within.

Returns

constrained (PointCloud) – The constrained pointcloud.

copy()

Generate an efficient copy of this object.

Note that Numpy arrays and other Copyable objects on self will be deeply copied. Dictionaries and sets will be shallow copied, and everything else will be assigned (no copy will be made).

Classes that store state other than numpy arrays and immutable types should overwrite this method to ensure all state is copied.

Returns

type(self) – A copy of this object

distance_to(pointcloud, **kwargs)

Returns a distance matrix between this PointCloud and another. By default the Euclidean distance is calculated - see scipy.spatial.distance.cdist for valid kwargs to change the metric and other properties.

Parameters

pointcloud (PointCloud) – The second pointcloud to compute distances between. This must be of the same dimension as this PointCloud.

Returns

distance_matrix ((n_points, n_points) ndarray) – The symmetric pairwise distance matrix between the two PointClouds s.t. distance_matrix[i, j] is the distance between the i’th point of this PointCloud and the j’th point of the input PointCloud.

find_all_paths(start, end, path=[])

Returns a list of lists with all the paths (without cycles) found from start vertex to end vertex.

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

  • end (int) – The vertex from which the paths end.

  • path (list, optional) – An existing path to append to.

Returns

paths (list of list) – The list containing all the paths from start to end.

find_all_shortest_paths(algorithm='auto', unweighted=False)

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

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

    The algorithm to be used. Possible options are:

    ’dijkstra’

    Dijkstra’s algorithm with Fibonacci heaps

    ’bellman-ford’

    Bellman-Ford algorithm

    ’johnson’

    Johnson’s algorithm

    ’floyd-warshall’

    Floyd-Warshall algorithm

    ’auto’

    Select the best among the above

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

Returns

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

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

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

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

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

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

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

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

Returns

path (list) – The path’s vertices.

Raises

ValueError – Method must be either bfs or dfs.

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

Returns a list with the shortest path (without cycles) found from start vertex to end vertex.

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

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

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

    The algorithm to be used. Possible options are:

    ’dijkstra’

    Dijkstra’s algorithm with Fibonacci heaps

    ’bellman-ford’

    Bellman-Ford algorithm

    ’johnson’

    Johnson’s algorithm

    ’floyd-warshall’

    Floyd-Warshall algorithm

    ’auto’

    Select the best among the above

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

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

Returns

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

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

from_mask(mask)[source]

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 in the mask.

Parameters

mask ((n_vertices,) ndarray) – 1D array of booleans

Returns

pointgraph (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.

from_vector(vector)

Build a new instance of the object from it’s vectorized state.

self is used to fill out the missing state required to rebuild a full object from it’s standardized flattened state. This is the default implementation, which is which is a deepcopy of the object followed by a call to from_vector_inplace(). This method can be overridden for a performance benefit if desired.

Parameters

vector ((n_parameters,) ndarray) – Flattened representation of the object.

Returns

object (type(self)) – An new instance of this class.

from_vector_inplace(vector)

Deprecated. Use the non-mutating API, from_vector.

For internal usage in performance-sensitive spots, see _from_vector_inplace()

Parameters

vector ((n_parameters,) ndarray) – Flattened representation of this object

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.

h_points()

Convert poincloud to a homogeneous array: (n_dims + 1, n_points)

Type

type(self)

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.

has_nan_values()

Tests if the vectorized form of the object contains nan values or not. This is particularly useful for objects with unknown values that have been mapped to nan values.

Returns

has_nan_values (bool) – If the vectorized object contains nan values.

classmethod init_2d_grid(shape, spacing=None, adjacency_matrix=None, skip_checks=False)

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 adjacency matrix is provided.

Returns

pgraph (PointGraph) – A pointgraph arranged in a grid.

classmethod init_from_depth_image(depth_image, spacing=None, adjacency_matrix=None, skip_checks=False)

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 (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 adjacency matrix is provided.

Returns

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

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

Construct a 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)
is_edge(vertex_1, vertex_2, skip_checks=False)

Whether there is an edge between the provided vertices.

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

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

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

Returns

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

Raises

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

is_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 (PointTree) – The computed minimum spanning tree with the points of self.

Raises

ValueError – Cannot compute minimum spanning tree of a graph with isolated vertices

n_neighbours(vertex, skip_checks=False)

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)

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

norm(**kwargs)

Returns the norm of this PointCloud. This is a translation and rotation invariant measure of the point cloud’s intrinsic size - in other words, it is always taken around the point cloud’s centre.

By default, the Frobenius norm is taken, but this can be changed by setting kwargs - see numpy.linalg.norm for valid options.

Returns

norm (float) – The norm of this PointCloud

range(boundary=0)

The range of the extent of the PointCloud.

Parameters

boundary (float) – A optional padding distance that is used to extend the bounds from which the range is computed. Default is 0, no extension is performed.

Returns

range ((n_dims,) ndarray) – The range of the PointCloud extent in each dimension.

tojson()

Convert this PointGraph to a dictionary representation suitable for inclusion in the LJSON landmark format.

Returns

json (dict) – Dictionary with points and connectivity keys.

with_dims(dims)

Return a copy of this shape with only particular dimensions retained.

Parameters

dims (valid numpy array slice) – The slice that will be used on the dimensionality axis of the shape under transform. For example, to go from a 3D shape to a 2D one, [0, 1] could be provided or np.array([True, True, False]).

Returns

copy of self, with only the requested dims

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 has_landmarks

Whether the object has landmarks.

Type

bool

property landmarks

The landmarks object.

Type

LandmarkManager

property lms

Deprecated. Maintained for compatibility, will be removed in a future version. Returns a copy of this object, which previously would have held the ‘underlying’ PointCloud subclass.

Type

self

property n_dims

The number of dimensions in the pointcloud.

Type

int

property n_edges

Returns the number of edges.

Type

int

property n_landmark_groups

The number of landmark groups on this object.

Type

int

property n_parameters

The length of the vector that this object produces.

Type

int

property n_points

The number of points in the pointcloud.

Type

int

property n_vertices

Returns the number of vertices.

Type

int

property vertices

Returns the list of vertices.

Type

list