Simple graph functionality for Python.

# PGraph: simple graphs for Python

This Python package allows the manipulation of directed and non-directed graphs. Also supports embedded graphs. It is suitable for graphs with thousands of nodes.

from pgraph import *
import json

with open('places.json', 'r') as f:
with open('routes.json', 'r') as f:

# build the graph
g = UGraph()

for name, info in places.items():

for route in routes:

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


### 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(v) the component that vertex v belongs to

• g.path_BFS() breadth-first search

• g.path_Astar() A* search

• g.adjacency() adjacency matrix

• g.Laplacian() Laplacian matrix

• g.incidence() incidence matrix

### Properties and methods of a vertex

Vertices belong to the class UVertex (for undirected graphs) or DVertex (for directed graphs), which are each subclasses of Vertex.

• v.coord the coordinate vector for embedded graph (optional)
• v.name the name of the vertex (optional)
• v.neighbours() is a list of the neighbouring vertices
• v1.samecomponent(v2) predicate for vertices belonging to the same component

Vertices can be named and referenced by name.

### Properties and methods of an edge

Edges are instances of the class Edge. Edges are not referenced by the graph object, each edge references a pair of vertices, and the vertices reference the edges. For a directed graph only the start vertex of an edge references the edge object, whereas for an undirected graph both vertices reference the edge object.

• 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(v) remove vertex v
• e.remove() remove edge e

## Subclasing pgraph classes

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

• Have it subclass either DVertex or UVertex depending on graph type
• Then place instances of Foo into the graph using add_vertex and create edges as required
class Foo(UVertex):
# foo stuff goes here

f1 = Foo(...)
f2 = Foo(...)

g = UGraph() # create a new undirected graph

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


## Under the hood

The key objects and their interactions are shown below.

## MATLAB version

This is a re-engineered version of PGraph.m which ships as part of the Spatial Math Toolbox for MATLAB. This class is 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.

## Project details

Uploaded source