M-File Help: PGraph

M-File Help: PGraph | View code for PGraph

# PGraph

Graph class

g = PGraph() | create a 2D, planar embedded, directed graph
g = PGraph(n) | create an n-d, embedded, directed graph

Provides support for graphs that:

- are directed
- are embedded in a coordinate system
- have symmetric cost edges (A to B is same cost as B to A)
- have no loops (edges from A to A)
- have vertices that are represented by integers VID
- have edges that are represented by integers EID

## Methods

## Constructing the graph

g.add_node(coord) | add vertex, return vid
g.add_edge(v1, v2) | add edge from v1 to v2, return eid
g.setcost(e, c) | set cost for edge e
g.setdata(v, u) | set user data for vertex v
g.data(v) | get user data for vertex v
g.clear() | remove all vertices and edges from the graph

## Information from graph

g.edges(v) | list of edges for vertex v
g.cost(e) | cost of edge e
g.neighbours(v) | neighbours of vertex v
g.component(v) | component id for vertex v
g.connectivity() | number of edges for all vertices

## Display

g.plot() | set goal vertex for path planning
g.highlight_node(v) | highlight vertex v
g.highlight_edge(e) | highlight edge e
g.highlight_component(c) | highlight all nodes in component c
g.highlight_path(p) | highlight nodes and edge along path p

g.pick(coord) | vertex closest to coord

g.char() | convert graph to string
g.display() | display summary of graph

## Matrix representations

g.adjacency() | adjacency matrix
g.incidence() | incidence matrix
g.degree() | degree matrix
g.laplacian() | Laplacian matrix

## Planning paths through the graph

g.Astar(s, g) | shortest path from s to g
g.goal(v) | set goal vertex, and plan paths
g.path(v) | list of vertices from v to goal

## Graph and world points

g.coord(v) | coordinate of vertex v
g.distance(v1, v2) | distance between v1 and v2
g.distances(coord) | return sorted distances from coord to all vertices
g.closest(coord) | vertex closest to coord

## Object properties (read only)

g.n | number of vertices
g.ne | number of edges
g.nc | number of components

