Bundle adjustment#

Simple bundle adjustment class

class BundleAdjust(camera: CentralCamera)[source][source]#

Create a bundle adjustment problem

Parameters:

camera (CentralCamera instance) – model of the moving camera

Implementation of a workable, easy to follow, bundle adjustment algorithm suitable for pedagogical purposes and problems of small to medium size.

It uses SciPy sparse linear algebra functions to solve the update equation. The state vector comprises, in order:

  • a 6-vector for every view, the camera pose \((t_x, t_y, t_z, q_x, q_y, q_z)\) as a translation vector and the vector part of the unit quaternion

  • a 3-vector for every landmark, (X, Y, Z)

Cameras and landmarks can be fixed in which case we have a variable state vector, shorter than the state vector, holding only the states corresponding to movable cameras and landmarks.

Warning

This class assumes that all camera views have the same camera intrinsics.

References:
Seealso:

optimize CentralCamera pgraph.UGraph

property nviews: int[source]#

Number of camera views

Returns:

Number of camera views

Return type:

int

Seealso:

add_view

property nlandmarks: int[source]#

Number of landmarks

Returns:

Number of landmarks

Return type:

int

Seealso:

add_landmark

property nstates: int[source]#

Length of state vector

Returns:

Length of the state vector

Return type:

int

This includes fixed views and landmarks whose state will not be updated in the optimization.

Seealso:

nvarstate

property nvarstates: int[source]#

Length of variable state vector

Returns:

Length of the variable state vector

Return type:

int

This is the length of the subset of the state vector that excludes fixed views and landmarks. It only includes cameras and landmarks whose state will be updated in the optimization.

Seealso:

nstates

add_view(pose: SE3 | ndarray, fixed: bool = False, color: str = 'black') → ViewPoint[source][source]#

Add camera view to bundle adjustment problem

Parameters:

  • pose (SE3, array_like(7)) – camera pose

  • fixed (bool, optional) – the camera is fixed, defaults to False

Returns:

new camera viewpoint

Return type:

ViewPoint

Creates a camera node and adds it to the bundle adjustment problem.

The camera pose can be SE3 or a vector (1x7) comprising translation and unit quaternion in vector form.

If the camera is fixed (anchored) it will not be adjusted in the optimization process.

Note

Adds a ViewPoint object as a node in the underlying scene graph.

Seealso:

add_landmark add_projection

add_landmark(P: ndarray, fixed: bool = False) → Landmark[source][source]#

Add 3D landmark point to bundle adjustment problem

Parameters:

  • P (array_like(3)) – 3D world point, aka landmark

  • fixed (bool, optional) – the landmark is fixed, defaults to False

Returns:

new landmark

Return type:

Landmark instance

Create a landmark node and add it to the bundle adjustment problem.

If the landmark is fixed (anchored) it will not be adjusted in the optimization process.

Note

Adds a Landmark object as a node in the underlying scene graph.

Seealso:

add_view add_projection

add_projection(viewpoint: ViewPoint, landmark: Landmark, uv: ndarray) → None[source][source]#

Add camera observation to bundle adjustment problem

Parameters:

  • view (ViewPoint) – camera viewpoint

  • landmark (Landmark) – landmark point

  • uv (array_like(2)) – image plane coordinate

Add an observation by viewpoint of a landmark to the bundle adjustment problem.

Note

Adds a Observation object as an edge in the underlying scene graph.

Seealso:

add_view add_landmark

classmethod load_SBA(cameraFile: str, pointFile: str, calibFile: str, imagesize: ndarray | None = None) → BundleAdjust[source][source]#

Load bundle adjustment data files

Parameters:

  • cameraFile (str) – name of file with camera view data

  • pointFile (str) – name of file with landmark data

  • calibFile (str) – name of file with camera intrinsic data

  • imagesize (array_like(2)) – image plane dimensions in pixels, if not given infer it from principal point data in calibFile

Provides access to bundle adjustment problems from data files as distributed with the SBA package. Details of the file format are given in the source code comments.

Example:

To solve the 7-point bundle adjustment problem distributed with SBA 1.6:

ba = Bundle.load_SBA('7cams.txt', '7pts.txt', 'calib.txt')
X = ba.optimize()
Reference:
Seealso:

add_view add_landmark add_projection

optimize(x: ndarray | None = None, animate: bool = False, lmbda: float = 0.1, lmbdamin: float = 1e-08, dxmin: float = 0.0001, tol: float = 0.5, iterations: int = 1000, verbose: bool = False) → tuple[ndarray, float][source][source]#

Perform the bundle adjustment

Parameters:

  • x – state vector, defaults to the state vector in the instance

  • animate (bool, optional) – graphically animate the updates, defaults to False

  • lmbda (float, optional) – initial damping term, defaults to 0.1

  • lmbdamin (float, optional) – minimum value of lmbda, defaults to 1e-8

  • dxmin (float, optional) – terminate optimization if state update norm falls below this threshold, defaults to 1e-4

  • tol (float, optional) – terminate optimization if error total reprojection error falls below this threshold, defaults to 0.5 pixels

  • iterations (int, optional) – maximum number of iterations, defaults to 1000

  • verbose (bool, optional) – show Levenberg-Marquadt status, defaults to False

Raises:

ValueError – no landmark projections have been added to the graph

Returns:

optimized state vector

Return type:

ndarray(N)

Performs a Levenberg-Marquadt style optimization of the bundle adjustment problem which repeatedly calls solve. Adjusts camera poses and landmark positions in order to minimize the total reprojection error.

References:
Seealso:

nstates solve build_linear_system

solve(x: ndarray, lmbda: float = 0.0) → tuple[ndarray, Any][source][source]#

Solve for state update

Parameters:

  • x (ndarray(N)) – state vector

  • lmbda (float, optional) – damping term, defaults to 0.0

Returns:

\(\delta \vec{X}\), update to the variable state vector

Return type:

ndarray(M)

Determines the state update \(\delta \vec{x}\) by creating and solving the linear equation

\[\mat{H} \delta \vec{x} = \vec{b}\]

where \(\mat{H}\) is the Hessian and \(\mat{b}\) is the the projection error.

Note

  • The damping term lmbda is added to the diagonal of the Hessian to prevent problems when the Hessian is nearly singular.

  • If the problem includes fixed cameras or landmarks then \(\text{len}(\delta \vec{x}) < \text{len}(\vec{x})\) since fixed elements are omitted from the variable state vector used for the optimization.

References:
Seealso:

build_linear_system

build_linear_system(x: ndarray) → tuple[Any, Any, Any][source][source]#

Build the linear system

Parameters:

x (ndarray(N)) – state vector

Returns:

Hessian \(\mat{H}(\vec{x})\) and projection error \(\vec{b}\)

Return type:

sparse_array(N,N), sparse_ndarray(N,1), float

Build the block structured Hessian matrix based on current bundle adjustment state and the Jacobians.

References:
Seealso:

spy derivatives

spyH(x: ndarray, block: bool = False) → None[source][source]#

Display sparsity of Hessian

Parameters:

x (ndarray(N)) – state vector

Use Matplotlib to display the zero and non-zero elements of the Hessian.

Seealso:

build_linear_system

getstate() → ndarray[source][source]#

Get the state vector

Returns:

state vector

Return type:

ndarray(N)

Build the state vector by concatenating the pose of all cameras and then the position of all landmarks. That information is provided at problem initialization by calls to add_view and add_landmark.

Seealso:

setstate nstates add_view add_landmark

setstate(x: ndarray) → None[source][source]#

Update camera and landmark state

Parameters:

x (ndarray(N)) – new state vector

Copy new state data into the nodes of the bundle adjustment graph. Those nodes corresponding to fixed cameras or landmarks are unchanged.

Seealso:

