Construction and basic usage

There are a number of ways to build a UGraph (undirected) or DGraph (directed): a plain constructor, or from a dictionary or an adjacency matrix. Graph is their common base class, used in type hints, and Graph(directed=flag) chooses the kind from a value.

See Object lifecycle and graph-membership policy for the rules around constructing vertices/edges standalone, independent of a graph.

`Graph`	Base class for all graphs
`DGraph`	Class for directed graphs
`UGraph`	Class for undirected graphs
`Dict`	Create graph from parent/child dictionary
`Adjacency`	Create graph from adjacency matrix

class DGraph(*, metric=None, heuristic=None, verbose=False, dim=None, vertex_class=None, edge_class=None, directed=None)[source]

Bases: Graph

Class for directed graphs

Vertices are Vertex objects, or instances of the subclass given as vertex_class. Edges are Edge objects, or instances of the subclass given as edge_class; see Graph for the constructor arguments and the exceptions they raise.

An edge is recorded as leaving its start vertex and entering its end vertex, and an edge supplied to Vertex.connect() must run exactly from that vertex to the other.

Seealso:: Graph UGraph

class UGraph(*, metric=None, heuristic=None, verbose=False, dim=None, vertex_class=None, edge_class=None, directed=None)[source]

Bases: Graph

Class for undirected graphs

Vertices are Vertex objects, or instances of the subclass given as vertex_class. Edges are Edge objects, or instances of the subclass given as edge_class; see Graph for the constructor arguments and the exceptions they raise.

An edge is recorded at both of its vertices, so it is found from either end, and an edge supplied to Vertex.connect() may have its endpoints in either order.

Seealso:: Graph DGraph

class Adjacency(A, coords=None, names=None, **kwargs)

Bases:

Create graph from adjacency matrix

Parameters:

A (ndarray(N,N)) – adjacency matrix
coords (ndarray(N,M), optional) – coordinates of vertices, defaults to None
names (list(N) of str, optional) – names of vertices, defaults to None
kwargs (Any) – optional arguments passed to the graph constructor, for example vertex_class or edge_class

Raises:

ValueError – A is not square, or the length of names or the number of rows of coords does not match A
TypeError – vertex_class or edge_class is not a suitable class, see Graph

Returns:

graph

Return type:

UGraph or DGraph

Behaves like a constructor for a DGraph or UGraph creating the graph from an adjacency matrix A. Here non-zero elements A[i,j] correspond to edges from vertex i to vertex j.

A non-zero diagonal element A[i,i] is a self-loop on vertex i, for both kinds of graph.

Warning

For an undirected graph A should be symmetric but this is not checked. Only the upper triangular part, including the diagonal, is used. Elements are costs, not edge counts: a non-zero element is a single edge with that element as its cost, so parallel edges cannot be created this way.

>>> from pgraph import UGraph
>>> import numpy as np
>>> A = np.array([[0, 1, 0], [1, 0, 1], [0, 1, 0]])
>>> g = UGraph.Adjacency(A)
>>> print(g)
UGraph: 3 vertices, 2 edges, 1 component

Seealso:: Dict() adjacency()

class Dict(d, reverse=False, **kwargs)

Bases:

Create graph from parent/child dictionary

Parameters:

d (dict) – dictionary that maps from Vertex subclass to Vertex subclass
reverse (bool) – reverse link direction, defaults to False
kwargs (Any) – optional arguments passed to the graph constructor, for example vertex_class or edge_class

Raises:

TypeError – vertex_class or edge_class is not a suitable class, see Graph

Returns:

graph

Return type:

UGraph or DGraph

Behaves like a constructor for a DGraph or UGraph from a dictionary that maps vertices to parents. From this information it can create a graph that is a tree or forest.

By default parent vertices are linked their children. If reverse is True then children are linked to their parents.

>>> from pgraph import UGraph
>>> d = {'b': 'a', 'c': 'a', 'd': 'b'}
>>> g = UGraph.Dict(d)
>>> print(g)
UGraph: 4 vertices, 3 edges, 1 component

