M-File Help: PGraph | View code for PGraph |
Graph class
g = PGraph() | create a 2D, planar, undirected graph |
g = PGraph(n) | create an n-d, undirected graph |
Provides support for graphs that:
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 |
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 |
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 |
g.adjacency() | adjacency matrix |
g.incidence() | incidence matrix |
g.degree() | degree matrix |
g.laplacian() | Laplacian matrix |
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 |
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 |
g.n | number of vertices |
g.ne | number of edges |
g.nc | number of components |
Graph class constructor
g=PGraph(d, options) is a graph object embedded in d dimensions.
'distance', M | Use the distance metric M for path planning which is either 'Euclidean' (default) or 'SE2'. |
'verbose' | Specify verbose operation |
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. cost C.
PGraph.add_node, PGraph.edgedir
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.
PGraph.add_edge, PGraph.data, PGraph.getdata
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.
PGraph.degree, PGraph.incidence, PGraph.laplacian
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.
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.
Clear the graph
G.clear() removes all vertices, edges and components.
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.
Graph component
C = G.component(v) is the id of the graph component
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())
Coordinate of node
x = G.coord(v) is the coordinate vector (Dx1) of vertex id v.
Cost of edge
C = G.cost(E) is the cost of edge id E.
Get user data for node
u = G.data(v) gets the user data of vertex v which can be of any type such as number, struct, object or cell array.
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.
PGraph.adjacency, PGraph.incidence, PGraph.laplacian
Display graph
G.display() displays a compact human readable representation of the state of the graph including the number of vertices, edges and components.
Distance between vertices
d = G.distance(v1, v2) is the geometric distance between the vertices v1 and v2.
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.
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.
PGraph.add_node, PGraph.add_edge
Find edges given vertex
E = G.edges(v) is a vector containing the id of all edges from vertex id v.
Number of vertices
G.n is the number of vertices in the graph.
Number of components
G.nc is the number of components in the graph.
Number of edges
G.ne is the number of edges in the graph.
Set goal node
G.goal(vg) computes the cost of reaching every vertex in the graph connected to the goal vertex vg.
Highlight a graph component
G.highlight_component(C, options) highlights the vertices that belong to graph component C.
'NodeSize', S | Size of vertex circle (default 12) |
'NodeFaceColor', C | Node circle color (default yellow) |
'NodeEdgeColor', C | Node circle edge color (default blue) |
PGraph.highlight_node, PGraph.highlight_edge, PGraph.highlight_component
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.
'EdgeColor', C | Edge edge color (default black) |
'EdgeThickness', T | Edge thickness (default 1.5) |
PGraph.highlight_node, PGraph.highlight_path, PGraph.highlight_component
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.
'NodeSize', S | Size of vertex circle (default 12) |
'NodeFaceColor', C | Node circle color (default yellow) |
'NodeEdgeColor', C | Node circle edge color (default blue) |
PGraph.highlight_edge, PGraph.highlight_path, PGraph.highlight_component
Highlight path
G.highlight_path(p, options) highlights the path defined by vector p which is a list of vertices comprising the path.
'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) |
PGraph.highlight_node, PGraph.highlight_edge, PGraph.highlight_component
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.
PGraph.adjacency, PGraph.degree, PGraph.laplacian
Laplacian matrix of graph
L = G.laplacian() is the Laplacian matrix (NxN) of the graph.
PGraph.adjacency, PGraph.incidence, PGraph.degree
the dominant and submissive labels
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.
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.
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);
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.
Plot the graph
G.plot(opt) plots the graph in the current figure. Nodes are shown as colored circles.
'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 |
Set cost of edge
G.setcost(E, C) set cost of edge id E to C.
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 number, struct, object or cell array.
Find vertices given edge
v = G.vertices(E) return the id of the vertices that define edge E.
© 1990-2012 Peter Corke.