updatestate getstate

updatestate(x: ndarray, dx: ndarray) → ndarray[source][source]#

Update the state vector

Parameters:

  • x (ndarray(N)) – state vector

  • dx (ndarray(M)) – variable state update vector

Returns:

updated state vector

Return type:

ndarray(N)

The elements of the update to the variable state are inserted into the state vector. Those elements corresponding to fixed cameras or landmarks are unchanged.

Seealso:

setstate nstates

errors(x: ndarray | None = None) → Any[source][source]#

Total reprojection error

Parameters:

x (ndarray(N), optional) – state vector, defaults to state vector in instance

Returns:

total residual

Return type:

float

Compute the total reprojection error, of all projected landmarks on all camera viewpoints. Is ideally zero.

Seealso:

getresidual

getresidual(x: ndarray | None = None) → ndarray[source][source]#

Get error residuals

Parameters:

X (ndarray(N), optional) – state vector, defaults to state vector in instance

Returns:

residuals \(\mat{R}\) for each observation

Return type:

ndarray(V,L)

Returns a 2D array \(\mat{R}\) whose elements \(r_{ij}\) represent the Euclidean reprojection error for camera \(i\) observing landmark \(j\).

Seealso:

errors

property graph: Any[source]#

Get the scene graph

Returns:

scene graph

Return type:

PGraph

The scene graph has nodes representing camera viewpoints, of type ViewPoint, and nodes representing landmarks, of type Landmark. An edge, of type Observation, exists between a landmark and the viewpoint that observed, and the edge has the associated image plane projection.

plot(camera: dict[str, Any] = {}, block: bool | None = None, ax: Any = None, **kwargs) → None[source][source]#

Plot the scene graph

Parameters:

  • camera (dict, optional) – options passed to CentralCamera.plot, defaults to {}

  • ax (Axes, optional) – axis to plot into, defaults to None

  • kwargs – options passed to PGraph.plot

Display the nodes and edges of the scene graph as an embedded graph. Overlay camera icons to indicate the camera viewpoint nodes.

Seealso:

graph

Scene graph classes#

class ViewPoint(x: ndarray, fixed: bool = False, color: str | None = None)[source][source]#

Create new camera viewpoint

Parameters:

  • x (array_like(6)) – viewpoint pose as translation + vector part of unit quaternion

  • fixed (bool, optional) – camera is fixed, defaults to False

  • color (str, optional) – color with which to draw camera icon, defaults to None

Represent a camera viewpoint in the bundle adjustment problem. If the camera is not fixed it will be adjusted during the optimization.

Seealso:

pgraph.Vertex

property pose: SE3[source]#

Get pose of camera

Returns:

pose as an SE(3)

Return type:

SE3

adjacent() → list[Vertex]#

Vertices adjacent to this vertex

Returns:

the vertices at the far end of this vertex’s edges

Return type:

list of Vertex subclass

v.adjacent() is a list of the vertices that this vertex is joined to by an edge. “Adjacent” is the graph-theory term, and it is the relation that Graph.adjacency tabulates: row i of the adjacency matrix is non-zero exactly at the columns of the vertices returned by g[i].adjacent().

Note

  • For a directed graph these are the vertices at the head of the edges leaving this vertex, the successors.

  • There is one entry per edge, so a vertex joined by k parallel edges appears k times. In an undirected graph a self-loop lists the vertex itself twice, once for each end.

  • neighbours and neighbors are aliases, the same method under the British and American spellings, and are not deprecated.

>>> from pgraph import UGraph
>>> g = UGraph()
>>> v1 = g.add_vertex(coord=[0,0], name='v1')
>>> v2 = g.add_vertex(coord=[1,1], name='v2')
>>> v3 = g.add_vertex(coord=[2,2], name='v3')
>>> g.add_edge(v1, v2)
Edge{[v1] -- [v2], cost=1.414}
>>> g.add_edge(v1, v3)
Edge{[v1] -- [v3], cost=2.828}
>>> print(v1.adjacent())
[Vertex[v2, coord=(1, 1)], Vertex[v3, coord=(2, 2)]]
Seealso:

isadjacent successors predecessors incidences out_edges edges Graph.adjacency

closest() → tuple[Vertex | None, float]#

Return the closest vertex to this vertex

Returns:

closest vertex and its distance

Return type:

Vertex subclass or None, float

Equivalent to self._graph.closest(self.coord). The vertex must belong to a graph, since closest() searches that graph’s other vertices.

>>> from pgraph import UGraph
>>> g = UGraph()
>>> v1 = g.add_vertex(coord=[0,0], name='v1')
>>> v2 = g.add_vertex(coord=[1,1], name='v2')
>>> v3 = g.add_vertex(coord=[2,3], name='v3')
>>> v4 = g.add_vertex(coord=[4,3], name='v4')
>>> print(v1.closest())
(Vertex[v1, coord=(0, 0)], 0.0)
Seealso:

Graph.closest

connect(dest: Vertex, edge: Edge | None = None, cost: float | None = None, data: Any = None) → Edge#

Connect two vertices with an edge

Parameters:

  • dest (Vertex subclass) – The vertex to connect to

  • edge (Edge subclass, optional) – Use this as the edge object, otherwise a new object of the graph’s Graph.edge_class is created from the vertices being connected, and the cost and data parameters, defaults to None

  • cost (float, optional) – the cost to traverse this edge, defaults to None

  • data (Any, optional) – reference to arbitrary data associated with the edge, defaults to None

Raises:

  • ValueError – either vertex has not been added to a graph, the vertices belong to different graphs, or edge already connects other vertices

  • TypeError – edge is not an instance of the graph’s Graph.edge_class

Returns:

the edge connecting the vertices

Return type:

Edge

v1.connect(v2) connects vertex v1 to vertex v2.

Note

  • In an undirected graph the edge is recorded in the edge list of both vertices, so it is found from either end. In a directed graph it is recorded as leaving this, the start, vertex and entering dest.

  • A supplied edge built without vertices has its v1 and v2 set to the vertices being connected. One built with vertices must agree with them: in either order if undirected, exactly self then dest if directed.

  • Both vertices must already have been added to the same graph, e.g. via Graph.add_vertex.

>>> from pgraph import UGraph
>>> g = UGraph()
>>> v1 = g.add_vertex(coord=[0,0], name='v1')
>>> v2 = g.add_vertex(coord=[1,1], name='v2')
>>> e = v1.connect(v2, cost=1.414)
>>> print(e)
Edge{[v1] -- [v2], cost=1.414}
Seealso:

Edge Edge.connect

copy(cls: type[Graph] | None = None) → Vertex#

Copy a vertex

Parameters:

cls (UGraph or DGraph subclass, optional) – graph class whose vertex_copy method should be used to create the copy, defaults to None

Returns:

a new, unconnected vertex with the same coordinate and name

Return type:

Vertex subclass

If cls is given, cls.vertex_copy(self) is used to create a vertex of the appropriate subclass for that graph type, otherwise a vertex of the same class as self is created directly.

>>> from pgraph import Vertex, DGraph
>>> v = Vertex(coord=[1,2], name='v1')
>>> v2 = v.copy(cls=DGraph)
>>> print(v2)
[v1]
Seealso:

Graph.vertex_copy

property degree: int#

Degree of vertex

Returns:

degree of the vertex

Return type:

int

The number of edge ends at this vertex: the edges leaving it plus the edges entering it, so a self-loop counts twice. The degrees of all the vertices of a graph sum to twice its number of edges.

For an undirected graph this is the number of incident edges. For a directed graph it is in_degree + out_degree.

Changed in version 1.0: For a DGraph this used to count only the edges leaving the vertex. It is now the graph-theory degree, in plus out. Use out_degree for the previous value.