Seealso:: Adjacency()

Inherited methods for all graph types

class Graph(*, metric=None, heuristic=None, verbose=False, dim=None, vertex_class=None, edge_class=None, directed=None)[source]

Base class for all graphs

A graph is a set of Vertex objects joined by Edge objects, which are directed or not according to the kind of graph: UGraph is undirected and DGraph is directed. This class holds everything they share, and Graph(directed=flag) makes one or the other. The constructor arguments are described below.

Seealso:: UGraph DGraph Vertex Edge

__contains__(item)[source]

Test if vertex in graph

Parameters:: item (Vertex subclass or str) – vertex or name of vertex
Returns:: true if vertex exists in the graph
Return type:: bool

'name' in graph is true if a vertex named 'name' exists in the graph.
v in graph is true if the vertex reference v exists in the graph.

__getitem__(i)[source]

Get vertex (base class method)

Parameters:

i (int, str or Vertex subclass) – vertex description

Raises:

IndexError – i is an integer outside the range of vertices
KeyError – i is a name that is not in the graph
TypeError – i is none of the types above

Returns:

the referenced vertex

Return type:

Vertex subclass

Retrieve a vertex by index or name:

g[i] is the i’th vertex in the graph. This reflects the order of addition to the graph. i can be any integer, including a NumPy integer such as the result of np.argmin(), and a negative i counts from the last vertex.
g[s] is vertex named s
g[v] is v where v is a Vertex subclass

This method also supports iteration over the vertices in a graph:

for v in g:
    print(v)

will iterate over all the vertices.

__init__(*, metric=None, heuristic=None, verbose=False, dim=None, vertex_class=None, edge_class=None, directed=None)[source]

Graph, undirected or directed

Parameters:

metric (callable or str, optional) – distance metric, defaults to “L2”
heuristic (callable or str, optional) – heuristic distance metric for A*, defaults to the same as metric
verbose (bool) – print diagnostic information as vertices/edges are added, defaults to False
dim (int, optional) – required length of every vertex’s coord, defaults to None (unconstrained – vertices may have coordinates of any length, or none at all)
vertex_class (subclass of Vertex, optional) – class of the vertices this graph creates, defaults to Vertex
edge_class (subclass of Edge, optional) – class of the edges this graph creates, defaults to Edge
directed (bool, optional) – whether the edges are directed, defaults to False for Graph and is fixed by the class for UGraph and DGraph

Raises:

ValueError – dim is given but is not a positive integer
ValueError – directed contradicts the class, for example UGraph(directed=True)
TypeError – vertex_class is not a subclass of Vertex, or edge_class is not a subclass of Edge

Graph(directed=True) is a DGraph and Graph() a UGraph, so the kind can be chosen by a variable:

g = Graph(directed=is_directed)

UGraph and DGraph remain, and are what isinstance and the documentation refer to. Everything else, the vertices included, is the same for both kinds, so there is one vertex class, Vertex. A vertex has no direction of its own; the graph it belongs to decides how an edge is recorded at its ends.

All arguments are keyword-only, so UGraph(dim=6) is correct and UGraph(6) raises TypeError.

Changed in version 1.0: Arguments are keyword-only. In 0.6.5 the first positional argument was accepted and ignored, so UGraph(6) silently did nothing.

vertex_class and edge_class let user subclasses be built by the graph, so they never need to be constructed by hand:

g = UGraph(vertex_class=MyVertex, edge_class=MyEdge)
v = g.add_vertex([0, 0])  # a MyVertex
e = g.add_edge(v, w)      # a MyEdge

The classes are called as vertex_class(coord, name=name) and edge_class(v1, v2, cost=cost, data=data), so a subclass that overrides __init__ must accept and pass on those arguments. A graph given a vertex_class only accepts vertices of that class in add_vertex(), and one given an edge_class only accepts edges of that class.

Seealso:: UGraph DGraph add_vertex() add_edge() vertex_class edge_class

