# PGraph: graphs for Python
[](https://github.com/petercorke/robotics-toolbox-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)
[](https://lgtm.com/projects/g/petercorke/pgraph-python/context:python)
- GitHub repository: [https://github.com/petercorke/pgraph-python](https://github.com/petercorke/pgraph-python)
- Wiki (examples and details) [https://github.com/petercorke/pgraph-python/wiki](https://github.com/petercorke/pgraph-python/wiki)
- Documentation: [https://petercorke.github.io/pgraph-python](https://petercorke.github.io/pgraph-python)
- Dependencies: `numpy`
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": "https://github.com/petercorke/pgraph-python",
"name": "pgraph-python",
"maintainer": "",
"docs_url": null,
"requires_python": ">=3.6",
"maintainer_email": "",
"keywords": "python graph directed-graph undirected-graph a*-search adjacency-matrix Laplacian-matrix plotting optimal-path",
"author": "Peter Corke",
"author_email": "rvc@petercorke.com",
"download_url": "https://files.pythonhosted.org/packages/9d/85/41d56023382e8a64319a42c762ff3ae189b4d500a0f41457a40bc2f5e575/pgraph-python-0.6.2.tar.gz",
"platform": null,
"description": "# PGraph: graphs for Python\n\n[](https://github.com/petercorke/robotics-toolbox-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[](https://lgtm.com/projects/g/petercorke/pgraph-python/context:python)\n\n\n- GitHub repository: [https://github.com/petercorke/pgraph-python](https://github.com/petercorke/pgraph-python)\n- Wiki (examples and details) [https://github.com/petercorke/pgraph-python/wiki](https://github.com/petercorke/pgraph-python/wiki)\n- Documentation: [https://petercorke.github.io/pgraph-python](https://petercorke.github.io/pgraph-python)\n- Dependencies: `numpy`\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": "MIT",
"summary": "Mathematical graphs for Python.",
"version": "0.6.2",
"split_keywords": [
"python",
"graph",
"directed-graph",
"undirected-graph",
"a*-search",
"adjacency-matrix",
"laplacian-matrix",
"plotting",
"optimal-path"
],
"urls": [
{
"comment_text": "",
"digests": {
"blake2b_256": "01c831da9453017aa085d228b483439842d7d262760fdc183aeaf9b453a4bddc",
"md5": "c7a61a6503773284d5d96df73b971a2b",
"sha256": "0f97585df83c3a2acaaa721970733b11f0fd35319f4a66464066b198ca86fc0c"
},
"downloads": -1,
"filename": "pgraph_python-0.6.2-py3-none-any.whl",
"has_sig": false,
"md5_digest": "c7a61a6503773284d5d96df73b971a2b",
"packagetype": "bdist_wheel",
"python_version": "py3",
"requires_python": ">=3.6",
"size": 20335,
"upload_time": "2023-01-15T05:55:04",
"upload_time_iso_8601": "2023-01-15T05:55:04.948945Z",
"url": "https://files.pythonhosted.org/packages/01/c8/31da9453017aa085d228b483439842d7d262760fdc183aeaf9b453a4bddc/pgraph_python-0.6.2-py3-none-any.whl",
"yanked": false,
"yanked_reason": null
},
{
"comment_text": "",
"digests": {
"blake2b_256": "9d8541d56023382e8a64319a42c762ff3ae189b4d500a0f41457a40bc2f5e575",
"md5": "2991598095c443110f87a6396b097498",
"sha256": "4abad7ded90677e4d1fc8317de298c7068942f8b289ec9a58bf3d36d666e70cf"
},
"downloads": -1,
"filename": "pgraph-python-0.6.2.tar.gz",
"has_sig": false,
"md5_digest": "2991598095c443110f87a6396b097498",
"packagetype": "sdist",
"python_version": "source",
"requires_python": ">=3.6",
"size": 61172,
"upload_time": "2023-01-15T05:55:06",
"upload_time_iso_8601": "2023-01-15T05:55:06.887535Z",
"url": "https://files.pythonhosted.org/packages/9d/85/41d56023382e8a64319a42c762ff3ae189b4d500a0f41457a40bc2f5e575/pgraph-python-0.6.2.tar.gz",
"yanked": false,
"yanked_reason": null
}
],
"upload_time": "2023-01-15 05:55:06",
"github": true,
"gitlab": false,
"bitbucket": false,
"github_user": "petercorke",
"github_project": "pgraph-python",
"travis_ci": false,
"coveralls": false,
"github_actions": true,
"lcname": "pgraph-python"
}
JSON