>>> from pgraph import DGraph
>>> g = DGraph()
>>> v1 = g.add_vertex(coord=[0,0], name='v1')
>>> v2 = g.add_vertex(coord=[1,1], name='v2')
>>> v3 = g.add_vertex(coord=[2,2], name='v3')
>>> g.add_edge(v1, v2)
Edge{[v1] -> [v2], cost=1.414}
>>> g.add_edge(v1, v3)
Edge{[v1] -> [v3], cost=2.828}
>>> g.add_edge(v3, v1)
Edge{[v3] -> [v1], cost=2.828}
>>> print(v1.degree, v1.in_degree, v1.out_degree)
3 1 2

For graphs with parallel edges or loops

Every edge is counted, so k parallel edges to the same vertex add k. A self-loop adds 2, for both kinds of graph: it has two ends.

Seealso:

in_degree out_degree edges Graph.degree Graph.connectivity

distance(coord: ArrayLike | Vertex) → float#

Distance from vertex to point

Parameters:

coord (ndarray(n) or Vertex) – coordinates of the point

Returns:

distance

Return type:

float

Distance is computed according to the graph’s metric. The vertex must belong to a graph, since the metric is a property of the graph, not the vertex.

>>> from pgraph import UGraph
>>> g = UGraph()
>>> v1 = g.add_vertex(coord=[0,0], name='v1')
>>> v2 = g.add_vertex(coord=[3,4], name='v2')
>>> print(v1.distance(v2))
5.0
Seealso:

Graph.metric

edges() → list[Edge]#

The edges at the vertex, in the order they were connected

Returns:

the edges at this vertex

Return type:

list of Edge

For a directed graph these are the edges leaving this vertex. For an undirected graph they are the edges incident on it, whichever end it is. A self-loop in an undirected graph is listed twice, once for each end.

The list is a new one on every call, in the order the edges were connected, so changing it does not change the graph, and edges can be removed from the graph while iterating over it. Use Graph.remove_edge to remove one.

>>> from pgraph import UGraph
>>> g = UGraph()
>>> v1 = g.add_vertex(coord=[0,0], name='v1')
>>> v2 = g.add_vertex(coord=[1,1], name='v2')
>>> g.add_edge(v1, v2)
Edge{[v1] -- [v2], cost=1.414}
>>> print(v1.edges())
[Edge{[v1] -- [v2], cost=1.414}]
Seealso:

out_edges in_edges adjacent incidences edges_to degree Graph.edges

edges_to(dest: Vertex) → list[Edge]#

All the edges from this vertex to another vertex

Parameters:

dest (Vertex subclass) – the vertex at the far end

Returns:

every edge from this vertex to dest, in the order they were connected, which is empty if there are none

Return type:

list of Edge

This is how to see parallel edges. edgeto returns the one edge that a path would use, the cheapest, whereas this returns them all.

Note

  • For a directed graph only the edges leaving this vertex for dest are included, so a.edges_to(b) and b.edges_to(a) are different lists

  • For an undirected graph the edges are found from either end, whichever vertex they were connected from

  • A self-loop is listed once, although its vertex holds it twice (see edges)

  • Unlike edgeto, there being no edge is not an error, the list is empty

  • The list is a new one, so changing it does not change the graph

>>> from pgraph import UGraph
>>> g = UGraph()
>>> v1 = g.add_vertex(coord=[0,0], name='v1')
>>> v2 = g.add_vertex(coord=[1,1], name='v2')
>>> g.add_edge(v1, v2, cost=3)
Edge{[v1] -- [v2], cost=3}
>>> g.add_edge(v1, v2, cost=1)
Edge{[v1] -- [v2], cost=1}
>>> print(v1.edges_to(v2))
[Edge{[v1] -- [v2], cost=3}, Edge{[v1] -- [v2], cost=1}]
>>> print(v1.edgeto(v2))
Edge{[v1] -- [v2], cost=1}
Seealso:

edgeto edges out_edges incidences adjacent

edgeto(dest: Vertex) → Edge#

The edge from this vertex to an adjacent vertex

Parameters:

dest (Vertex subclass) – an adjacent vertex

Raises:

ValueError – dest is not adjacent to this vertex

Returns:

the edge from this vertex to dest

Return type:

Edge

Note

  • For a directed graph dest must be at the arrow end of the edge

  • If there are parallel edges to dest the cheapest is returned (the first, if none of them has a cost)

>>> from pgraph import UGraph
>>> g = UGraph()
>>> v1 = g.add_vertex(coord=[0,0], name='v1')
>>> v2 = g.add_vertex(coord=[1,1], name='v2')
>>> g.add_edge(v1, v2, cost=1.414)
Edge{[v1] -- [v2], cost=1.414}
>>> print(v1.edgeto(v2))
Edge{[v1] -- [v2], cost=1.414}
Seealso:

edges_to incidences adjacent

heuristic_distance(v2: Vertex) → float#

Heuristic distance to another vertex

Parameters:

v2 (Vertex subclass) – the other vertex

Returns:

heuristic distance between this vertex and v2

Return type:

float

Distance is computed according to the graph’s heuristic, see Graph.heuristic. The vertex must belong to a graph, since the heuristic is a property of the graph, not the vertex.

>>> from pgraph import UGraph
>>> g = UGraph()
>>> v1 = g.add_vertex(coord=[1, 2], name='v1')
>>> v2 = g.add_vertex(coord=[4, 3], name='v2')
>>> print(v1.heuristic_distance(v2))
3.1622776601683795
Seealso:

distance Graph.heuristic

property in_degree: int#

Number of edges entering the vertex

Returns:

in-degree of the vertex

Return type:

int

For an undirected graph every incident edge both leaves and enters, so this equals degree.

Seealso:

out_degree degree in_edges

in_edges() → list[Edge]#

The edges entering the vertex

Returns:

the incoming edges, in the order they were connected

Return type:

list of Edge

This is a new list. For an undirected graph every incident edge is incoming, so it equals edges.

Seealso:

out_edges edges predecessors in_degree

incidences() → list[tuple[Vertex, Edge]]#

Adjacent vertices paired with the edges that lead to them

Returns:

a (vertex, edge) pair for each edge leaving this vertex, in the order the edges were connected

Return type:

list of (Vertex subclass, Edge)

v.incidences() is adjacent and out_edges taken together: the first element of each pair is the vertex at the far end of the edge, the second is the edge itself, so its Edge.cost and Edge.data are at hand. It is equivalent to:

list(zip(v.adjacent(), v.out_edges()))

but is built in a single pass, which is what the path-planning methods want when they expand a vertex.

Note

  • In graph-theory terms adjacent is a vertex’s adjacency list, out_edges its incidence list, and this is the two joined.

  • For a directed graph the pairs are for the edges leaving this vertex. The ones entering it are in_edges, and the vertices at their tails are predecessors.

  • There is one pair per edge, so parallel edges to the same vertex give repeated vertices with different edges, and an undirected self-loop gives the pair twice, once for each end.

>>> from pgraph import UGraph
>>> g = UGraph()
>>> v1 = g.add_vertex(coord=[0,0], name='v1')
>>> v2 = g.add_vertex(coord=[1,1], name='v2')
>>> v3 = g.add_vertex(coord=[2,2], name='v3')
>>> g.add_edge(v1, v2, cost=1.5)
Edge{[v1] -- [v2], cost=1.5}
>>> g.add_edge(v1, v3, cost=2.5)
Edge{[v1] -- [v3], cost=2.5}
>>> for vertex, edge in v1.incidences():
...     print(vertex.name, edge.cost)
v2 1.5
v3 2.5
Seealso:

adjacent isadjacent successors out_edges in_edges predecessors edgeto edges_to edges edgeto degree Graph.adjacency

property index: int[source]#