__iter__()[source]

Iterate over the vertices of the graph

Returns:: iterator over vertices, in order of addition
Return type:: iterator of Vertex subclass

>>> 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')
>>> for v in g:
...     print(v)
[v1]
[v2]
[v3]

Seealso:: __getitem__()

__repr__()[source]

Detailed representation of the graph, one line per vertex

Returns:: one line per vertex showing its name, coordinate and component
Return type:: str

>>> 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(v2, v3)
Edge{[v2] -- [v3], cost=1.414}
>>> repr(g)
'UGraph:\n  v1 at [0 0] component=0\n  v2 at [1 1] component=0\n  v3 at [2 2] component=0'

__str__()[source]

Human-readable summary of the graph

Returns:: one-line summary of vertex/edge/component counts
Return type:: str

Counts of 1,000 or more have thousands separators.

>>> 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(v2, v3)
Edge{[v2] -- [v3], cost=1.414}
>>> str(g)
'UGraph: 3 vertices, 2 edges, 1 component'

Seealso:: show()

copy()[source]

Deepcopy of graph

Returns:: deep copy
Return type:: Graph

The copy has its own vertices and edges, which keep their class, name, coordinate, cost and any attributes the user has added, and in the same order, so it can be modified without affecting the original.

A graph can also be pickled, and copied with copy.deepcopy(), which this method calls. Both work for a graph of any size. A vertex or an edge cannot be pickled or copied on its own, since it has no meaning apart from its graph: a TypeError is raised, and the graph should be copied instead.

Note

A metric or heuristic given by name ("L1", "L2", "SE2") is pickled by name, and an SE2Metric with its weight. A function you supply must be importable at module level to be pickled; a lambda or a function defined inside another function can be copied but not pickled.
Attributes that you add to vertices or edges must not refer to other vertices or edges of the graph, since those cannot be pickled on their own.
A pickle is not a long-term storage format. Use export() for that.

Changed in version 1.0: Pickling a graph works, and copying one no longer fails with a RecursionError for a graph with a path of about a hundred vertices.

Copies the graph, its vertices and edges, but not any external data that may be attached to them. The copy is a new graph of the same kind, with the same vertices and edges, but the vertices and edges are new objects.

>>> from pgraph import UGraph
>>> g = UGraph()
>>> v1 = g.add_vertex(coord=[0,0], name='v1')
>>> g2 = g.copy()
>>> g2 is g
False
>>> g2[0] is g[0]
False

Seealso:: vertex_copy() export()

property edge_class: type[Edge]

Class of the edges this graph creates

Returns:: edge class
Return type:: subclass of Edge

This is read-only. It is set by the edge_class argument of the graph constructor, see Graph, and is Edge if not given.

>>> from pgraph import UGraph, Edge
>>> class MyEdge(Edge):
...     pass
>>> g = UGraph(edge_class=MyEdge)
>>> print(g.edge_class.__name__)
MyEdge

Seealso:: add_edge() vertex_class

property heuristic: Callable[[ndarray[tuple[Any, ...], dtype[_ScalarT]]], float]

Get the heuristic distance metric for graph

Returns:: heuristic distance metric
Return type:: callable

This is a function of a single coordinate-difference vector (shape (n,)), returning a scalar distance.

property metric: Callable[[ndarray[tuple[Any, ...], dtype[_ScalarT]]], float]

Get the distance metric for graph

Returns:: distance metric
Return type:: callable

This is a function of a single coordinate-difference vector (shape (n,)), returning a scalar distance.

show()[source]

Print a summary of all vertices and edges to stdout

>>> 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}
>>> g.show()
vertices:
  [v1]
  [v2]
edges:
  Edge{[v1] -- [v2], cost=1.414}

Seealso:: __str__()
Return type:: None

property vertex_class: type[Vertex]

Class of the vertices this graph creates

Returns:: vertex class
Return type:: subclass of Vertex

This is read-only. It is set by the vertex_class argument of the graph constructor, see Graph, and is Vertex if not given.