## Examples

    g = PGraph();
    g.add_node([1 2]');  % add node 1
    g.add_node([3 4]');  % add node 1
    g.add_node([1 3]');  % add node 1
    g.add_edge(1, 2);    % add edge 1-2
    g.add_edge(2, 3);    % add edge 2-3
    g.add_edge(1, 3);    % add edge 1-3
    g.plot()

## Notes

- Graph connectivity is maintained by a labeling algorithm and this is updated every time an edge is added.
- Nodes and edges cannot be deleted.
- Support for edge direction is rudimentary.

# PGraph.PGraph

Graph class constructor

g=PGraph(d, options) is a graph object embedded in d dimensions.

## Options

'distance', M | Use the distance metric M for path planning which is either 'Euclidean' (default) or 'SE2'.
'verbose' | Specify verbose operation

## Notes

- Number of dimensions is not limited to 2 or 3.
- The distance metric 'SE2' is the sum of the squares of the difference in position and angle modulo 2pi.
- To use a different distance metric create a subclass of PGraph and override the method distance_metric().

# PGraph.add_edge

Add an edge

E = G.add_edge(v1, v2) adds a directed edge from vertex id v1 to vertex id v2, and returns the edge id E. The edge cost is the distance between the vertices.

E = G.add_edge(v1, v2, C) as above but the edge cost is C.

## Notes

- Distance is computed according to the metric specified in the constructor.
- Graph connectivity is maintained by a labeling algorithm and this is updated every time an edge is added.

## See also

PGraph.add_node, PGraph.edgedir

# PGraph.add_node

Add a node

v = G.add_node(x) adds a node/vertex with coordinate x (Dx1) and returns the integer node id v.

v = G.add_node(x, v2) as above but connected by a directed edge from vertex v to vertex v2 with cost equal to the distance between the vertices.

v = G.add_node(x, v2, C) as above but the added edge has cost C.

## Notes

- Distance is computed according to the metric specified in the constructor.

## See also

PGraph.add_edge, PGraph.data, PGraph.getdata

# PGraph.adjacency

Adjacency matrix of graph

a = G.adjacency() is a matrix (NxN) where element a(i,j) is the cost of moving from vertex i to vertex j.

## Notes

- 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 one edge from vertex I to vertex J (either zero or one). The element (I,J) of A^N are the number of walks of length N from vertex I to vertex J.

## See also

PGraph.degree, PGraph.incidence, PGraph.laplacian

# PGraph.Astar

path finding

path = G.Astar(v1, v2) is the lowest cost path from vertex v1 to vertex v2. path is a list of vertices starting with v1 and ending v2.

[path,C] = G.Astar(v1, v2) as above but also returns the total cost of traversing path.

## Notes

- Uses the efficient A* search algorithm.

## References

- Correction to "A Formal Basis for the Heuristic Determination of Minimum Cost Paths". Hart, P. E.; Nilsson, N. J.; Raphael, B. SIGART Newsletter 37: 28-29, 1972.

## See also

PGraph.goal, PGraph.path

# PGraph.char

Convert graph to string

s = G.char() is a compact human readable representation of the state of the graph including the number of vertices, edges and components.

# PGraph.clear

Clear the graph

G.clear() removes all vertices, edges and components.

# PGraph.closest

Find closest vertex

v = G.closest(x) is the vertex geometrically closest to coordinate x.

[v,d] = G.closest(x) as above but also returns the distance d.

## See also

PGraph.distances

# PGraph.component

Graph component

C = G.component(v) is the id of the graph component that contains vertex v.

# PGraph.connectivity

Graph connectivity

C = G.connectivity() is a vector (Nx1) with the number of edges per vertex.

The average vertex connectivity is

    mean(g.connectivity())

and the minimum vertex connectivity is

    min(g.connectivity())

# PGraph.coord

Coordinate of node

x = G.coord(v) is the coordinate vector (Dx1) of vertex id v.

# PGraph.cost

Cost of edge

C = G.cost(E) is the cost of edge id E.

# PGraph.data

Get user data for node

u = G.data(v) gets the user data of vertex v which can be of any type such as a number, struct, object or cell array.

## See also

PGraph.setdata

# PGraph.degree

Degree matrix of graph

d = G.degree() is a diagonal matrix (NxN) where element d(i,i) is the number of edges connected to vertex id i.

## See also

PGraph.adjacency, PGraph.incidence, PGraph.laplacian

# PGraph.display

Display graph

G.display() displays a compact human readable representation of the state of the graph including the number of vertices, edges and components.

## See also

PGraph.char

# PGraph.distance

Distance between vertices

d = G.distance(v1, v2) is the geometric distance between the vertices v1 and v2.

## See also

PGraph.distances

# PGraph.distances

Distances from point to vertices

d = G.distances(x) is a vector (1xN) of geometric distance from the point x (Dx1) to every other vertex sorted into increasing order.

[d,w] = G.distances(p) as above but also returns w (1xN) with the corresponding vertex id.

## Notes

- Distance is computed according to the metric specified in the constructor.

## See also

PGraph.closest

# PGraph.edgedir

Find edge direction

d = G.edgedir(v1, v2) is the direction of the edge from vertex id v1 to vertex id v2.

If we add an edge from vertex 3 to vertex 4

    g.add_edge(3, 4)

then

    g.edgedir(3, 4)

is positive, and

    g.edgedir(4, 3)

is negative.

## See also

PGraph.add_node, PGraph.add_edge

# PGraph.edges

Find edges given vertex

E = G.edges(v) is a vector containing the id of all edges connected to vertex id v.

## See also

PGraph.edgedir

# PGraph.get.n

Number of vertices

G.n is the number of vertices in the graph.

## See also

PGraph.ne

# PGraph.get.nc

Number of components

G.nc is the number of components in the graph.

## See also

PGraph.component

# PGraph.get.ne

Number of edges

G.ne is the number of edges in the graph.

## See also

PGraph.n

# PGraph.goal

Set goal node

G.goal(vg) computes the cost of reaching every vertex in the graph connected to the goal vertex vg.

## Notes

- Combined with G.path performs a breadth-first search for paths to the goal.

## See also

PGraph.path, PGraph.Astar, astar

# PGraph.highlight_component

Highlight a graph component

G.highlight_component(C, options) highlights the vertices that belong to graph component C.

## Options

'NodeSize', S | Size of vertex circle (default 12)
'NodeFaceColor', C | Node circle color (default yellow)
'NodeEdgeColor', C | Node circle edge color (default blue)

## See also

PGraph.highlight_node, PGraph.highlight_edge, PGraph.highlight_component

# PGraph.highlight_edge

Highlight a node

G.highlight_edge(v1, v2) highlights the edge between vertices v1 and v2.

G.highlight_edge(E) highlights the edge with id E.

## Options

'EdgeColor', C | Edge edge color (default black)
'EdgeThickness', T | Edge thickness (default 1.5)

## See also

PGraph.highlight_node, PGraph.highlight_path, PGraph.highlight_component

# PGraph.highlight_node

Highlight a node

G.highlight_node(v, options) highlights the vertex v with a yellow marker. If v is a list of vertices then all are highlighted.

## Options

'NodeSize', S | Size of vertex circle (default 12)
'NodeFaceColor', C | Node circle color (default yellow)
'NodeEdgeColor', C | Node circle edge color (default blue)

## See also

PGraph.highlight_edge, PGraph.highlight_path, PGraph.highlight_component

# PGraph.highlight_path

Highlight path

G.highlight_path(p, options) highlights the path defined by vector p which is a list of vertex ids comprising the path.

## Options

'NodeSize', S | Size of vertex circle (default 12)
'NodeFaceColor', C | Node circle color (default yellow)
'NodeEdgeColor', C | Node circle edge color (default blue)
'EdgeColor', C | Node circle edge color (default black)

## See also

PGraph.highlight_node, PGraph.highlight_edge, PGraph.highlight_component

# PGraph.incidence

Incidence matrix of graph

in = G.incidence() is a matrix (NxNE) where element in(i,j) is non-zero if vertex id i is connected to edge id j.

## See also

PGraph.adjacency, PGraph.degree, PGraph.laplacian

# PGraph.laplacian

Laplacian matrix of graph

L = G.laplacian() is the Laplacian matrix (NxN) of the graph.

## Notes

- L is always positive-semidefinite.
- L has at least one zero eigenvalue.
- The number of zero eigenvalues is the number of connected components in the graph.

## See also

PGraph.adjacency, PGraph.incidence, PGraph.degree

# PGraph.neighbours

Neighbours of a vertex

n = G.neighbours(v) is a vector of ids for all vertices which are directly connected neighbours of vertex v.

[n,C] = G.neighbours(v) as above but also returns a vector C whose elements are the edge costs of the paths corresponding to the vertex ids in n.

# PGraph.neighbours_d

Directed neighbours of a vertex

n = G.neighbours_d(v) is a vector of ids for all vertices which are directly connected neighbours of vertex v. Elements are positive if there is a link from v to the node, and negative if the link is from the node to v.

[n,C] = G.neighbours_d(v) as above but also returns a vector C whose elements are the edge costs of the paths corresponding to the vertex ids in n.

# PGraph.path

Find path to goal node

p = G.path(vs) is a vector of vertex ids that form a path from the starting vertex vs to the previously specified goal. The path includes the start and goal vertex id.

To compute path to goal vertex 5

    g.goal(5);

then the path, starting from vertex 1 is

    p1 = g.path(1);

and the path starting from vertex 2 is

    p2 = g.path(2);

## Notes

- Pgraph.goal must have been invoked first.
- Can be used repeatedly to find paths from different starting points to the goal specified to Pgraph.goal().

## See also

PGraph.goal, PGraph.Astar

# PGraph.pick

Graphically select a vertex

v = G.pick() is the id of the vertex closest to the point clicked by the user on a plot of the graph.

## See also

PGraph.plot

# PGraph.plot

Plot the graph

G.plot(opt) plots the graph in the current figure. Nodes are shown as colored circles.

## Options

'labels' | Display vertex id (default false)
'edges' | Display edges (default true)
'edgelabels' | Display edge id (default false)
'NodeSize', S | Size of vertex circle (default 8)
'NodeFaceColor', C | Node circle color (default blue)
'NodeEdgeColor', C | Node circle edge color (default blue)
'NodeLabelSize', S | Node label text sizer (default 16)
'NodeLabelColor', C | Node label text color (default blue)
'EdgeColor', C | Edge color (default black)
'EdgeLabelSize', S | Edge label text size (default black)
'EdgeLabelColor', C | Edge label text color (default black)
'componentcolor' | Node color is a function of graph component

# PGraph.setcost

Set cost of edge

G.setcost(E, C) set cost of edge id E to C.

# PGraph.setdata

Set user data for node

G.setdata(v, u) sets the user data of vertex v to u which can be of any type such as a number, struct, object or cell array.

## See also

PGraph.data

# PGraph.vertices

Find vertices given edge

v = G.vertices(E) return the id of the vertices that define edge E.

© 1990-2014 Peter Corke.