# PGraph: graphs for Python
[](https://github.com/petercorke/robotics-toolbox-python)
[](https://github.com/petercorke/spatialmath-python)
[](https://qcr.github.io)
[](https://pypi.python.org/pypi/pgraph-python/)
[](https://pypi.python.org/pypi/pgraph-python/)
[](https://github.com/petercorke/pgraph-python/blob/master/LICENSE)
[](https://github.com/petercorke/pgraph-python/actions?query=workflow%3Abuild)
[](https://codecov.io/gh/petercorke/pgraph-python)
- [GitHub repository](https://github.com/petercorke/pgraph-python)
- [Wiki (examples and details)](https://github.com/petercorke/pgraph-python/wiki)
- [Documentation](https://petercorke.github.io/pgraph-python)
- [Changelog](https://github.com/petercorke/pgraph-python/blob/master/CHANGELOG.md)
- Dependencies: [`numpy`](https://numpy.org) [`spatialmath`](https://github.com/bdaiinstitute/spatialmath-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
# 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.
## MATLAB version
This is a re-engineered version of [PGraph.m](https://github.com/petercorke/spatialmath-matlab/blob/master/PGraph.m) which ships as part of the [Spatial Math Toolbox for MATLAB](https://github.com/petercorke/spatialmath-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.
Raw data
{
"_id": null,
"home_page": null,
"name": "pgraph-python",
"maintainer": null,
"docs_url": null,
"requires_python": ">=3.7",
"maintainer_email": null,
"keywords": "python, graph, directed graph, undirected graph, a* search, adjacency matrix, Laplacian matrix, plotting, optimal path",
"author": null,
"author_email": "Peter Corke <rvc@petercorke.com>",
"download_url": "https://files.pythonhosted.org/packages/63/7f/89b04d2bfbb0e46a08a93c51b63d96a7be32d0b861021e9db533762ba356/pgraph_python-0.6.3.tar.gz",
"platform": null,
"description": "# PGraph: graphs for Python\n\n[](https://github.com/petercorke/robotics-toolbox-python)\n[](https://github.com/petercorke/spatialmath-python)\n[](https://qcr.github.io)\n\n[](https://pypi.python.org/pypi/pgraph-python/)\n[](https://pypi.python.org/pypi/pgraph-python/)\n[](https://github.com/petercorke/pgraph-python/blob/master/LICENSE)\n\n[](https://github.com/petercorke/pgraph-python/actions?query=workflow%3Abuild)\n[](https://codecov.io/gh/petercorke/pgraph-python)\n\n\n- [GitHub repository](https://github.com/petercorke/pgraph-python)\n- [Wiki (examples and details)](https://github.com/petercorke/pgraph-python/wiki)\n- [Documentation](https://petercorke.github.io/pgraph-python)\n- [Changelog](https://github.com/petercorke/pgraph-python/blob/master/CHANGELOG.md)\n- Dependencies: [`numpy`](https://numpy.org) [`spatialmath`](https://github.com/bdaiinstitute/spatialmath-python)\n\n\nThis Python package allows the manipulation of directed and non-directed graphs. Also supports embedded graphs. It is suitable for graphs with thousands of nodes.\n\n\n\n```\nfrom pgraph import *\nimport json\n\n# load places and routes\nwith open('places.json', 'r') as f:\n places = json.loads(f.read())\nwith open('routes.json', 'r') as f:\n routes = json.loads(f.read())\n\n# build the graph\ng = UGraph()\n\nfor name, info in places.items():\n g.add_vertex(name=name, coord=info[\"utm\"])\n\nfor route in routes:\n g.add_edge(route[0], route[1], cost=route[2])\n\n# plan a path from Hughenden to Brisbane\np = g.path_Astar('Hughenden', 'Brisbane')\ng.plot(block=False) # plot it\ng.highlight_path(p) # overlay the path\n```\n\n### Properties and methods of the graph\nGraphs belong to the class `UGraph` or `DGraph` for undirected or directed graphs respectively. The graph is essentially a container for the vertices.\n\n- `g.add_vertex()` add a vertex\n- `g.n` the number of vertices\n- `g` is an iterator over vertices, can be used as `for vertex in g:`\n- `g[i]` reference a vertex by its index or name\n\n ***\n- `g.add_edge()` connect two vertices\n- `g.edges()` all edges in the graph\n- `g.plot()` plots the vertices and edges\n- `g.nc` the number of graph components, 1 if fully connected\n- `g.component(v)` the component that vertex `v` belongs to\n\n ***\n- `g.path_BFS()` breadth-first search\n- `g.path_Astar()` A* search\n\n ***\n- `g.adjacency()` adjacency matrix\n- `g.Laplacian()` Laplacian matrix\n- `g.incidence()` incidence matrix\n\n### Properties and methods of a vertex\nVertices belong to the class `UVertex` (for undirected graphs) or `DVertex` (for directed graphs), which are each subclasses of `Vertex`.\n\n- `v.coord` the coordinate vector for embedded graph (optional)\n- `v.name` the name of the vertex (optional)\n- `v.neighbours()` is a list of the neighbouring vertices\n- `v1.samecomponent(v2)` predicate for vertices belonging to the same component\n\nVertices can be named and referenced by name.\n\n### Properties and methods of an edge\nEdges are instances of the class `Edge`.\nEdges 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.\n\n- `e.cost` cost of edge for planning methods\n- `e.next(v)` vertex on edge `e` that is not `v`\n- `e.v1`, `e.v2` the two vertices that define the edge `e`\n\n## Modifying a graph\n\n- `g.remove(v)` remove vertex `v`\n- `e.remove()` remove edge `e`\n\n## Subclasing pgraph classes\n\nConsider a user class `Foo` that we would like to connect using a graph _overlay_, ie.\ninstances of `Foo` becomes vertices in a graph.\n\n- Have it subclass either `DVertex` or `UVertex` depending on graph type\n- Then place instances of `Foo` into the graph using `add_vertex` and create edges as required\n\n```\nclass Foo(UVertex):\n # foo stuff goes here\n \nf1 = Foo(...)\nf2 = Foo(...)\n\ng = UGraph() # create a new undirected graph\ng.add_vertex(f1)\ng.add_vertex(f2)\n\nf1.connect(f2, cost=3)\nfor f in f1.neighbours():\n # say hi to the neighbours\n```\n\n## Under the hood\n\nThe key objects and their interactions are shown below.\n\n\n\n## MATLAB version\n\nThis is a re-engineered version of [PGraph.m](https://github.com/petercorke/spatialmath-matlab/blob/master/PGraph.m) which ships as part of the [Spatial Math Toolbox for MATLAB](https://github.com/petercorke/spatialmath-matlab). This class is used to support bundle adjustment, pose-graph SLAM and various planners such as PRM, RRT and Lattice.\n\nThe 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\n_user data_ is encouraged.\n\n\n\n\n\n",
"bugtrack_url": null,
"license": null,
"summary": "Mathematical graphs for Python",
"version": "0.6.3",
"project_urls": {
"Bug Tracker": "https://github.com/pypa/sampleproject/issues",
"Changelog": "https://github.com/petercorke/pgraph-python/blob/master/CHANGELOG.md",
"Coverage": "https://codecov.io/gh/petercorke/spatialmath-python",
"Documentation": "https://petercorke.github.io/pgraph-python",
"GitHub Source": "https://github.com/petercorke/pgraph-python",
"Homepage": "https://github.com/petercorke/pgraph-python"
},
"split_keywords": [
"python",
" graph",
" directed graph",
" undirected graph",
" a* search",
" adjacency matrix",
" laplacian matrix",
" plotting",
" optimal path"
],
"urls": [
{
"comment_text": "",
"digests": {
"blake2b_256": "a1a4b7c6b1971bdff95429a52e60ab04c21d9176307d36299a07d0076fa63b1b",
"md5": "2283d7de54b2abbe2c8a3b2bee6f42f1",
"sha256": "184d51b5acc595daceb92d9505d614ec9b72539d37e3162cbe6fc880d6d1d807"
},
"downloads": -1,
"filename": "pgraph_python-0.6.3-py3-none-any.whl",
"has_sig": false,
"md5_digest": "2283d7de54b2abbe2c8a3b2bee6f42f1",
"packagetype": "bdist_wheel",
"python_version": "py3",
"requires_python": ">=3.7",
"size": 17677,
"upload_time": "2025-01-08T03:39:34",
"upload_time_iso_8601": "2025-01-08T03:39:34.369850Z",
"url": "https://files.pythonhosted.org/packages/a1/a4/b7c6b1971bdff95429a52e60ab04c21d9176307d36299a07d0076fa63b1b/pgraph_python-0.6.3-py3-none-any.whl",
"yanked": false,
"yanked_reason": null
},
{
"comment_text": "",
"digests": {
"blake2b_256": "637f89b04d2bfbb0e46a08a93c51b63d96a7be32d0b861021e9db533762ba356",
"md5": "48b50e270c1b475eb6ba858fe7cbb50e",
"sha256": "ff41f718daf7ae925d36cd7d17f567b67479f115f073f497f985733ecbbc90b4"
},
"downloads": -1,
"filename": "pgraph_python-0.6.3.tar.gz",
"has_sig": false,
"md5_digest": "48b50e270c1b475eb6ba858fe7cbb50e",
"packagetype": "sdist",
"python_version": "source",
"requires_python": ">=3.7",
"size": 22619,
"upload_time": "2025-01-08T03:39:35",
"upload_time_iso_8601": "2025-01-08T03:39:35.968100Z",
"url": "https://files.pythonhosted.org/packages/63/7f/89b04d2bfbb0e46a08a93c51b63d96a7be32d0b861021e9db533762ba356/pgraph_python-0.6.3.tar.gz",
"yanked": false,
"yanked_reason": null
}
],
"upload_time": "2025-01-08 03:39:35",
"github": true,
"gitlab": false,
"bitbucket": false,
"codeberg": false,
"github_user": "pypa",
"github_project": "sampleproject",
"travis_ci": false,
"coveralls": false,
"github_actions": true,
"lcname": "pgraph-python"
}
JSON
