Skip to main content

Mathematical graphs for Python.

Project description

PGraph: graphs for Python

A Python Robotics Package QUT Centre for Robotics Open Source

PyPI version fury.io PyPI pyversions GitHub license

Build Status Coverage Language grade: Python pypi downloads

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.

road network

from pgraph import *
import json

# load places and routes
with open('places.json', 'r') as f:
    places = json.loads(f.read())
with open('routes.json', 'r') as f:
    routes = json.loads(f.read())

# build the graph
g = UGraph()

for name, info in places.items():
    g.add_vertex(name=name, coord=info["utm"])

for route in routes:
    g.add_edge(route[0], route[1], cost=route[2])

# 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
g.add_vertex(f1)
g.add_vertex(f2)

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.

data structures

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


Download files

Download the file for your platform. If you're not sure which to choose, learn more about installing packages.

Source Distribution

pgraph-python-0.6.2.tar.gz (61.2 kB view details)

Uploaded Source

Built Distribution

pgraph_python-0.6.2-py3-none-any.whl (20.3 kB view details)

Uploaded Python 3

File details

Details for the file pgraph-python-0.6.2.tar.gz.

File metadata

  • Download URL: pgraph-python-0.6.2.tar.gz
  • Upload date:
  • Size: 61.2 kB
  • Tags: Source
  • Uploaded using Trusted Publishing? No
  • Uploaded via: twine/3.2.0 pkginfo/1.5.0.1 requests/2.25.1 setuptools/65.4.1 requests-toolbelt/0.9.1 tqdm/4.49.0 CPython/3.8.5

File hashes

Hashes for pgraph-python-0.6.2.tar.gz
Algorithm Hash digest
SHA256 4abad7ded90677e4d1fc8317de298c7068942f8b289ec9a58bf3d36d666e70cf
MD5 2991598095c443110f87a6396b097498
BLAKE2b-256 9d8541d56023382e8a64319a42c762ff3ae189b4d500a0f41457a40bc2f5e575

See more details on using hashes here.

File details

Details for the file pgraph_python-0.6.2-py3-none-any.whl.

File metadata

  • Download URL: pgraph_python-0.6.2-py3-none-any.whl
  • Upload date:
  • Size: 20.3 kB
  • Tags: Python 3
  • Uploaded using Trusted Publishing? No
  • Uploaded via: twine/3.2.0 pkginfo/1.5.0.1 requests/2.25.1 setuptools/65.4.1 requests-toolbelt/0.9.1 tqdm/4.49.0 CPython/3.8.5

File hashes

Hashes for pgraph_python-0.6.2-py3-none-any.whl
Algorithm Hash digest
SHA256 0f97585df83c3a2acaaa721970733b11f0fd35319f4a66464066b198ca86fc0c
MD5 c7a61a6503773284d5d96df73b971a2b
BLAKE2b-256 01c831da9453017aa085d228b483439842d7d262760fdc183aeaf9b453a4bddc

See more details on using hashes here.

Supported by

AWS AWS Cloud computing and Security Sponsor Datadog Datadog Monitoring Fastly Fastly CDN Google Google Download Analytics Microsoft Microsoft PSF Sponsor Pingdom Pingdom Monitoring Sentry Sentry Error logging StatusPage StatusPage Status page