PGraph module
- class PGraph.DGraph(arg=None, metric=None, heuristic=None, verbose=False)[source]
Bases:
PGraph
Class for directed graphs
- add_vertex(coord=None, name=None)[source]
Add vertex to directed graph
- Parameters:
coord (array-like, optional) – coordinate for an embedded graph, defaults to None
name (str, optional) – vertex name, defaults to “#i”
- Returns:
new vertex
- Return type:
g.add_vertex()
creates a new vertex with optionalcoord
andname
.g.add_vertex(v)
takes an instance or subclass of DVertex and adds it to the graph
- class PGraph.DVertex(coord=None, name=None)[source]
Bases:
Vertex
Vertex subclass for directed graphs
This class can be inherited to provide user objects with graph capability.
- connect(other, **kwargs)[source]
Connect two vertices with an edge
- Parameters:
dest (
Vertex
subclass) – The vertex to connect toedge (
Edge
subclass, optional) – Use this as the edge object, otherwise a newEdge
object is created from the vertices being connected, and thecost
andedge
parameters, defaults to Nonecost (float, optional) – the cost to traverse this edge, defaults to None
data (Any, optional) – reference to arbitrary data associated with the edge, defaults to None
- Raises:
TypeError – vertex types are different subclasses
- Returns:
the edge connecting the vertices
- Return type:
v1.connect(v2)
connects vertexv1
to vertexv2
.Note
If the vertices subclass
UVertex
the edge is undirected, and if they subclassDVertex
the edge is directed.Vertices must both be of the same
Vertex
subclass
- Seealso:
- class PGraph.Edge(v1=None, v2=None, cost=None, data=None)[source]
Bases:
object
Edge class
Is used to represent directed directed and undirected edges.
Each edge has: -
cost
cost of traversing this edge, required for planning methods -data
reference to arbitrary data associated with the edge -v1
first vertex, start vertex for a directed edge -v2
second vertex, end vertex for a directed edgeNote
An undirected graph is created by having a single edge object in the edgelist of _each_ vertex.
This class can be inherited to provide user objects with graph capability.
Inheritance is an alternative to providing arbitrary user data.
An Edge points to a pair of vertices. At
connect
time the vertices get references back to the Edge object.graph.add_edge(v1, v2)
callsv1.connect(v2)
- connect(v1, v2)[source]
Add edge to the graph
- Parameters:
v1 (Vertex subclass) – start of the edge
v2 (Vertex subclass) – end of the edge
The edge is added to the graph and connects vertices
v1
andv2
.Note
The vertices must already be added to the graph.
- property endpoints
- next(vertex)[source]
Return other end of an edge
- Parameters:
vertex (Vertex subclass) – one vertex on the edge
- Raises:
ValueError –
vertex
is not on the edge- Returns:
the other vertex on the edge
- Return type:
Vertex subclass
e.next(v1)
is the vertex at the other end of edgee
, ie. the vertex that is notv1
.
- class PGraph.PGraph(arg=None, metric=None, heuristic=None, verbose=False)[source]
Bases:
ABC
- classmethod Adjacency(A, coords=None, names=None)[source]
Create graph from adjacency matrix
- Parameters:
A (ndarray(N,N)) – adjacency matrix
coords (ndarray(N,M), optional) – coordinates of vertices, defaults to None
names (list(N) of str, optional) – names of vertices, defaults to None
- Returns:
[description]
- Return type:
[type]
Create a directed or undirected graph where non-zero elements
A[i,j]
correspond to edges from vertexi
to vertexj
.Warning
For undirected graph
A
should be symmetric but this is not checked. Only the upper triangular part is used.
- classmethod Dict(d, reverse=False)[source]
Create graph from parent/child dictionary
- Parameters:
d (dict) – dictionary that maps from
Vertex
subclass toVertex
subclassreverse (bool, optional) – reverse link direction, defaults to False
- Returns:
graph
- Return type:
Behaves like a constructor for a
DGraph
orUGraph
from a dictionary that maps vertices to parents. From this information it can create a tree graph.By default parent vertices are linked their children. If
reverse
is True then children are linked to their parents.
- Laplacian()[source]
Laplacian matrix for the graph
- Returns:
Laplacian matrix
- Return type:
NumPy ndarray
g.Laplacian()
is the Laplacian matrix (NxN) of the graph where N is the number of vertices.Note
Laplacian is always positive-semidefinite.
Laplacian has at least one zero eigenvalue.
- The number of zero-valued eigenvalues is the number of connected
components in the graph.
- Seealso:
- add_edge(v1, v2, **kwargs)[source]
Add an edge to the graph (superclass method)
- Parameters:
v1 (Vertex subclass) – first vertex (start if a directed graph)
v2 (Vertex subclass) – second vertex (end if a directed graph)
kwargs – optional arguments to pass to
Vertex.connect
- Returns:
edge
- Return type:
Create an edge between a vertex pair and adds it to the graph.
This is a graph centric way of creating an edge. The alternative is the
connect
method of a vertex.- Seealso:
- add_vertex(vertex, name=None)[source]
Add a vertex to the graph (superclass method)
- Parameters:
vertex (Vertex subclass) – vertex to add
name (str) – name of vertex
G.add_vertex(v)
add vertexv
to the graphG
.If the vertex has no name and
name
is None give it a default name#N
whereN
is a consecutive integer.The vertex is placed into a dictionary with a key equal to its name.
- adjacency()[source]
Adjacency matrix of graph
- Returns:
adjacency matrix
- Return type:
ndarray(N,N)
The elements of the adjacency matrix
[i,j]
are 1 if vertexi
is connected to vertexj
, else 0.Note
vertices are numbered in their order of creation. A vertex index can be resolved to a vertex reference by
graph[i]
.for an undirected graph the matrix is symmetric
Eigenvalues of
A
are real and are known as the spectrum of the graph.The element
A[i,j]
can be considered the number of walks of length one edge from vertexi
to vertexj
(either zero or one).If
Ak = A ** k
the elementAk[i,j]
is the number of walks of lengthk
from vertexi
to vertexj
.
- Seealso:
- average_degree()[source]
Average degree of the graph
- Returns:
average degree
- Return type:
float
Average degree is
for an undirected graph and for a directed graph where is the total number of edges and is the number of vertices.
- closest(coord)[source]
Vertex closest to point
- Parameters:
coord (ndarray(n)) – coordinates of a point
- Returns:
closest vertex
- Return type:
Vertex subclass
Returns the vertex closest to the given point. Distance is computed according to the graph’s metric.
- Seealso:
- component(c)[source]
All vertices in specified graph component
graph.component(c)
is a list of all vertices in graph componentc
.
- connectivity(vertices=None)[source]
Graph connectivity
- Returns:
a list with the number of edges per vertex
- Return type:
list
The average vertex connectivity is:
mean(g.connectivity())
and the minimum vertex connectivity is:
min(g.connectivity())
- degree()[source]
Degree matrix of graph
- Returns:
degree matrix
- Return type:
ndarray(N,N)
This is a diagonal matrix where element
[i,i]
is the number of edges connected to vertex idi
.- Seealso:
adjacency()
incidence()
laplacian()
- distance()[source]
Distance matrix of graph
- Returns:
distance matrix
- Return type:
ndarray(n,n)
The elements of the distance matrix
D[i,j]
is the edge cost of moving from vertexi
to vertexj
. It is zero if the vertices are not connected.
- dotfile(filename=None, direction=None)[source]
Export graph as a GraphViz dot file
- Parameters:
filename (str, optional) – filename to save graph to, defaults to None
g.dotfile()
creates the specified file which contains the GraphViz code to represent the embedded graph. By default output is to the console.Note
The graph is undirected if it is a subclass of
UGraph
The graph is directed if it is a subclass of
DGraph
Use
neato
rather than dot to get the embedded layout
Note
If
filename
is a file object then the file will not be closed after the GraphViz model is written.- Seealso:
- edges()[source]
Get all edges in graph (superclass method)
- Returns:
All edges in the graph
- Return type:
list of Edge references
We can iterate over all edges in the graph by:
for e in g.edges(): print(e)
Note
The
edges()
of a Vertex is a list of all edges connected to that vertex.- Seealso:
- property heuristic
Get the heuristic distance metric for graph
- Returns:
heuristic distance metric
- Return type:
callable
This is a function of a vector and returns a scalar.
- highlight_edge(edge, scale=2, color='r', alpha=0.5)[source]
Highlight an edge in the graph
- Parameters:
edge (Edge subclass) – The edge to highlight
scale (float, optional) – Overwrite with a line this much bigger than the original, defaults to 1.5
color (str, optional) – Overwrite with a line in this color, defaults to ‘r’
- highlight_path(path, block=False, **kwargs)[source]
Highlight a path through the graph
- Parameters:
path ([type]) – [description]
block (bool, optional) – [description], defaults to True
The vertices and edges along the path are overwritten with a different size/width and color.
- Seealso:
- highlight_vertex(vertex, scale=2, color='r', alpha=0.5)[source]
Highlight a vertex in the graph
- Parameters:
edge (Vertex subclass) – The vertex to highlight
scale (float, optional) – Overwrite with a line this much bigger than the original, defaults to 1.5
color (str, optional) – Overwrite with a line in this color, defaults to ‘r’
- incidence()[source]
Incidence matrix of graph
- Returns:
incidence matrix
- Return type:
ndarray(n,ne)
The elements of the incidence matrix
I[i,j]
are 1 if vertexi
is connected to edgej
, else 0.Note
vertices are numbered in their order of creation. A vertex index can be resolved to a vertex reference by
graph[i]
.edges are numbered in the order they appear in
graph.edges()
.
- Seealso:
- property metric
Get the distance metric for graph
- Returns:
distance metric
- Return type:
callable
This is a function of a vector and returns a scalar.
- property n
Number of vertices
- Returns:
Number of vertices
- Return type:
int
- property nc
Number of components
- Returns:
Number of components
- Return type:
int
Note
Components are labeled from 0 to
g.nc-1
.A graph coloring algorithm is run if the graph connectivity has changed.
Note
A lazy approach is used, and if a connectivity changing operation has been performed since the last call, the graph coloring algorithm is run which is potentially expensive for a large graph.
- property ne
Number of edges
- Returns:
Number of vertices
- Return type:
int
- path_Astar(S, G, verbose=False, summary=False)[source]
A* search for path
- Parameters:
S (Vertex subclass) – start vertex
G (Vertex subclass) – goal vertex
- Returns:
list of vertices from S to G inclusive, path length, tree
- Return type:
list of Vertex subclass, float, dict
Returns a list of vertices that form a path from vertex
S
to vertexG
if possible, otherwise return None.The search tree is returned as dict that maps a vertex to its parent.
The heuristic is the distance metric of the graph, which defaults to Euclidean distance.
- Seealso:
- path_BFS(S, G, verbose=False, summary=False)[source]
Breadth-first search for path
- Parameters:
S (Vertex subclass) – start vertex
G (Vertex subclass) – goal vertex
- Returns:
list of vertices from S to G inclusive, path length
- Return type:
list of Vertex subclass, float
Returns a list of vertices that form a path from vertex
S
to vertexG
if possible, otherwise return None.
- path_UCS(S, G, verbose=False, summary=False)[source]
Uniform cost search for path
- Parameters:
S (Vertex subclass) – start vertex
G (Vertex subclass) – goal vertex
- Returns:
list of vertices from S to G inclusive, path length, tree
- Return type:
list of Vertex subclass, float, dict
Returns a list of vertices that form a path from vertex
S
to vertexG
if possible, otherwise return None.The search tree is returned as dict that maps a vertex to its parent.
The heuristic is the distance metric of the graph, which defaults to Euclidean distance.
- plot(colorcomponents=True, force2d=False, vopt={}, eopt={}, text={}, block=False, grid=True, ax=None)[source]
Plot the graph
- Parameters:
vopt (dict, optional) – vertex format, defaults to 12pt o-marker
eopt (dict, optional) – edge format, defaults to None
text (False or dict, optional) – text label format, defaults to None
colorcomponents – color vertices and edges by component, defaults to None
block (bool, optional) – block until figure is dismissed, defaults to True
The graph is plotted using matplotlib.
If
colorcomponents
is True then each component is assigned a unique color.vertex
andedge
cannot include a color keyword.If
text
is a dict it is used to format text labels for the vertices which are the vertex names. Iftext
is None default formatting is used. Iftext
is False no labels are added.
- remove(x)[source]
Remove element from graph (superclass method)
- Parameters:
x (Edge or Vertex subclass) – element to remove from graph
- Raises:
TypeError – unknown type
The edge or vertex is removed, and all references and lists are updated.
Warning
The connectivity of the network may be changed.
- samecomponent(v1, v2)[source]
Test if vertices belong to same graph component
- Parameters:
v1 (Vertex subclass) – vertex
v2 (Vertex subclass) – vertex
- Returns:
true if vertices belong to same graph component
- Return type:
bool
Test whether vertices belong to the same component. For a:
directed graph this implies a path between them
undirected graph there is not necessarily a path between them
- class PGraph.UGraph(arg=None, metric=None, heuristic=None, verbose=False)[source]
Bases:
PGraph
Class for undirected graphs
- add_vertex(coord=None, name=None)[source]
Add vertex to undirected graph
- Parameters:
coord (array-like, optional) – coordinate for an embedded graph, defaults to None
name (str, optional) – vertex name, defaults to “#i”
- Returns:
new vertex
- Return type:
g.add_vertex()
creates a new vertex with optionalcoord
andname
.g.add_vertex(v)
takes an instance or subclass of UVertex and adds it to the graph
- class PGraph.UVertex(coord=None, name=None)[source]
Bases:
Vertex
Vertex subclass for undirected graphs
This class can be inherited to provide user objects with graph capability.
- connect(other, **kwargs)[source]
Connect two vertices with an edge
- Parameters:
dest (
Vertex
subclass) – The vertex to connect toedge (
Edge
subclass, optional) – Use this as the edge object, otherwise a newEdge
object is created from the vertices being connected, and thecost
andedge
parameters, defaults to Nonecost (float, optional) – the cost to traverse this edge, defaults to None
data (Any, optional) – reference to arbitrary data associated with the edge, defaults to None
- Raises:
TypeError – vertex types are different subclasses
- Returns:
the edge connecting the vertices
- Return type:
v1.connect(v2)
connects vertexv1
to vertexv2
.Note
If the vertices subclass
UVertex
the edge is undirected, and if they subclassDVertex
the edge is directed.Vertices must both be of the same
Vertex
subclass
- Seealso:
- class PGraph.Vertex(coord=None, name=None)[source]
Bases:
object
Superclass for vertices of directed and non-directed graphs.
- Each vertex has:
name
label
an int indicating which graph component contains it_edgelist
a list of edge objects that connect this vertex to otherscoord
the coordinate in an embedded graph (optional)
- connect(dest, edge=None, cost=None, data=None)[source]
Connect two vertices with an edge
- Parameters:
dest (
Vertex
subclass) – The vertex to connect toedge (
Edge
subclass, optional) – Use this as the edge object, otherwise a newEdge
object is created from the vertices being connected, and thecost
andedge
parameters, defaults to Nonecost (float, optional) – the cost to traverse this edge, defaults to None
data (Any, optional) – reference to arbitrary data associated with the edge, defaults to None
- Raises:
TypeError – vertex types are different subclasses
- Returns:
the edge connecting the vertices
- Return type:
v1.connect(v2)
connects vertexv1
to vertexv2
.Note
If the vertices subclass
UVertex
the edge is undirected, and if they subclassDVertex
the edge is directed.Vertices must both be of the same
Vertex
subclass
- Seealso:
- property degree
Degree of vertex
- Returns:
degree of the vertex
- Return type:
int
Returns the number of edges connected to the vertex.
Note
For a
DGraph
only outgoing edges are considered.- Seealso:
- distance(coord)[source]
Distance from vertex to point
- Parameters:
coord (ndarray(n) or Vertex) – coordinates of the point
- Returns:
distance
- Return type:
float
Distance is computed according to the graph’s metric.
- Seealso:
metric()
- edges()[source]
All outgoing edges of vertex
- Returns:
List of all edges leaving this vertex
- Return type:
list of Edge
Note
For a directed graph the edges are those leaving this vertex
- For a non-directed graph the edges are those leaving or entering
this vertex
- edgeto(dest)[source]
Get edge connecting vertex to specific neighbour
- Parameters:
dest (
Vertex
subclass) – a neigbouring vertex- Raises:
ValueError –
dest
is not a neighbour- Returns:
the edge from this vertex to
dest
- Return type:
Note
For a directed graph
dest
must be at the arrow end of the edge
- incidences()[source]
Neighbours and edges of a vertex
v.incidences()
is a generator that returns a list of incidences, tuples of (vertex, edge) for all neighbours of the vertexv
.Note
For a directed graph the edges are those leaving this vertex
- isneighbour(vertex)[source]
Test if vertex is a neigbour
- Parameters:
vertex (Vertex subclass) – vertex reference
- Returns:
true if a neighbour
- Return type:
bool
For a directed graph this is true only if the edge is from
self
tovertex
.
- neighbors()[source]
Neighbors of a vertex
v.neighbors()
is a list of neighbors of this vertex.Note
For a directed graph the neighbours are those on edges leaving this vertex
- neighbours()[source]
Neighbours of a vertex
v.neighbours()
is a list of neighbours of this vertex.Note
For a directed graph the neighbours are those on edges leaving this vertex
- property x
The x-coordinate of an embedded vertex
- Returns:
The x-coordinate
- Return type:
float
- property y
The y-coordinate of an embedded vertex
- Returns:
The y-coordinate
- Return type:
float
- property z
The z-coordinate of an embedded vertex
- Returns:
The z-coordinate
- Return type:
float