Index into the state vector (base method)

Returns:

the index of the start of this object’s state in the state vector

Return type:

int

property index2: int[source]#

Index into the variable state vector (base method)

Returns:

the index of the start of this object’s state in the variable state vector

Return type:

int

isadjacent(vertex: Vertex) → bool#

Test if a vertex is adjacent to this vertex

Parameters:

vertex (Vertex subclass) – vertex reference

Returns:

true if vertex is adjacent

Return type:

bool

For a directed graph this is true only if there is an edge from self to vertex.

isneighbour and isneighbor are aliases.

>>> from pgraph import UGraph
>>> g = UGraph()
>>> v1 = g.add_vertex(coord=[0,0], name='v1')
>>> v2 = g.add_vertex(coord=[1,1], name='v2')
>>> v3 = g.add_vertex(coord=[2,2], name='v3')
>>> g.add_edge(v1, v2)
Edge{[v1] -- [v2], cost=1.414}
>>> print(v1.isadjacent(v2))
True
>>> print(v1.isadjacent(v3))
False
Seealso:

adjacent

property isfixed: bool[source]#

Value is fixed (base method)

Returns:

Quantity is fixed

Return type:

bool

This viewpoint or landmark will not be adjusted during optimization.

isneighbor(vertex: Vertex) → bool#

Test if a vertex is adjacent to this vertex

Parameters:

vertex (Vertex subclass) – vertex reference

Returns:

true if vertex is adjacent

Return type:

bool

For a directed graph this is true only if there is an edge from self to vertex.

isneighbour and isneighbor are aliases.

>>> from pgraph import UGraph
>>> g = UGraph()
>>> v1 = g.add_vertex(coord=[0,0], name='v1')
>>> v2 = g.add_vertex(coord=[1,1], name='v2')
>>> v3 = g.add_vertex(coord=[2,2], name='v3')
>>> g.add_edge(v1, v2)
Edge{[v1] -- [v2], cost=1.414}
>>> print(v1.isadjacent(v2))
True
>>> print(v1.isadjacent(v3))
False
Seealso:

adjacent

isneighbour(vertex: Vertex) → bool#

Test if a vertex is adjacent to this vertex

Parameters:

vertex (Vertex subclass) – vertex reference

Returns:

true if vertex is adjacent

Return type:

bool

For a directed graph this is true only if there is an edge from self to vertex.

isneighbour and isneighbor are aliases.

>>> from pgraph import UGraph
>>> g = UGraph()
>>> v1 = g.add_vertex(coord=[0,0], name='v1')
>>> v2 = g.add_vertex(coord=[1,1], name='v2')
>>> v3 = g.add_vertex(coord=[2,2], name='v3')
>>> g.add_edge(v1, v2)
Edge{[v1] -- [v2], cost=1.414}
>>> print(v1.isadjacent(v2))
True
>>> print(v1.isadjacent(v3))
False
Seealso:

adjacent

property label: int | None#

Number of the graph component that contains the vertex

Returns:

component number, counted from 0, or None if the vertex is not in a graph

Return type:

int or None

Assigned by the graph, which finds its components when this is read after the graph has changed, as it does for Graph.nc, Graph.component and Graph.samecomponent. The numbering is by the first vertex of each component, in the order the vertices were added. It is read-only.

Changed in version 1.0: Read-only. It was a plain attribute, but it is computed from the graph’s structure and meaningless to assign. Reading it finds the components; in 0.6.5 it was None until something else had.

Seealso:

Graph.nc Graph.component

property name: str | None#

Name of the vertex

Returns:

the name

Return type:

str or None

The name is the vertex’s key in its graph: g[name] and name in g look it up. A vertex that is not in a graph can be given any name, or none. For one that is in a graph:

  • assigning a new name updates the graph’s name table, so the vertex is then found under the new name and not the old

  • a name already used by another vertex in the graph raises ValueError and changes nothing

  • the name cannot be cleared

Changed in version 1.0: Renaming a vertex in a graph used to leave the graph’s name table stale, so lookups by the new name failed.

Seealso:

Graph.add_vertex

neighbors() → list[Vertex]#

Vertices adjacent to this vertex

Returns:

the vertices at the far end of this vertex’s edges

Return type:

list of Vertex subclass

v.adjacent() is a list of the vertices that this vertex is joined to by an edge. “Adjacent” is the graph-theory term, and it is the relation that Graph.adjacency tabulates: row i of the adjacency matrix is non-zero exactly at the columns of the vertices returned by g[i].adjacent().

Note

  • For a directed graph these are the vertices at the head of the edges leaving this vertex, the successors.

  • There is one entry per edge, so a vertex joined by k parallel edges appears k times. In an undirected graph a self-loop lists the vertex itself twice, once for each end.

  • neighbours and neighbors are aliases, the same method under the British and American spellings, and are not deprecated.

>>> from pgraph import UGraph
>>> g = UGraph()
>>> v1 = g.add_vertex(coord=[0,0], name='v1')
>>> v2 = g.add_vertex(coord=[1,1], name='v2')
>>> v3 = g.add_vertex(coord=[2,2], name='v3')
>>> g.add_edge(v1, v2)
Edge{[v1] -- [v2], cost=1.414}
>>> g.add_edge(v1, v3)
Edge{[v1] -- [v3], cost=2.828}
>>> print(v1.adjacent())
[Vertex[v2, coord=(1, 1)], Vertex[v3, coord=(2, 2)]]
Seealso:

isadjacent successors predecessors incidences out_edges edges Graph.adjacency

neighbours() → list[Vertex]#

Vertices adjacent to this vertex

Returns:

the vertices at the far end of this vertex’s edges

Return type:

list of Vertex subclass

v.adjacent() is a list of the vertices that this vertex is joined to by an edge. “Adjacent” is the graph-theory term, and it is the relation that Graph.adjacency tabulates: row i of the adjacency matrix is non-zero exactly at the columns of the vertices returned by g[i].adjacent().

Note

  • For a directed graph these are the vertices at the head of the edges leaving this vertex, the successors.

  • There is one entry per edge, so a vertex joined by k parallel edges appears k times. In an undirected graph a self-loop lists the vertex itself twice, once for each end.

  • neighbours and neighbors are aliases, the same method under the British and American spellings, and are not deprecated.

>>> from pgraph import UGraph
>>> g = UGraph()
>>> v1 = g.add_vertex(coord=[0,0], name='v1')
>>> v2 = g.add_vertex(coord=[1,1], name='v2')
>>> v3 = g.add_vertex(coord=[2,2], name='v3')
>>> g.add_edge(v1, v2)
Edge{[v1] -- [v2], cost=1.414}
>>> g.add_edge(v1, v3)
Edge{[v1] -- [v3], cost=2.828}
>>> print(v1.adjacent())
[Vertex[v2, coord=(1, 1)], Vertex[v3, coord=(2, 2)]]
Seealso:

isadjacent successors predecessors incidences out_edges edges Graph.adjacency

property out_degree: int#

Number of edges leaving the vertex

Returns:

out-degree of the vertex

Return type:

int

For an undirected graph every incident edge both leaves and enters, so this equals degree.

Seealso:

in_degree degree out_edges

out_edges() → list[Edge]#

The edges leaving the vertex

Returns:

the outgoing edges, in the order they were connected

Return type:

list of Edge

This is a new list, and is the same as edges: for an undirected graph every incident edge is outgoing.

Seealso:

in_edges edges adjacent successors incidences edges_to out_degree

predecessors() → list[Vertex]#

Vertices that have an edge to this vertex

Returns:

the vertices at the tail of the incoming edges

Return type:

list of Vertex subclass

There is one entry per edge, so a vertex joined by k parallel edges appears k times. For an undirected graph this is adjacent.

