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:

DVertex

g.add_vertex() creates a new vertex with optional coord and name.
g.add_vertex(v) takes an instance or subclass of DVertex and adds it to the graph

classmethod vertex_copy(vertex)[source]

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 to
edge (Edge subclass, optional) – Use this as the edge object, otherwise a new Edge object is created from the vertices being connected, and the cost and edge parameters, defaults to None
cost (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:

Edge

v1.connect(v2) connects vertex v1 to vertex v2.

Note

If the vertices subclass UVertex the edge is undirected, and if they subclass DVertex the edge is directed.
Vertices must both be of the same Vertex subclass

Seealso:: Edge()

remove()[source]

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 edge

Note

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) calls v1.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 and v2.

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 edge e, ie. the vertex that is not v1.

vertices()[source]

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 vertex i to vertex j.

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 to Vertex subclass
reverse (bool, optional) – reverse link direction, defaults to False

Returns:

graph

Return type:

UGraph or DGraph

Behaves like a constructor for a DGraph or UGraph 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:: adjacency() incidence() degree()

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:

Edge

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:: Edge.connect() Vertex.connect()

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 vertex v to the graph G.

If the vertex has no name and name is None give it a default name #N where N 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 vertex i is connected to vertex j, 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 vertex i to vertex j (either zero or one).
If Ak = A ** k the element Ak[i,j] is the number of walks of length k from vertex i to vertex j.

Seealso:: Laplacian() incidence() degree()

average_degree()[source]

Average degree of the graph

Returns:: average degree
Return type:: float

Average degree is \(2 E / N\) for an undirected graph and \(E / N\) for a directed graph where \(E\) is the total number of edges and \(N\) 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:: metric()

component(c)[source]

All vertices in specified graph component

graph.component(c) is a list of all vertices in graph component c.

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())

copy()[source]

Deepcopy of graph

Parameters:: g (PGraph) – A graph
Returns:: deep copy
Return type:: PGraph

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 id i.

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 vertex i to vertex j. 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:: showgraph()

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:: Vertex.edges()

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() highlight_edge()

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 vertex i is connected to edge j, 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:: Laplacian() adjacency() degree()

iscyclic()[source]

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 vertex G 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:: heuristic()

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 vertex G 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 vertex G 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 and edge 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. If text is None default formatting is used. If text 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

show()[source]

showgraph(**kwargs)[source]

Display graph in a browser tab

Parameters:: kwargs – arguments passed to dotfile()

g.showgraph() renders and displays the graph in a browser tab. The graph is exported in GraphViz format, rendered to PDF using dot and then displayed in a browser tab.

Seealso:: dotfile()

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:

UVertex

g.add_vertex() creates a new vertex with optional coord and name.
g.add_vertex(v) takes an instance or subclass of UVertex and adds it to the graph

classmethod vertex_copy(vertex)[source]

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 to
edge (Edge subclass, optional) – Use this as the edge object, otherwise a new Edge object is created from the vertices being connected, and the cost and edge parameters, defaults to None
cost (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:

Edge

v1.connect(v2) connects vertex v1 to vertex v2.

Note

If the vertices subclass UVertex the edge is undirected, and if they subclass DVertex the edge is directed.
Vertices must both be of the same Vertex subclass

Seealso:: Edge()

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 others
coord the coordinate in an embedded graph (optional)

closest()[source]

connect(dest, edge=None, cost=None, data=None)[source]

Connect two vertices with an edge

Parameters:

dest (Vertex subclass) – The vertex to connect to
edge (Edge subclass, optional) – Use this as the edge object, otherwise a new Edge object is created from the vertices being connected, and the cost and edge parameters, defaults to None
cost (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:

Edge

v1.connect(v2) connects vertex v1 to vertex v2.

Note

If the vertices subclass UVertex the edge is undirected, and if they subclass DVertex the edge is directed.
Vertices must both be of the same Vertex subclass

Seealso:: Edge()

copy(cls=None)[source]

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:: edges()

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:: Edge

Note

For a directed graph dest must be at the arrow end of the edge

heuristic_distance(v2)[source]

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 vertex v.

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 to vertex.

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