PGraph module

class PGraph.DGraph(arg=None, metric=None, heuristic=None, verbose=False)[source]

Bases: PGraph

Class for directed graphs

Inheritance diagram of DGraph
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.

Inheritance diagram of DVertex
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:

ValueErrorvertex 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 2E/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

Inheritance diagram of UGraph
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.

Inheritance diagram of UVertex
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:

ValueErrordest 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