>>> from pgraph import DGraph
>>> g = DGraph()
>>> v1 = g.add_vertex(coord=[0,0], name='v1')
>>> v2 = g.add_vertex(coord=[1,1], name='v2')
>>> v3 = g.add_vertex(coord=[2,2], name='v3')
>>> g.add_edge(v1, v3)
Edge{[v1] -> [v3], cost=2.828}
>>> g.add_edge(v2, v3)
Edge{[v2] -> [v3], cost=1.414}
>>> print(v3.predecessors())
[Vertex[v1, coord=(0, 0)], Vertex[v2, coord=(1, 1)]]
Seealso:

successors adjacent in_edges in_degree

remove() → None#

Remove this vertex, and all its edges, from its graph

Raises:

ValueError – the vertex is not connected to a graph

v.remove() removes v, and every edge touching it (incoming or outgoing), from its graph. The Vertex object itself is not deleted.

Note

This is a thin convenience wrapper around Graph.remove_vertex.

Return type:

None

>>> from pgraph import UGraph
>>> g = UGraph()
>>> v1 = g.add_vertex(coord=[0,0], name='v1')
>>> v2 = g.add_vertex(coord=[1,1], name='v2')
>>> g.add_edge(v1, v2)
Edge{[v1] -- [v2], cost=1.414}
>>> v2.remove()
>>> print(g)
UGraph: 1 vertex, 0 edges, 1 component
Seealso:

Graph.remove_vertex Edge.remove

successors() → list[Vertex]#

Vertices that this vertex has an edge to

Returns:

the vertices at the head of the outgoing edges

Return type:

list of Vertex subclass

This is adjacent, under its directed-graph name.

Seealso:

predecessors adjacent incidences out_edges

property x: float#

The x-coordinate of an embedded vertex

Raises:

ValueError – the vertex has no coordinate

Returns:

The x-coordinate

Return type:

float

>>> from pgraph import Vertex
>>> v = Vertex(coord=[1,2], name='v1')
>>> print(v.x)
1
property y: float#

The y-coordinate of an embedded vertex

Raises:

ValueError – the vertex has no coordinate

Returns:

The y-coordinate

Return type:

float

>>> from pgraph import Vertex
>>> v = Vertex(coord=[1,2], name='v1')
>>> print(v.y)
2
property z: float#

The z-coordinate of an embedded vertex

Raises:

ValueError – the vertex has no coordinate

Returns:

The z-coordinate

Return type:

float

>>> from pgraph import Vertex
>>> v = Vertex(coord=[1,2,3], name='v1')
>>> print(v.z)
3
class Landmark(P: ndarray, fixed: bool = False)[source][source]#

Create new landmark point

Parameters:

  • P (ndarray(3)) – landmark coordinate

  • fixed (bool, optional) – point is fixed, defaults to False

Represent a world point in the bundle adjustment problem. If the point is not fixed it will be adjusted during the optimization.

Seealso:

pgraph.Vertex

property P: ndarray[source]#

Get landmark position

Returns:

landmark position in 3D

Return type:

ndarray(3)

adjacent() → list[Vertex]#

Vertices adjacent to this vertex

Returns:

the vertices at the far end of this vertex’s edges

Return type:

list of Vertex subclass

v.adjacent() is a list of the vertices that this vertex is joined to by an edge. “Adjacent” is the graph-theory term, and it is the relation that Graph.adjacency tabulates: row i of the adjacency matrix is non-zero exactly at the columns of the vertices returned by g[i].adjacent().

Note

  • For a directed graph these are the vertices at the head of the edges leaving this vertex, the successors.

  • There is one entry per edge, so a vertex joined by k parallel edges appears k times. In an undirected graph a self-loop lists the vertex itself twice, once for each end.

  • neighbours and neighbors are aliases, the same method under the British and American spellings, and are not deprecated.

>>> from pgraph import UGraph
>>> g = UGraph()
>>> v1 = g.add_vertex(coord=[0,0], name='v1')
>>> v2 = g.add_vertex(coord=[1,1], name='v2')
>>> v3 = g.add_vertex(coord=[2,2], name='v3')
>>> g.add_edge(v1, v2)
Edge{[v1] -- [v2], cost=1.414}
>>> g.add_edge(v1, v3)
Edge{[v1] -- [v3], cost=2.828}
>>> print(v1.adjacent())
[Vertex[v2, coord=(1, 1)], Vertex[v3, coord=(2, 2)]]
Seealso:

isadjacent successors predecessors incidences out_edges edges Graph.adjacency

closest() → tuple[Vertex | None, float]#

Return the closest vertex to this vertex

Returns:

closest vertex and its distance

Return type:

Vertex subclass or None, float

Equivalent to self._graph.closest(self.coord). The vertex must belong to a graph, since closest() searches that graph’s other vertices.

>>> from pgraph import UGraph
>>> g = UGraph()
>>> v1 = g.add_vertex(coord=[0,0], name='v1')
>>> v2 = g.add_vertex(coord=[1,1], name='v2')
>>> v3 = g.add_vertex(coord=[2,3], name='v3')
>>> v4 = g.add_vertex(coord=[4,3], name='v4')
>>> print(v1.closest())
(Vertex[v1, coord=(0, 0)], 0.0)
Seealso:

Graph.closest

connect(dest: Vertex, edge: Edge | None = None, cost: float | None = None, data: Any = None) → Edge#

Connect two vertices with an edge

Parameters:

  • dest (Vertex subclass) – The vertex to connect to

  • edge (Edge subclass, optional) – Use this as the edge object, otherwise a new object of the graph’s Graph.edge_class is created from the vertices being connected, and the cost and data parameters, defaults to None

  • cost (float, optional) – the cost to traverse this edge, defaults to None

  • data (Any, optional) – reference to arbitrary data associated with the edge, defaults to None

Raises:

  • ValueError – either vertex has not been added to a graph, the vertices belong to different graphs, or edge already connects other vertices

  • TypeError – edge is not an instance of the graph’s Graph.edge_class

Returns:

the edge connecting the vertices

Return type:

Edge

v1.connect(v2) connects vertex v1 to vertex v2.

Note

  • In an undirected graph the edge is recorded in the edge list of both vertices, so it is found from either end. In a directed graph it is recorded as leaving this, the start, vertex and entering dest.

  • A supplied edge built without vertices has its v1 and v2 set to the vertices being connected. One built with vertices must agree with them: in either order if undirected, exactly self then dest if directed.

  • Both vertices must already have been added to the same graph, e.g. via Graph.add_vertex.

>>> from pgraph import UGraph
>>> g = UGraph()
>>> v1 = g.add_vertex(coord=[0,0], name='v1')
>>> v2 = g.add_vertex(coord=[1,1], name='v2')
>>> e = v1.connect(v2, cost=1.414)
>>> print(e)
Edge{[v1] -- [v2], cost=1.414}
Seealso:

Edge Edge.connect

copy(cls: type[Graph] | None = None) → Vertex#

Copy a vertex

Parameters:

cls (UGraph or DGraph subclass, optional) – graph class whose vertex_copy method should be used to create the copy, defaults to None

Returns:

a new, unconnected vertex with the same coordinate and name

Return type:

Vertex subclass

If cls is given, cls.vertex_copy(self) is used to create a vertex of the appropriate subclass for that graph type, otherwise a vertex of the same class as self is created directly.

>>> from pgraph import Vertex, DGraph
>>> v = Vertex(coord=[1,2], name='v1')
>>> v2 = v.copy(cls=DGraph)
>>> print(v2)
[v1]
Seealso:

Graph.vertex_copy

property degree: int#

Degree of vertex

Returns:

degree of the vertex

Return type:

int

The number of edge ends at this vertex: the edges leaving it plus the edges entering it, so a self-loop counts twice. The degrees of all the vertices of a graph sum to twice its number of edges.

