{"id":1493,"date":"2015-11-18T17:48:46","date_gmt":"2015-11-18T22:48:46","guid":{"rendered":"https:\/\/blogs.mathworks.com\/steve\/?p=1493"},"modified":"2019-11-01T12:13:52","modified_gmt":"2019-11-01T16:13:52","slug":"graphs-in-matlab-r2015b","status":"publish","type":"post","link":"https:\/\/blogs.mathworks.com\/steve\/2015\/11\/18\/graphs-in-matlab-r2015b\/","title":{"rendered":"Graphs in MATLAB R2015b"},"content":{"rendered":"

I was inspired by ICIP 2015 and by the new graph functions in MATLAB R2015b to write some functions to help experiment with graph-based image processing algorithms. Earlier this week I submitted the code to the File Exchange<\/a>. Here's a screen shot:<\/p>

\"\" <\/p>

Over the next couple of weeks I want to show you how to get started with these functions. Today starts with a general introduction to graphs in MATLAB R2015b. I'll be picking on the state of Minnesota.<\/p>

\"\" <\/p>

There are lots of ways to create a graph. A simple way is to provide two lists of nodes. Each corresponding pair of nodes corresponds to an edge. Nodes can be numbered or identified by text labels.<\/p>

G = graph({'A'<\/span>, 'B'<\/span>, 'B'<\/span>}, {'B'<\/span>, 'C'<\/span>, 'D'<\/span>})\r\n<\/pre>
\r\nG = \r\n\r\n  graph with properties:\r\n\r\n    Edges: [3x1 table]\r\n    Nodes: [4x1 table]\r\n\r\n<\/pre>
As shown above, a graph contains a table of nodes and a table of edges.<\/p>
You can use the plot<\/tt> function to visualize a graph.<\/p>
plot(G)\r\n<\/pre>\"\" 
Use digraph<\/tt> to make a directed graph. Here's one that uses node numbers,node names, and edge weights.<\/p>
s = [1 1 2 2 3 3 4 4 5 5];\r\nt = [2 5 3 4 4 5 3 1 1 6];\r\nnames = {'alpha'<\/span>, 'beta'<\/span>, 'gamma'<\/span>, 'delta'<\/span>, 'epsilon'<\/span>, 'zeta'<\/span>};\r\nweight = randi(100, size(s));\r\nD = digraph(s, t, weight, names)\r\n<\/pre>
\r\nD = \r\n\r\n  digraph with properties:\r\n\r\n    Edges: [10x2 table]\r\n    Nodes: [6x1 table]\r\n\r\n<\/pre>
The weight values are stored directly in the edge table.<\/p>
D.Edges\r\n<\/pre>
\r\nans = \r\n\r\n           EndNodes           Weight\r\n    ______________________    ______\r\n\r\n    'alpha'      'beta'       24    \r\n    'alpha'      'epsilon'    36    \r\n    'beta'       'gamma'      83    \r\n    'beta'       'delta'       2    \r\n    'gamma'      'delta'       5    \r\n    'gamma'      'epsilon'    17    \r\n    'delta'      'alpha'      74    \r\n    'delta'      'gamma'      65    \r\n    'epsilon'    'alpha'      65    \r\n    'epsilon'    'zeta'       46    \r\n\r\n<\/pre>
When you plot a directed graphs, arrows show the edge directions.<\/p>
plot(D)\r\n<\/pre>\"\" 
You can choose different plot layouts.<\/p>
plot(D,'Layout'<\/span>,'layered'<\/span>)\r\ntitle('Layered graph plot'<\/span>)\r\n<\/pre>\"\" 
plot(D,'Layout'<\/span>,'circle'<\/span>)\r\naxis equal<\/span>\r\ntitle('Circular graph plot'<\/span>)\r\n<\/pre>\"\" 
You can customize a GraphPlot<\/tt> directly. Call the plot<\/tt> function with an output argument to get the GraphPlot<\/tt> object.<\/p>
p = plot(D)\r\n<\/pre>
\r\np = \r\n\r\n  GraphPlot with properties:\r\n\r\n     NodeColor: [0 0.4470 0.7410]\r\n    MarkerSize: 4\r\n        Marker: 'o'\r\n     EdgeColor: [0 0.4470 0.7410]\r\n     LineWidth: 0.5000\r\n     LineStyle: '-'\r\n     NodeLabel: {'alpha'  'beta'  'gamma'  'delta'  'epsilon'  'zeta'}\r\n     EdgeLabel: {}\r\n         XData: [-0.0350 0.5891 0.4312 0.9742 -0.5613 -1.3981]\r\n         YData: [0.4486 0.8689 -0.1321 0.3850 -0.4499 -1.1206]\r\n\r\n  Use GET to show all properties\r\n\r\n<\/pre>\"\" 
Now modify some of the properties.<\/p>
p.MarkerSize = 8;\r\np.Marker = 'x'<\/span>;\r\np.EdgeColor = 'red'<\/span>;\r\n<\/pre>\"\" 
I really like the highlight<\/tt> function, which you can use to emphasize selected graph nodes and edges.<\/p>
Here I highlight the shortest path between nodes 'alpha'<\/tt> and 'zeta'<\/tt>.<\/p>
p = plot(D);\r\nshortPath = shortestpath(D, 'alpha'<\/span>, 'zeta'<\/span>)\r\nhighlight(p, shortPath)\r\n<\/pre>
\r\nshortPath = \r\n\r\n    'alpha'    'epsilon'    'zeta'\r\n\r\n<\/pre>\"\" 
Many graph computations are available. For example, you can compute the pair-wise weighted distance between all nodes, or the out-degree of all nodes.<\/p>
distances(D)\r\n<\/pre>
\r\nans =\r\n\r\n     0    24    91    26    36    82\r\n    76     0    67     2    84   130\r\n    79   103     0     5    17    63\r\n    74    98    65     0    82   128\r\n    65    89   156    91     0    46\r\n   Inf   Inf   Inf   Inf   Inf     0\r\n\r\n<\/pre>
Poor node 6. You can't get anywhere else from there! That's because its out-degree is 0.<\/p>
outdegree(D)\r\n<\/pre>
\r\nans =\r\n\r\n     2\r\n     2\r\n     2\r\n     2\r\n     2\r\n     0\r\n\r\n<\/pre>
Let's look at a somewhat larger graph, based on the network of roads in the state of Minnesota. (If you want to play with this data yourself, you can get it from the UF Sparse Matrix Collection<\/a>.)<\/p>
load('minnesota.mat'<\/span>)\r\nxy = Problem.aux.coord;\r\nminn_roads = graph(Problem.A);\r\nminn_roads.Edges.Weight = hypot(xy(minn_roads.Edges.EndNodes(:,1),1) - ...<\/span>\r\n   xy(minn_roads.Edges.EndNodes(:,2),1), ...<\/span>\r\n   xy(minn_roads.Edges.EndNodes(:,1),2) - ...<\/span>\r\n   xy(minn_roads.Edges.EndNodes(:,2),2));\r\nplot(minn_roads,'XData'<\/span>,xy(:,1),'YData'<\/span>,xy(:,2));\r\n<\/pre>\"\" 
You can compute a graph's minimum spanning tree.<\/p>
T = minspantree(minn_roads)\r\nplot(T,'XData'<\/span>,xy(:,1),'YData'<\/span>,xy(:,2));\r\n<\/pre>
\r\nT = \r\n\r\n  graph with properties:\r\n\r\n    Edges: [2639x2 table]\r\n    Nodes: [2642x0 table]\r\n\r\n<\/pre>\"\" 
This example shows how to color the graph by the shortest path tree.<\/p>
[tree, d] = shortestpathtree(minn_roads, 1561);\r\np = plot(minn_roads,'XData'<\/span>,xy(:,1),'YData'<\/span>,xy(:,2));\r\np.NodeCData = d;\r\ncolorbar\r\n<\/pre>\"\" 
Next time I'll start talking about graphs whose nodes are image pixels.<\/p>