>>> from pgraph import UGraph, Vertex
>>> class MyVertex(Vertex):
...     pass
>>> g = UGraph(vertex_class=MyVertex)
>>> print(g.vertex_class.__name__)
MyVertex

Seealso:: add_vertex() edge_class

classmethod vertex_copy(vertex)[source]

Copy a vertex for use in a new graph of this kind

Parameters:: vertex (Vertex subclass) – vertex to copy
Returns:: new, unconnected vertex with the same coordinate and name
Return type:: Vertex subclass

A vertex can only belong to a single graph, so this method is used to create a new vertex with the same name and coordinates for inclusion in a new graph. A vertex is the same for undirected and directed graphs.

>>> from pgraph import UGraph, DGraph
>>> g = UGraph()
>>> v = g.add_vertex(coord=[1,2], name='v1')
>>> newv = DGraph.vertex_copy(v)
>>> print(newv)
[v1]

Seealso:: Vertex.copy()

Copying a vertex

Vertex.copy(cls=None)[source]

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

Distance metrics

The cost of an edge, the nearest vertex to a point and the heuristic of the A* planner all come from a distance metric, a function of the difference between two coordinates. It is chosen by name, "L2" (the default, Euclidean), "L1" (Manhattan) or "SE2", or you can supply your own function; see metric and heuristic.

The "SE2" metric is for poses \((x, y, \theta)\) and adds a position in metres to an angle in radians, which are not the same kind of quantity. It counts a radian as a metre. If a turn should count for more or less, use SE2Metric with a weight, which is the length that a radian is worth. Below, one vertex is 2 m ahead and facing the same way, and another is at our position but turned through 1.5 radians. With a weight of 1 the turn costs 1.5, so the turned vertex is the nearer; with a weight of 2 it costs 3, and the vertex ahead is nearer

>>> from pgraph import UGraph, SE2Metric
>>> for weight in (1.0, 2.0):
...     g = UGraph(dim=3, metric=SE2Metric(weight=weight))
...     v = g.add_vertex([2, 0, 0], name="ahead")
...     v = g.add_vertex([0, 0, 1.5], name="turned")
...     vertex, distance = g.closest([0, 0, 0])
...     print(weight, vertex.name, distance)
1.0 turned 1.5
2.0 ahead 2.0

class SE2Metric(weight=1.0)[source]

Distance between planar poses, a weighted mixed norm

Parameters:: weight (float) – length that one radian of turn counts for, defaults to 1
Raises:: ValueError – weight is negative or not finite

The metric of a vector \((x, y, \theta)\), the difference between two poses, is

\[d = \sqrt{x^2 + y^2 + (w \bar{\theta})^2}\]

where \(\bar{\theta}\) is \(\theta\) wrapped to the interval \([-\pi, \pi)\) and \(w\) is the weight.

Distance and angle have different units, so their relative importance is a choice. The weight is the conversion: it is how much length a turn of one radian is worth, so a turn of \(\theta\) costs as much as moving \(w \theta\). A weight of 1 treats a radian as a metre, which is what the string "SE2" means. A characteristic length of the vehicle, such as its turning radius, is a natural choice. With a weight of 0 the orientation is ignored and this is the distance in the plane.

An instance is a metric for a graph, and can be used as its heuristic too:

g = UGraph(dim=3, metric=SE2Metric(weight=0.5))

>>> from pgraph import SE2Metric
>>> import numpy as np
>>> v = np.r_[3, 4, np.pi / 2]   # 3 east, 4 north, a quarter turn
>>> SE2Metric()(v)
5.240935136048942
>>> SE2Metric(weight=0.5)(v)
5.06130914636402
>>> SE2Metric(weight=0)(v)
5.0

A metric with a weight is still a metric, so it is a consistent heuristic for A* when the edge costs are computed with it. If edge costs come from somewhere else, use a weight low enough, or zero, for the heuristic never to exceed the cost to go.

Seealso:: Graph.metric() Graph.heuristic()