For an undirected graph this is the number of incident edges. For a directed graph it is in_degree + out_degree.

Changed in version 1.0: For a DGraph this used to count only the edges leaving the vertex. It is now the graph-theory degree, in plus out. Use out_degree for the previous value.

>>> from pgraph import DGraph
>>> g = DGraph()
>>> v1 = g.add_vertex(coord=[0,0], name='v1')
>>> v2 = g.add_vertex(coord=[1,1], name='v2')
>>> v3 = g.add_vertex(coord=[2,2], name='v3')
>>> g.add_edge(v1, v2)
Edge{[v1] -> [v2], cost=1.414}
>>> g.add_edge(v1, v3)
Edge{[v1] -> [v3], cost=2.828}
>>> g.add_edge(v3, v1)
Edge{[v3] -> [v1], cost=2.828}
>>> print(v1.degree, v1.in_degree, v1.out_degree)
3 1 2

For graphs with parallel edges or loops

Every edge is counted, so k parallel edges to the same vertex add k. A self-loop adds 2, for both kinds of graph: it has two ends.

Seealso:

in_degree out_degree edges Graph.degree Graph.connectivity

distance(coord: ArrayLike | Vertex) → float#

Distance from vertex to point

Parameters:

coord (ndarray(n) or Vertex) – coordinates of the point

Returns:

distance

Return type:

float

Distance is computed according to the graph’s metric. The vertex must belong to a graph, since the metric is a property of the graph, not the vertex.

>>> from pgraph import UGraph
>>> g = UGraph()
>>> v1 = g.add_vertex(coord=[0,0], name='v1')
>>> v2 = g.add_vertex(coord=[3,4], name='v2')
>>> print(v1.distance(v2))
5.0
Seealso:

Graph.metric

edges() → list[Edge]#

The edges at the vertex, in the order they were connected

Returns:

the edges at this vertex

Return type:

list of Edge

For a directed graph these are the edges leaving this vertex. For an undirected graph they are the edges incident on it, whichever end it is. A self-loop in an undirected graph is listed twice, once for each end.

The list is a new one on every call, in the order the edges were connected, so changing it does not change the graph, and edges can be removed from the graph while iterating over it. Use Graph.remove_edge to remove one.

>>> from pgraph import UGraph
>>> g = UGraph()
>>> v1 = g.add_vertex(coord=[0,0], name='v1')
>>> v2 = g.add_vertex(coord=[1,1], name='v2')
>>> g.add_edge(v1, v2)
Edge{[v1] -- [v2], cost=1.414}
>>> print(v1.edges())
[Edge{[v1] -- [v2], cost=1.414}]
Seealso:

out_edges in_edges adjacent incidences edges_to degree Graph.edges

edges_to(dest: Vertex) → list[Edge]#

All the edges from this vertex to another vertex

Parameters:

dest (Vertex subclass) – the vertex at the far end

Returns:

every edge from this vertex to dest, in the order they were connected, which is empty if there are none

Return type:

list of Edge

This is how to see parallel edges. edgeto returns the one edge that a path would use, the cheapest, whereas this returns them all.

Note

  • For a directed graph only the edges leaving this vertex for dest are included, so a.edges_to(b) and b.edges_to(a) are different lists

  • For an undirected graph the edges are found from either end, whichever vertex they were connected from

  • A self-loop is listed once, although its vertex holds it twice (see edges)

  • Unlike edgeto, there being no edge is not an error, the list is empty

  • The list is a new one, so changing it does not change the graph

>>> from pgraph import UGraph
>>> g = UGraph()
>>> v1 = g.add_vertex(coord=[0,0], name='v1')
>>> v2 = g.add_vertex(coord=[1,1], name='v2')
>>> g.add_edge(v1, v2, cost=3)
Edge{[v1] -- [v2], cost=3}
>>> g.add_edge(v1, v2, cost=1)
Edge{[v1] -- [v2], cost=1}
>>> print(v1.edges_to(v2))
[Edge{[v1] -- [v2], cost=3}, Edge{[v1] -- [v2], cost=1}]
>>> print(v1.edgeto(v2))
Edge{[v1] -- [v2], cost=1}
Seealso:

edgeto edges out_edges incidences adjacent

edgeto(dest: Vertex) → Edge#

The edge from this vertex to an adjacent vertex

Parameters:

dest (Vertex subclass) – an adjacent vertex

Raises:

ValueError – dest is not adjacent to this vertex

Returns:

the edge from this vertex to dest

Return type:

Edge

Note

  • For a directed graph dest must be at the arrow end of the edge

  • If there are parallel edges to dest the cheapest is returned (the first, if none of them has a cost)

>>> from pgraph import UGraph
>>> g = UGraph()
>>> v1 = g.add_vertex(coord=[0,0], name='v1')
>>> v2 = g.add_vertex(coord=[1,1], name='v2')
>>> g.add_edge(v1, v2, cost=1.414)
Edge{[v1] -- [v2], cost=1.414}
>>> print(v1.edgeto(v2))
Edge{[v1] -- [v2], cost=1.414}
Seealso:

edges_to incidences adjacent

heuristic_distance(v2: Vertex) → float#

Heuristic distance to another vertex

Parameters:

v2 (Vertex subclass) – the other vertex

Returns:

heuristic distance between this vertex and v2

Return type:

float

Distance is computed according to the graph’s heuristic, see Graph.heuristic. The vertex must belong to a graph, since the heuristic is a property of the graph, not the vertex.

>>> from pgraph import UGraph
>>> g = UGraph()
>>> v1 = g.add_vertex(coord=[1, 2], name='v1')
>>> v2 = g.add_vertex(coord=[4, 3], name='v2')
>>> print(v1.heuristic_distance(v2))
3.1622776601683795
Seealso:

distance Graph.heuristic

property in_degree: int#

Number of edges entering the vertex

Returns:

in-degree of the vertex

Return type:

int

For an undirected graph every incident edge both leaves and enters, so this equals degree.

Seealso:

out_degree degree in_edges

in_edges() → list[Edge]#

The edges entering the vertex

Returns:

the incoming edges, in the order they were connected

Return type:

list of Edge

This is a new list. For an undirected graph every incident edge is incoming, so it equals edges.

Seealso:

out_edges edges predecessors in_degree

incidences() → list[tuple[Vertex, Edge]]#

Adjacent vertices paired with the edges that lead to them

Returns:

a (vertex, edge) pair for each edge leaving this vertex, in the order the edges were connected

Return type:

list of (Vertex subclass, Edge)

v.incidences() is adjacent and out_edges taken together: the first element of each pair is the vertex at the far end of the edge, the second is the edge itself, so its Edge.cost and Edge.data are at hand. It is equivalent to:

list(zip(v.adjacent(), v.out_edges()))

but is built in a single pass, which is what the path-planning methods want when they expand a vertex.

Note

  • In graph-theory terms adjacent is a vertex’s adjacency list, out_edges its incidence list, and this is the two joined.

  • For a directed graph the pairs are for the edges leaving this vertex. The ones entering it are in_edges, and the vertices at their tails are predecessors.

  • There is one pair per edge, so parallel edges to the same vertex give repeated vertices with different edges, and an undirected self-loop gives the pair twice, once for each end.

>>> from pgraph import UGraph
>>> g = UGraph()
>>> v1 = g.add_vertex(coord=[0,0], name='v1')
>>> v2 = g.add_vertex(coord=[1,1], name='v2')
>>> v3 = g.add_vertex(coord=[2,2], name='v3')
>>> g.add_edge(v1, v2, cost=1.5)
Edge{[v1] -- [v2], cost=1.5}
>>> g.add_edge(v1, v3, cost=2.5)
Edge{[v1] -- [v3], cost=2.5}
>>> for vertex, edge in v1.incidences():
...     print(vertex.name, edge.cost)
v2 1.5
v3 2.5
Seealso:

