Mathematical graphs for Python.
Project description
PGraph: graphs for 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
- 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 asfor 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 vertexv
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 verticesv1.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 methodse.next(v)
vertex on edgee
that is notv
e.v1
,e.v2
the two vertices that define the edgee
Modifying a graph
g.remove(v)
remove vertexv
e.remove()
remove edgee
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
orUVertex
depending on graph type - Then place instances of
Foo
into the graph usingadd_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 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
Built Distribution
Hashes for pgraph_python-0.6.2-py3-none-any.whl
Algorithm | Hash digest | |
---|---|---|
SHA256 | 0f97585df83c3a2acaaa721970733b11f0fd35319f4a66464066b198ca86fc0c |
|
MD5 | c7a61a6503773284d5d96df73b971a2b |
|
BLAKE2b-256 | 01c831da9453017aa085d228b483439842d7d262760fdc183aeaf9b453a4bddc |