PGraph: graphs for Python

Graphs for Python

GitHub • Wiki • Changelog

Status & Project Health

Ecosystem & Dependencies

This pure-Python package provides classes for directed and undirected graphs: vertices connected by edges, with edge costs and path planning. Self-loops and parallel edges are permitted. Performance is good enough to support bundle adjustment, pose-graph SLAM and path planning over thousands of vertices.

Vertices can optionally be embedded: given a coordinate in a space of any dimension. Edge costs are then computed from the vertex positions using a distance metric (Euclidean, Manhattan, SE(2), or your own), the vertex nearest a point can be found, A* uses the metric as its heuristic, and the graph can be plotted, or exported with its layout preserved.

Installation

pip install pgraph-python

This needs Python 3.9 or later. The dependencies, NumPy, Matplotlib and Spatial Maths, are installed with it.

Examples

A small example: routing through towns in Queensland

from pgraph import UGraph
import json

# load the places and routes
with open('queensland.json', 'r') as f:
    data = json.load(f)

# build the graph
g = UGraph()
for name, info in data['places'].items():
    g.add_vertex(name=name, coord=info['utm'])
for route in data['routes']:
    g.add_edge(route['start'], route['end'], cost=route['distance'])

# plan a path from Hughenden to Brisbane
p, length, _ = g.path_Astar('Hughenden', 'Brisbane')
g.plot(block=False)  # plot it
g.highlight_path(p)  # overlay the path

The data file and the complete example are in the notebook examples/roads.ipynb.

A bigger example: routing through central London

A directed graph of the road network of central London, taken from OpenStreetMap, and the shortest drive between Buckingham Palace and Tower Bridge, there (solid) and back (dashed). The two routes differ in length, 5,515 m and 5,948 m, because of the one-way streets. The notebook examples/london.ipynb builds the graph from the map data, keeps the part of it that can be driven around in, and plans with A*. This graph has over 4,000 vertices.

Map data © OpenStreetMap contributors, available under the Open Database License.

Using pgraph

Full details are given in the online documentation. For an AI assistant there is a short summary, llms.txt, and the complete documentation as one file, llms-full.txt.

Properties and methods of the graph

Graphs belong to the class UGraph or DGraph for undirected or directed graphs respectively. The graph is essentially a container for the vertices.

• g.add_vertex() add a vertex

• g.n the number of vertices

• g is an iterator over vertices, can be used as for vertex in g:

• g[i] reference a vertex by its index or name

  ---

• g.add_edge() connect two vertices

• g.edges() all edges in the graph

• g.plot() plots the vertices and edges

• g.nc the number of graph components, 1 if fully connected

• g.component(c) the vertices in component number c, numbered from 0

• g.samecomponent(v1, v2) predicate for vertices belonging to the same component

  ---

• g.path_BFS() breadth-first search, the path with the fewest edges

• g.path_UCS() uniform-cost search, the cheapest path

• g.path_Astar() A* search, the cheapest path using a heuristic

  ---

• g.closest(point) the vertex nearest to a point

• g.near(point, radius) the vertices within a distance of a point

• g.within(box) the vertices inside a box

• g.subgraph(vertices) the part of the graph that those vertices induce, as a new graph

• g.coordinates() the vertex coordinates as a matrix, a column per vertex

• g.build_kdtree() an optional spatial index (needs scipy) that makes closest and near faster on a large graph

• g.metric the distance metric: "L2" (the default), "L1", "SE2", SE2Metric(weight) that weights the angle of a pose, or a function of your own

  ---

• g.adjacency() adjacency matrix

• g.laplacian() Laplacian matrix

• g.incidence() incidence matrix

  ---

• g.copy() a deep copy; a graph can also be pickled

• g.export() write the graph as GraphViz DOT, Mermaid, GraphML, ELK, or an image (which needs GraphViz)

• g.validate() check that the graph's records agree with each other

Properties and methods of a vertex

Vertices are instances of the class Vertex, for both undirected and directed graphs.

• v.coord the coordinate vector for embedded graph (optional)
• v.name the name of the vertex (optional)
• v.label the number of the component that the vertex belongs to
• v.adjacent() is a list of the adjacent vertices (neighbours() and neighbors() are the same)

Vertices can be named and referenced by name.

Properties and methods of an edge

Edges are instances of the class Edge. Each edge references a pair of vertices, the graph lists all of its edges in g.edges(), and the vertices reference the edges.

• e.cost cost of edge for planning methods
• e.next(v) vertex on edge e that is not v
• e.v1, e.v2 the two vertices that define the edge e

Modifying a graph

• g.remove_vertex(v) or v.remove() remove vertex v
• g.remove_edge(e) or e.remove() remove edge e

Subclassing pgraph classes

Consider a user class Foo that we would like to connect using a graph overlay, i.e. instances of Foo become vertices in a graph.

• Have it subclass Vertex
• Then place instances of Foo into the graph using add_vertex and create edges as required

from pgraph import UGraph, Vertex

class Foo(Vertex):
    # foo stuff goes here
    def say_hi(self):
        print(f"hi from {self.name}")

f1 = Foo(name="f1")
f2 = Foo(name="f2")

g = UGraph() # create a new undirected graph
g.add_vertex(f1)
g.add_vertex(f2)

f1.connect(f2, cost=3)
for f in f1.adjacent():
    f.say_hi()  # say hi to the neighbours

Or tell the graph which classes to make, with UGraph(vertex_class=Foo, edge_class=Bar), and g.add_vertex() and g.add_edge() create instances of them, so they never need to be constructed by hand.

Performance

Timings of the key operations on random geometric graphs, each vertex joined to its 4 nearest neighbours, of 100, 1,000 and 10,000 vertices, measured with examples/benchmark.py on an Apple M4 with Python 3.12 and NumPy 2.5. The path times are the median of 10 random start and goal pairs. The last column is the exponent b in time ∝ N^b between the smallest and the largest graph for the quantity shown, so 0 is constant, 1 is linear and 2 is quadratic. The adjacency, Laplacian and incidence matrices are dense, so they are only formed up to 1,000 vertices.

Undirected graphs

Directed graphs

History

This is a re-engineered version of PGraph.m which ships as part of the Spatial Math Toolbox for MATLAB. That class was used to support bundle adjustment, pose-graph SLAM and various planners such as PRM, RRT and Lattice.

The Python version was designed from the start to work with directed and undirected graphs, whereas directed graphs were a late addition to the MATLAB version. Semantics are similar but not identical. In particular the use of subclassing rather than references to user data is encouraged.