adjacent isadjacent successors out_edges in_edges predecessors edgeto edges_to edges edgeto degree Graph.adjacency

property index: int[source]#

Index into the state vector (base method)

Returns:

the index of the start of this object’s state in the state vector

Return type:

int

property index2: int[source]#

Index into the variable state vector (base method)

Returns:

the index of the start of this object’s state in the variable state vector

Return type:

int

isadjacent(vertex: Vertex) → bool#

Test if a vertex is adjacent to this vertex

Parameters:

vertex (Vertex subclass) – vertex reference

Returns:

true if vertex is adjacent

Return type:

bool

For a directed graph this is true only if there is an edge from self to vertex.

isneighbour and isneighbor are aliases.

>>> from pgraph import UGraph
>>> g = UGraph()
>>> v1 = g.add_vertex(coord=[0,0], name='v1')
>>> v2 = g.add_vertex(coord=[1,1], name='v2')
>>> v3 = g.add_vertex(coord=[2,2], name='v3')
>>> g.add_edge(v1, v2)
Edge{[v1] -- [v2], cost=1.414}
>>> print(v1.isadjacent(v2))
True
>>> print(v1.isadjacent(v3))
False
Seealso:

adjacent

property isfixed: bool[source]#

Value is fixed (base method)

Returns:

Quantity is fixed

Return type:

bool

This viewpoint or landmark will not be adjusted during optimization.

isneighbor(vertex: Vertex) → bool#

Test if a vertex is adjacent to this vertex

Parameters:

vertex (Vertex subclass) – vertex reference

Returns:

true if vertex is adjacent

Return type:

bool

For a directed graph this is true only if there is an edge from self to vertex.

isneighbour and isneighbor are aliases.

>>> from pgraph import UGraph
>>> g = UGraph()
>>> v1 = g.add_vertex(coord=[0,0], name='v1')
>>> v2 = g.add_vertex(coord=[1,1], name='v2')
>>> v3 = g.add_vertex(coord=[2,2], name='v3')
>>> g.add_edge(v1, v2)
Edge{[v1] -- [v2], cost=1.414}
>>> print(v1.isadjacent(v2))
True
>>> print(v1.isadjacent(v3))
False
Seealso:

adjacent

isneighbour(vertex: Vertex) → bool#

Test if a vertex is adjacent to this vertex

Parameters:

vertex (Vertex subclass) – vertex reference

Returns:

true if vertex is adjacent

Return type:

bool

For a directed graph this is true only if there is an edge from self to vertex.

isneighbour and isneighbor are aliases.

>>> from pgraph import UGraph
>>> g = UGraph()
>>> v1 = g.add_vertex(coord=[0,0], name='v1')
>>> v2 = g.add_vertex(coord=[1,1], name='v2')
>>> v3 = g.add_vertex(coord=[2,2], name='v3')
>>> g.add_edge(v1, v2)
Edge{[v1] -- [v2], cost=1.414}
>>> print(v1.isadjacent(v2))
True
>>> print(v1.isadjacent(v3))
False
Seealso:

adjacent

property label: int | None#

Number of the graph component that contains the vertex

Returns:

component number, counted from 0, or None if the vertex is not in a graph

Return type:

int or None

Assigned by the graph, which finds its components when this is read after the graph has changed, as it does for Graph.nc, Graph.component and Graph.samecomponent. The numbering is by the first vertex of each component, in the order the vertices were added. It is read-only.

Changed in version 1.0: Read-only. It was a plain attribute, but it is computed from the graph’s structure and meaningless to assign. Reading it finds the components; in 0.6.5 it was None until something else had.

Seealso:

Graph.nc Graph.component

property name: str | None#

Name of the vertex

Returns:

the name

Return type:

str or None

The name is the vertex’s key in its graph: g[name] and name in g look it up. A vertex that is not in a graph can be given any name, or none. For one that is in a graph:

  • assigning a new name updates the graph’s name table, so the vertex is then found under the new name and not the old

  • a name already used by another vertex in the graph raises ValueError and changes nothing

  • the name cannot be cleared

Changed in version 1.0: Renaming a vertex in a graph used to leave the graph’s name table stale, so lookups by the new name failed.

Seealso:

Graph.add_vertex

neighbors() → list[Vertex]#

Vertices adjacent to this vertex

Returns:

the vertices at the far end of this vertex’s edges

Return type:

list of Vertex subclass

v.adjacent() is a list of the vertices that this vertex is joined to by an edge. “Adjacent” is the graph-theory term, and it is the relation that Graph.adjacency tabulates: row i of the adjacency matrix is non-zero exactly at the columns of the vertices returned by g[i].adjacent().

Note

  • For a directed graph these are the vertices at the head of the edges leaving this vertex, the successors.

  • There is one entry per edge, so a vertex joined by k parallel edges appears k times. In an undirected graph a self-loop lists the vertex itself twice, once for each end.

  • neighbours and neighbors are aliases, the same method under the British and American spellings, and are not deprecated.

>>> from pgraph import UGraph
>>> g = UGraph()
>>> v1 = g.add_vertex(coord=[0,0], name='v1')
>>> v2 = g.add_vertex(coord=[1,1], name='v2')
>>> v3 = g.add_vertex(coord=[2,2], name='v3')
>>> g.add_edge(v1, v2)
Edge{[v1] -- [v2], cost=1.414}
>>> g.add_edge(v1, v3)
Edge{[v1] -- [v3], cost=2.828}
>>> print(v1.adjacent())
[Vertex[v2, coord=(1, 1)], Vertex[v3, coord=(2, 2)]]
Seealso:

isadjacent successors predecessors incidences out_edges edges Graph.adjacency

neighbours() → list[Vertex]#

Vertices adjacent to this vertex

Returns:

the vertices at the far end of this vertex’s edges

Return type:

list of Vertex subclass

v.adjacent() is a list of the vertices that this vertex is joined to by an edge. “Adjacent” is the graph-theory term, and it is the relation that Graph.adjacency tabulates: row i of the adjacency matrix is non-zero exactly at the columns of the vertices returned by g[i].adjacent().

Note

  • For a directed graph these are the vertices at the head of the edges leaving this vertex, the successors.

  • There is one entry per edge, so a vertex joined by k parallel edges appears k times. In an undirected graph a self-loop lists the vertex itself twice, once for each end.

  • neighbours and neighbors are aliases, the same method under the British and American spellings, and are not deprecated.

>>> from pgraph import UGraph
>>> g = UGraph()
>>> v1 = g.add_vertex(coord=[0,0], name='v1')
>>> v2 = g.add_vertex(coord=[1,1], name='v2')
>>> v3 = g.add_vertex(coord=[2,2], name='v3')
>>> g.add_edge(v1, v2)
Edge{[v1] -- [v2], cost=1.414}
>>> g.add_edge(v1, v3)
Edge{[v1] -- [v3], cost=2.828}
>>> print(v1.adjacent())
[Vertex[v2, coord=(1, 1)], Vertex[v3, coord=(2, 2)]]
Seealso:

isadjacent successors predecessors incidences out_edges edges Graph.adjacency

property out_degree: int#

Number of edges leaving the vertex

Returns:

out-degree of the vertex

Return type:

int

For an undirected graph every incident edge both leaves and enters, so this equals degree.

Seealso:

in_degree degree out_edges

out_edges() → list[Edge]#

The edges leaving the vertex

Returns:

the outgoing edges, in the order they were connected

Return type:

list of Edge

This is a new list, and is the same as edges: for an undirected graph every incident edge is outgoing.

Seealso:

in_edges edges adjacent successors incidences edges_to out_degree

predecessors() → list[Vertex]#

Vertices that have an edge to this vertex

Returns:

the vertices at the tail of the incoming edges

Return type:

list of Vertex subclass

There is one entry per edge, so a vertex joined by k parallel edges appears k times. For an undirected graph this is adjacent.

>>> from pgraph import DGraph
>>> g = DGraph()
>>> v1 = g.add_vertex(coord=[0,0], name='v1')
>>> v2 = g.add_vertex(coord=[1,1], name='v2')
>>> v3 = g.add_vertex(coord=[2,2], name='v3')
>>> g.add_edge(v1, v3)
Edge{[v1] -> [v3], cost=2.828}
>>> g.add_edge(v2, v3)
Edge{[v2] -> [v3], cost=1.414}
>>> print(v3.predecessors())
[Vertex[v1, coord=(0, 0)], Vertex[v2, coord=(1, 1)]]
Seealso:

successors adjacent in_edges in_degree

remove() → None#

Remove this vertex, and all its edges, from its graph

Raises:

ValueError – the vertex is not connected to a graph

v.remove() removes v, and every edge touching it (incoming or outgoing), from its graph. The Vertex object itself is not deleted.

Note

This is a thin convenience wrapper around Graph.remove_vertex.

Return type:

None

>>> from pgraph import UGraph
>>> g = UGraph()
>>> v1 = g.add_vertex(coord=[0,0], name='v1')
>>> v2 = g.add_vertex(coord=[1,1], name='v2')
>>> g.add_edge(v1, v2)
Edge{[v1] -- [v2], cost=1.414}
>>> v2.remove()
>>> print(g)
UGraph: 1 vertex, 0 edges, 1 component
Seealso:

Graph.remove_vertex Edge.remove

successors() → list[Vertex]#

Vertices that this vertex has an edge to

Returns:

the vertices at the head of the outgoing edges

Return type:

list of Vertex subclass

This is adjacent, under its directed-graph name.

Seealso:

predecessors adjacent incidences out_edges

property x: float#

The x-coordinate of an embedded vertex

Raises:

ValueError – the vertex has no coordinate

Returns:

The x-coordinate

Return type:

float

>>> from pgraph import Vertex
>>> v = Vertex(coord=[1,2], name='v1')
>>> print(v.x)
1
property y: float#

The y-coordinate of an embedded vertex

Raises:

ValueError – the vertex has no coordinate

Returns:

The y-coordinate

Return type:

float

>>> from pgraph import Vertex
>>> v = Vertex(coord=[1,2], name='v1')
>>> print(v.y)
2
property z: float#

The z-coordinate of an embedded vertex

Raises:

ValueError – the vertex has no coordinate

Returns:

The z-coordinate

Return type:

float

>>> from pgraph import Vertex
>>> v = Vertex(coord=[1,2,3], name='v1')
>>> print(v.z)
3
class Observation(camera: ViewPoint, landmark: Landmark, uv: ndarray)[source][source]#

Create new landmark observation

Parameters:

  • camera (ViewPoint) – the camera that made the observation

  • landmark (Landmark) – the observed landmark

  • uv (ndarray(2)) – the image plane coordinates of the observed landmark

Represent the observation of a point by a camera in the bundle adjustment problem.

Seealso:

pgraph.Edge

property p: ndarray[source]#

Get image plane projection

Returns:

observed projection of landmark on image plane

Return type:

ndarray(2)

connect(v1: Vertex, v2: Vertex) → None#

Attach this edge to a pair of vertices

Parameters:

  • v1 (Vertex subclass) – start of the edge

  • v2 (Vertex subclass) – end of the edge

Raises:

  • ValueError – either vertex has not been added to a graph, or the vertices belong to different graphs

  • TypeError – this edge is not an instance of the graph’s Graph.edge_class

The edge connects vertices v1 and v2, and is added to the graph that those vertices belong to.

Warning

Intended for an edge that is not yet part of a graph. The edge’s v1 and v2 are overwritten without checking, so connecting an edge that is already in a graph leaves it referenced from its old vertices as well.

>>> from pgraph import Vertex, Edge, UGraph
>>> g = UGraph()
>>> v1 = g.add_vertex(coord=[0,0], name='v1')
>>> v2 = g.add_vertex(coord=[1,1], name='v2')
>>> e = Edge(cost=1.414)
>>> e.connect(v1, v2)
>>> print(e)
Edge{[v1] -- [v2], cost=1.414}

Note

The vertices must already be added to the graph.

Seealso:

Vertex.connect

property endpoints: list[Vertex]#

The two vertices of this edge

Returns:

start and end vertex

Return type:

list of Vertex subclass

>>> from pgraph import Vertex, Edge
>>> v1 = Vertex(coord=[1,2], name="A")
>>> v2 = Vertex(coord=[3,4], name="B")
>>> e = Edge(v1, v2, cost=5.0, data="A to B")
>>> print(e)
Edge{[A] -- [B], cost=5} data=A to B
>>> print(e.endpoints)
[Vertex[A, coord=(1, 2)], Vertex[B, coord=(3, 4)]]
Seealso:

vertices

next(vertex: Vertex) → Vertex#

Return other end of an edge

Parameters:

vertex (Vertex subclass) – one vertex on the edge

Raises:

ValueError – vertex is not on the edge

Returns:

the other vertex on the edge

Return type:

Vertex subclass

e.next(v1) is the vertex at the other end of edge e, ie. the vertex that is not v1.

>>> from pgraph import Vertex, Edge
>>> v1 = Vertex(coord=[1,2], name="A")
>>> v2 = Vertex(coord=[3,4], name="B")
>>> e = Edge(v1, v2, cost=5.0, data="A to B")
>>> print(e)
Edge{[A] -- [B], cost=5} data=A to B
>>> e.next(v1)
Vertex[B, coord=(3, 4)]
>>> e.next(v2)
Vertex[A, coord=(1, 2)]
remove() → None#

Remove this edge from its graph

Raises:

ValueError – the edge is not connected to a graph

e.remove() removes e from its graph’s own edge collection and from its connected vertices’ edge lists (both, for an undirected edge; the source only, for a directed one – see Graph.remove_edge), and clears e.v1/e.v2 to None. The Edge object itself is not deleted – it becomes an orphaned, disconnected shell, and calling remove() on it again raises ValueError.

Note

This is a thin convenience wrapper around Graph.remove_edge.

Return type:

None

>>> from pgraph import UGraph
>>> g = UGraph()
>>> v1 = g.add_vertex(coord=[0,0], name='v1')
>>> v2 = g.add_vertex(coord=[1,1], name='v2')
>>> e = g.add_edge(v1, v2)
>>> e.remove()
>>> print(g)
UGraph: 2 vertices, 0 edges, 2 components
Seealso:

Graph.remove_edge Vertex.remove

property v1: Vertex | None#

First vertex of the edge, the start vertex for a directed edge

Returns:

the vertex, or None if the edge is not connected

Return type:

Vertex subclass or None

Changed in version 1.0: Read-only. It was a plain attribute, so assigning to it on an edge that was in a graph left the graph inconsistent: the vertices’ edge lists no longer agreed with the edge, and the edge could not be removed. Give the vertices to the constructor, Edge(v1, v2), or to connect or Vertex.connect.

Seealso:

v2 connect

property v2: Vertex | None#

Second vertex of the edge, the end vertex for a directed edge

Returns:

the vertex, or None if the edge is not connected

Return type:

Vertex subclass or None

Read-only, see v1.

Seealso:

v1 connect

vertices() → list[Vertex]#

Vertices of an edge (deprecated)

Returns:

the two vertices of this edge

Return type:

list of Vertex subclass

Deprecated since version use: endpoints instead

On this page
Show Source