{"id":2336,"date":"2017-02-20T12:00:19","date_gmt":"2017-02-20T17:00:19","guid":{"rendered":"https:\/\/blogs.mathworks.com\/cleve\/?p=2336"},"modified":"2017-02-18T11:57:31","modified_gmt":"2017-02-18T16:57:31","slug":"hypercubes-and-graphs","status":"publish","type":"post","link":"https:\/\/blogs.mathworks.com\/cleve\/2017\/02\/20\/hypercubes-and-graphs\/","title":{"rendered":"Hypercubes and Graphs"},"content":{"rendered":"\r\n<div class=\"content\"><!--introduction--><p>The adjacency matrix of a hypercube demonstrates the new MATLAB graph object.<\/p><!--\/introduction--><h3>Contents<\/h3><div><ul><li><a href=\"#171f4f59-bb47-489d-8845-c734d3e7c766\">Graphs<\/a><\/li><li><a href=\"#db781b31-3182-4bba-a3cb-3dd3f37bcf20\">Hypercubes<\/a><\/li><li><a href=\"#0026a27b-9e4f-4046-9f32-8b309e34fbcc\">IPSC<\/a><\/li><li><a href=\"#9574044d-c83e-4a92-b41a-f217ccc7191a\">3d<\/a><\/li><li><a href=\"#b2797440-4e68-426f-8ac5-0f8b2c055c54\">Layouts<\/a><\/li><li><a href=\"#a67c612c-376c-4532-beff-d2f79d56a50e\">4d<\/a><\/li><li><a href=\"#6cf93707-1df0-4518-973f-53128eea951f\">Insider<\/a><\/li><li><a href=\"#5dbf440d-66a9-4fd6-8f91-de2e1ddb1018\">Eigenvectors<\/a><\/li><li><a href=\"#d862724c-c42e-4754-9a6d-3f90b1da6bdb\">6d<\/a><\/li><li><a href=\"#b0d085d2-7703-4228-a081-4130e9c15d6a\">Bend It Like Beckham<\/a><\/li><\/ul><\/div><h4>Graphs<a name=\"171f4f59-bb47-489d-8845-c734d3e7c766\"><\/a><\/h4><p>My previous blog post was about the <a href=\"https:\/\/blogs.mathworks.com\/cleve\/2017\/02\/06\">Patience Chinese Rings Puzzle<\/a>. The puzzle's state lives in a six-dimensional space. There are 64 vertices, numbered 0 from to 63.  Each vertex is connected to six other vertices, the ones whose numbers, expressed in binary, differ from its own by one bit.  That connectivity arrangement -- those vertices and the connections between them -- form a <i>graph<\/i> known as a <i>hypercube<\/i>.<\/p><p>Recent versions of MATLAB include two new objects, <tt>graph<\/tt> and <tt>digraph<\/tt>.  Here is an abbreviated <tt>help<\/tt> entry for <tt>graph<\/tt>.<\/p><pre>&gt;&gt; help graph\r\ngraph Undirected Graph\r\nG = graph(A) uses the square symmetric matrix A as an adjacency matrix\r\nand constructs a weighted graph with edges corresponding to the nonzero\r\nentries of A.  If A is logical then no weights are added.<\/pre><pre>G = graph(A,NAMES) additionally uses the cell array of strings NAMES as\r\nthe names of the nodes in G.  NAMES must have as many elements as\r\nsize(A,1).<\/pre><h4>Hypercubes<a name=\"db781b31-3182-4bba-a3cb-3dd3f37bcf20\"><\/a><\/h4><p>And here is a function that generates the adjacency matrix for a hypercube.<\/p><pre class=\"codeinput\">   type <span class=\"string\">hypercube<\/span>\r\n<\/pre><pre class=\"codeoutput\">\r\nfunction A = hypercube(d)\r\n% hypercube(d) is a logical adjacency matrix for a d-dimensional hypercube.\r\n    pow2 = 2.^(0:d-1);\r\n    f2b = @(j) floor(rem(j.\/pow2,2)); % flint to binary\r\n    b2f = @(b) b*pow2'; % binary to flint\r\n    n = 2^d;\r\n    A = zeros(n,n,'logical');\r\n    for j = 0:n-1\r\n        % Convert column index to binary.\r\n        b = f2b(j);\r\n        % Flip bits to get corresponding row indices.\r\n        for i = 1:d\r\n            b(i) = ~b(i);\r\n            k = b2f(b);\r\n            b(i) = ~b(i);\r\n            A(k+1,j+1) = 1;\r\n        end\r\n    end\r\nend\r\n<\/pre><h4>IPSC<a name=\"0026a27b-9e4f-4046-9f32-8b309e34fbcc\"><\/a><\/h4><p>I first encountered hypercubes thirty years ago.  For a couple of years in the late 1980s I was involved with one of the world's first commercial parallel computers, the IPSC, the <i>Intel Personal Super Computer<\/i>.  Here is a link to <a href=\"https:\/\/blogs.mathworks.com\/cleve\/2013\/10\/28\/the-intel-hypercube-part-1\">my blog post in 2013<\/a>.<\/p><p>The IPSC was constructed from single board computers, similar to the mother boards in the PCs of the day.  We had three models -- <i>d5<\/i>, <i>d6<\/i> and <i>d7<\/i> -- with 32, 64 or 128 processors.  Since it was impractical to connect every processor directly to every other processor, the connection network formed a hypercube.  For a machine with $n = 2^d$ processors, that's $n \\log_2{n}$ instead of $n^2$ connections.  For the d6 that's 384 connections instead of 4096.<\/p><p>The d6 model has the same graph as the patience puzzle that I wrote about in my previous post.  (Actually, the IPSC's graph is a directed graph, a <i>digraph<\/i>, because the connections are two-way.  But undirected graphs have simpler plots.)<\/p><h4>3d<a name=\"9574044d-c83e-4a92-b41a-f217ccc7191a\"><\/a><\/h4><p>A 3-dimensional hypercube is not a conventional cube. The 3-d hypercube is only the vertices and edges of the cube. The cube itself includes its surfaces and interior.  If you had a wire-frame cube made from rubber bands and squished it around without destroying the connectivity, you wouldn't have a cube any more, but you would still have a model of a hypercube.<\/p><p>Here is the adjacency matrix of a 3-d hypercube.  (It's so small that it's not necessary to make use of the sparsity.)<\/p><pre class=\"codeinput\">   A = hypercube(3)\r\n<\/pre><pre class=\"codeoutput\">A =\r\n  8&times;8 logical array\r\n   0   1   1   0   1   0   0   0\r\n   1   0   0   1   0   1   0   0\r\n   1   0   0   1   0   0   1   0\r\n   0   1   1   0   0   0   0   1\r\n   1   0   0   0   0   1   1   0\r\n   0   1   0   0   1   0   0   1\r\n   0   0   1   0   1   0   0   1\r\n   0   0   0   1   0   1   1   0\r\n<\/pre><p>One view of this matrix is its <tt>spy<\/tt> plot.<\/p><pre class=\"codeinput\">   spy(A)\r\n<\/pre><img decoding=\"async\" vspace=\"5\" hspace=\"5\" src=\"https:\/\/blogs.mathworks.com\/cleve\/files\/graphs_blog_01.png\" alt=\"\"> <p>To get other views, let's use the new MATLAB graph object. We'll label the nodes with '0' through '7'.<\/p><pre class=\"codeinput\">   nodes = num2cellstr(0:7)\r\n   G = graph(A,nodes)\r\n<\/pre><pre class=\"codeoutput\">nodes =\r\n  1&times;8 cell array\r\n    '0'    '1'    '2'    '3'    '4'    '5'    '6'    '7'\r\nG = \r\n  graph with properties:\r\n\r\n    Edges: [12&times;1 table]\r\n    Nodes: [8&times;1 table]\r\n<\/pre><h4>Layouts<a name=\"b2797440-4e68-426f-8ac5-0f8b2c055c54\"><\/a><\/h4><p>By itself, a graph doesn't have any geometric structure.  In order to plot it you specify a <i>layout<\/i>, or coordinates, for the nodes. Coming up with good layouts is an art, as well as a science. Here are the currently available layouts.<\/p><pre>     'auto'      (Default) Automatic choice of layout method based on\r\n                 the structure of the graph.\r\n     'circle'    Circular layout.\r\n     'force'     Force-directed layout. Uses attractive and repulsive\r\n                 forces on nodes.\r\n     'layered'   Layered layout. Places nodes in a set of layers.\r\n     'subspace'  Subspace embedding layout. Uses projection onto an\r\n                 embedded subspace.\r\n     'force3'    3-D force-directed layout.\r\n     'subspace3' 3-D Subspace embedding layout.<\/pre><p>The default layout of the 3-d hypercube graph is a perspective view of an ordinary cube.<\/p><pre class=\"codeinput\">   plot(G)\r\n   axis <span class=\"string\">square<\/span>\r\n<\/pre><img decoding=\"async\" vspace=\"5\" hspace=\"5\" src=\"https:\/\/blogs.mathworks.com\/cleve\/files\/graphs_blog_02.png\" alt=\"\"> <h4>4d<a name=\"a67c612c-376c-4532-beff-d2f79d56a50e\"><\/a><\/h4><p>Let's move up to four dimensions.<\/p><pre class=\"codeinput\">   A = hypercube(4);\r\n   spy(A)\r\n<\/pre><img decoding=\"async\" vspace=\"5\" hspace=\"5\" src=\"https:\/\/blogs.mathworks.com\/cleve\/files\/graphs_blog_03.png\" alt=\"\"> <p>I think the default layout of the 4-d hypercube is attractive.<\/p><pre class=\"codeinput\">   nodes = num2cellstr(0:15)';\r\n   G = graph(A,nodes);\r\n   plot(G)\r\n   axis <span class=\"string\">square<\/span>\r\n<\/pre><img decoding=\"async\" vspace=\"5\" hspace=\"5\" src=\"https:\/\/blogs.mathworks.com\/cleve\/files\/graphs_blog_04.png\" alt=\"\"> <p>But <tt>'circle'<\/tt> is another attractive layout.  Notice that '3' is not connected to '4' because 0011 and 0100 differ by more than a single bit. The blue dot in the center is not a node -- it is just the point where many edges cross.<\/p><pre class=\"codeinput\">   plot(G,<span class=\"string\">'layout'<\/span>,<span class=\"string\">'circle'<\/span>)\r\n   axis <span class=\"string\">square<\/span>\r\n<\/pre><img decoding=\"async\" vspace=\"5\" hspace=\"5\" src=\"https:\/\/blogs.mathworks.com\/cleve\/files\/graphs_blog_05.png\" alt=\"\"> <p>Here is yet another view.<\/p><pre class=\"codeinput\">   plot(G,<span class=\"string\">'layout'<\/span>,<span class=\"string\">'layered'<\/span>)\r\n   axis <span class=\"string\">square<\/span>\r\n<\/pre><img decoding=\"async\" vspace=\"5\" hspace=\"5\" src=\"https:\/\/blogs.mathworks.com\/cleve\/files\/graphs_blog_06.png\" alt=\"\"> <h4>Insider<a name=\"6cf93707-1df0-4518-973f-53128eea951f\"><\/a><\/h4><p>I'm still not satisfied.  I want one cube inside of another. I can supply my own coordinates for the vertices.<\/p><pre class=\"codeinput\">    type <span class=\"string\">cubelet<\/span>\r\n<\/pre><pre class=\"codeoutput\">\r\nfunction x = cubelet\r\n% x = cubelet\r\n% 8-by-3 array of vertices of a unit cube.\r\n   x = [-1 -1 -1\r\n         1 -1 -1\r\n        -1  1 -1\r\n         1  1 -1\r\n        -1 -1  1\r\n         1 -1  1\r\n        -1  1  1\r\n         1  1  1];\r\nend\r\n<\/pre><pre class=\"codeinput\">    x = cubelet;\r\n    x = [3*x; x];\r\n    plot(G,<span class=\"string\">'xdata'<\/span>,x(:,1),<span class=\"string\">'ydata'<\/span>,x(:,2),<span class=\"string\">'zdata'<\/span>,x(:,3))\r\n    axis <span class=\"string\">equal<\/span> <span class=\"string\">off<\/span>\r\n    view(-20,11)\r\n<\/pre><img decoding=\"async\" vspace=\"5\" hspace=\"5\" src=\"https:\/\/blogs.mathworks.com\/cleve\/files\/graphs_blog_07.png\" alt=\"\"> <p>This served as a logo for the IPSC.<\/p><h4>Eigenvectors<a name=\"5dbf440d-66a9-4fd6-8f91-de2e1ddb1018\"><\/a><\/h4><p>The Laplacian of a graph is a matrix that has the degree of the nodes on the diagonal and -1's off the diagonal marking the edges.  For the 3-d hypercube the degrees are all 4.  So here the Laplacian.<\/p><pre class=\"codeinput\">    L = full(laplacian(G));\r\n    frmt = [<span class=\"string\">'   '<\/span> repmat(<span class=\"string\">'%3d'<\/span>,1,16) <span class=\"string\">'\\n'<\/span>];\r\n    fprintf(<span class=\"string\">'L = \\n'<\/span>)\r\n    fprintf(frmt,L)\r\n<\/pre><pre class=\"codeoutput\">L = \r\n     4 -1 -1  0 -1  0  0  0 -1  0  0  0  0  0  0  0\r\n    -1  4  0 -1  0 -1  0  0  0 -1  0  0  0  0  0  0\r\n    -1  0  4 -1  0  0 -1  0  0  0 -1  0  0  0  0  0\r\n     0 -1 -1  4  0  0  0 -1  0  0  0 -1  0  0  0  0\r\n    -1  0  0  0  4 -1 -1  0  0  0  0  0 -1  0  0  0\r\n     0 -1  0  0 -1  4  0 -1  0  0  0  0  0 -1  0  0\r\n     0  0 -1  0 -1  0  4 -1  0  0  0  0  0  0 -1  0\r\n     0  0  0 -1  0 -1 -1  4  0  0  0  0  0  0  0 -1\r\n    -1  0  0  0  0  0  0  0  4 -1 -1  0 -1  0  0  0\r\n     0 -1  0  0  0  0  0  0 -1  4  0 -1  0 -1  0  0\r\n     0  0 -1  0  0  0  0  0 -1  0  4 -1  0  0 -1  0\r\n     0  0  0 -1  0  0  0  0  0 -1 -1  4  0  0  0 -1\r\n     0  0  0  0 -1  0  0  0 -1  0  0  0  4 -1 -1  0\r\n     0  0  0  0  0 -1  0  0  0 -1  0  0 -1  4  0 -1\r\n     0  0  0  0  0  0 -1  0  0  0 -1  0 -1  0  4 -1\r\n     0  0  0  0  0  0  0 -1  0  0  0 -1  0 -1 -1  4\r\n<\/pre><p>The Laplacian could also be obtained from the original adjacency matrix.<\/p><pre class=\"codeinput\">    L = diag(sum(A)) - A;\r\n<\/pre><p>The coordinates of possible layouts for the plot of the graph can be obtained by picking three of the eigenvectors of the Laplacian. Here are all of the eigenvalues and three of the eigenvectors. (The eigenvalues are all integers.)<\/p><pre class=\"codeinput\">    [V,E] = eig(L);\r\n    evals = round(diag(E)');\r\n    fprintf(<span class=\"string\">'evals = \\n'<\/span>)\r\n    fprintf(frmt,evals)\r\n    evecs3 = V(:,1:3)\r\n<\/pre><pre class=\"codeoutput\">evals = \r\n     0  2  2  2  2  4  4  4  4  4  4  6  6  6  6  8\r\nevecs3 =\r\n   -0.2500    0.0216    0.0025\r\n   -0.2500    0.1620    0.4067\r\n   -0.2500    0.0245   -0.1449\r\n   -0.2500    0.1649    0.2593\r\n   -0.2500    0.2546   -0.2521\r\n   -0.2500    0.3950    0.1521\r\n   -0.2500    0.2575   -0.3996\r\n   -0.2500    0.3979    0.0046\r\n   -0.2500   -0.3979   -0.0046\r\n   -0.2500   -0.2575    0.3996\r\n   -0.2500   -0.3950   -0.1521\r\n   -0.2500   -0.2546    0.2521\r\n   -0.2500   -0.1649   -0.2593\r\n   -0.2500   -0.0245    0.1449\r\n   -0.2500   -0.1620   -0.4067\r\n   -0.2500   -0.0216   -0.0025\r\n<\/pre><p>And here is the resulting plot.<\/p><pre class=\"codeinput\">    G = graph(A,nodes);\r\n    plot(G,<span class=\"string\">'xdata'<\/span>,V(:,1),<span class=\"string\">'ydata'<\/span>,V(:,2),<span class=\"string\">'zdata'<\/span>,V(:,3))\r\n    axis <span class=\"string\">square<\/span> <span class=\"string\">off<\/span>\r\n    set(gca,<span class=\"string\">'clipping'<\/span>,<span class=\"string\">'off'<\/span>)\r\n    zoom(2)\r\n    view(-75,45)\r\n<\/pre><img decoding=\"async\" vspace=\"5\" hspace=\"5\" src=\"https:\/\/blogs.mathworks.com\/cleve\/files\/graphs_blog_08.png\" alt=\"\"> <h4>6d<a name=\"d862724c-c42e-4754-9a6d-3f90b1da6bdb\"><\/a><\/h4><p>The state space of both the puzzle that got me started on this blog post and one of the models of the parallel computer that consumed me thirty years ago is six dimensional.<\/p><pre class=\"codeinput\">    A = hypercube(6);\r\n    spy(A)\r\n<\/pre><img decoding=\"async\" vspace=\"5\" hspace=\"5\" src=\"https:\/\/blogs.mathworks.com\/cleve\/files\/graphs_blog_09.png\" alt=\"\"> <p>A plot of a cube inside of a cube inside of a cube inside of a cube is a bit messy.  The circle layout is an interesting design, but it is hard to see which nodes are connected to which.<\/p><pre class=\"codeinput\">    nodes = num2cellstr(0:63)';\r\n    G = graph(A,nodes);\r\n    plot(G,<span class=\"string\">'layout'<\/span>,<span class=\"string\">'circle'<\/span>)\r\n    axis <span class=\"string\">square<\/span>\r\n<\/pre><img decoding=\"async\" vspace=\"5\" hspace=\"5\" src=\"https:\/\/blogs.mathworks.com\/cleve\/files\/graphs_blog_10.png\" alt=\"\"> <p>Here is a three-dimensional layout.<\/p><pre class=\"codeinput\">    plot(G,<span class=\"string\">'layout'<\/span>,<span class=\"string\">'subspace3'<\/span>)\r\n    axis <span class=\"string\">off<\/span> <span class=\"string\">square<\/span>\r\n    set(gca,<span class=\"string\">'clipping'<\/span>,<span class=\"string\">'off'<\/span>)\r\n    zoom(2)\r\n    view(-108,-21)\r\n<\/pre><img decoding=\"async\" vspace=\"5\" hspace=\"5\" src=\"https:\/\/blogs.mathworks.com\/cleve\/files\/graphs_blog_11.png\" alt=\"\"> <h4>Bend It Like Beckham<a name=\"b0d085d2-7703-4228-a081-4130e9c15d6a\"><\/a><\/h4><p>The Bucky Ball provides an elegant example of a graph.  Here's the <tt>help<\/tt> entry.<\/p><pre class=\"codeinput\">   help <span class=\"string\">bucky<\/span>\r\n<\/pre><pre class=\"codeoutput\"> BUCKY  Connectivity graph of the Buckminster Fuller geodesic dome.\r\n    B = BUCKY is the 60-by-60 sparse adjacency matrix of the\r\n        connectivity graph of the geodesic dome, the soccer ball,\r\n        and the carbon-60 molecule.\r\n    [B,V] = BUCKY also returns xyz coordinates of the vertices.\r\n\r\n<\/pre><p>When we put <tt>bucky<\/tt> into MATLAB years ago we went to a whole lot of trouble to compute those vertex coordinates.  (To see how much trouble, <tt>type bucky<\/tt>.)  But now, with the three dimensional <tt>force3<\/tt> layout, the <tt>graph\/plot<\/tt> function does that work. Putting a little spin on it makes it interesting to watch.<\/p><pre class=\"codeinput\">   type <span class=\"string\">bucky_gif<\/span>\r\n<\/pre><pre class=\"codeoutput\">\r\nB = graph(bucky);\r\nplot(B,'layout','force3')\r\naxis square off vis3d\r\nset(gca,'clipping','off')\r\nzoom(2)\r\n[a,e] = view;\r\ngif_frame('bucky_spin.gif')\r\nfor d = 10:10:360\r\n    view(a+d,e+d)\r\n    gif_frame\r\nend\r\ngif_frame('reset')\r\n<\/pre><p><img decoding=\"async\" vspace=\"5\" hspace=\"5\" src=\"https:\/\/blogs.mathworks.com\/cleve\/files\/bucky_spin.gif\" alt=\"\"> <\/p><p>It's more fun to use the <tt>cameratoolbar<\/tt> and put the spin on the ball yourself.<\/p><script language=\"JavaScript\"> <!-- \r\n    function grabCode_003a22074b4d4d6dbb2c9016aeb3b4f9() {\r\n        \/\/ Remember the title so we can use it in the new page\r\n        title = document.title;\r\n\r\n        \/\/ Break up these strings so that their presence\r\n        \/\/ in the Javascript doesn't mess up the search for\r\n        \/\/ the MATLAB code.\r\n        t1='003a22074b4d4d6dbb2c9016aeb3b4f9 ' + '##### ' + 'SOURCE BEGIN' + ' #####';\r\n        t2='##### ' + 'SOURCE END' + ' #####' + ' 003a22074b4d4d6dbb2c9016aeb3b4f9';\r\n    \r\n        b=document.getElementsByTagName('body')[0];\r\n        i1=b.innerHTML.indexOf(t1)+t1.length;\r\n        i2=b.innerHTML.indexOf(t2);\r\n \r\n        code_string = b.innerHTML.substring(i1, i2);\r\n        code_string = code_string.replace(\/REPLACE_WITH_DASH_DASH\/g,'--');\r\n\r\n        \/\/ Use \/x3C\/g instead of the less-than character to avoid errors \r\n        \/\/ in the XML parser.\r\n        \/\/ Use '\\x26#60;' instead of '<' so that the XML parser\r\n        \/\/ doesn't go ahead and substitute the less-than character. \r\n        code_string = code_string.replace(\/\\x3C\/g, '\\x26#60;');\r\n\r\n        copyright = 'Copyright 2017 The MathWorks, Inc.';\r\n\r\n        w = window.open();\r\n        d = w.document;\r\n        d.write('<pre>\\n');\r\n        d.write(code_string);\r\n\r\n        \/\/ Add copyright line at the bottom if specified.\r\n        if (copyright.length > 0) {\r\n            d.writeln('');\r\n            d.writeln('%%');\r\n            if (copyright.length > 0) {\r\n                d.writeln('% _' + copyright + '_');\r\n            }\r\n        }\r\n\r\n        d.write('<\/pre>\\n');\r\n\r\n        d.title = title + ' (MATLAB code)';\r\n        d.close();\r\n    }   \r\n     --> <\/script><p style=\"text-align: right; font-size: xx-small; font-weight:lighter;   font-style: italic; color: gray\"><br><a href=\"javascript:grabCode_003a22074b4d4d6dbb2c9016aeb3b4f9()\"><span style=\"font-size: x-small;        font-style: italic;\">Get \r\n      the MATLAB code <noscript>(requires JavaScript)<\/noscript><\/span><\/a><br><br>\r\n      Published with MATLAB&reg; R2017a<br><\/p><\/div><!--\r\n003a22074b4d4d6dbb2c9016aeb3b4f9 ##### SOURCE BEGIN #####\r\n%% Hypercubes and Graphs\r\n% The adjacency matrix of a hypercube demonstrates the new MATLAB graph\r\n% object.\r\n\r\n%% Graphs\r\n% My previous blog post was about the \r\n% <https:\/\/blogs.mathworks.com\/cleve\/2017\/02\/06\r\n% Patience Chinese Rings Puzzle>.\r\n% The puzzle's state lives in a six-dimensional space.\r\n% There are 64 vertices, numbered 0 from to 63.  Each vertex is connected\r\n% to six other vertices, the ones whose numbers, expressed in binary,\r\n% differ from its own by one bit.  That connectivity arrangement REPLACE_WITH_DASH_DASH\r\n% those vertices and the connections between them REPLACE_WITH_DASH_DASH form a _graph_\r\n% known as a _hypercube_.\r\n\r\n%%\r\n% Recent versions of MATLAB include two new objects, \r\n% |graph| and |digraph|.  Here is an abbreviated |help| entry for |graph|.\r\n%\r\n%  >> help graph\r\n%  graph Undirected Graph\r\n%  G = graph(A) uses the square symmetric matrix A as an adjacency matrix\r\n%  and constructs a weighted graph with edges corresponding to the nonzero\r\n%  entries of A.  If A is logical then no weights are added.\r\n% \r\n%  G = graph(A,NAMES) additionally uses the cell array of strings NAMES as\r\n%  the names of the nodes in G.  NAMES must have as many elements as\r\n%  size(A,1).\r\n \r\n%% Hypercubes\r\n% And here is a function that generates the adjacency matrix for a\r\n% hypercube.\r\n\r\n   type hypercube\r\n   \r\n%% IPSC\r\n% I first encountered hypercubes thirty years ago.  For a couple of years\r\n% in the late 1980s I was involved with one of the world's first\r\n% commercial parallel computers, the IPSC, the _Intel Personal\r\n% Super Computer_.  Here is a link to\r\n% <https:\/\/blogs.mathworks.com\/cleve\/2013\/10\/28\/the-intel-hypercube-part-1\r\n% my blog post in 2013>.\r\n\r\n%%\r\n% The IPSC was constructed from single board computers, similar to\r\n% the mother boards in the PCs of the day.  We had three models REPLACE_WITH_DASH_DASH\r\n% _d5_, _d6_ and _d7_ REPLACE_WITH_DASH_DASH with 32, 64 or 128 processors.  Since it\r\n% was impractical to connect every processor directly to every other\r\n% processor, the connection network formed a hypercube.  For a machine\r\n% with $n = 2^d$ processors, that's $n \\log_2{n}$ instead of $n^2$ \r\n% connections.  For the d6 that's 384 connections instead of 4096.\r\n\r\n%%\r\n% The d6 model has the same graph as the patience puzzle that I wrote\r\n% about in my previous post.  (Actually, the IPSC's graph is a directed\r\n% graph, a _digraph_, because the connections are two-way.  But\r\n% undirected graphs have simpler plots.)\r\n\r\n%% 3d\r\n% A 3-dimensional hypercube is not a conventional cube.\r\n% The 3-d hypercube is only the vertices and edges of the cube.\r\n% The cube itself includes its surfaces and interior.  If you had\r\n% a wire-frame cube made from rubber bands and squished it around\r\n% without destroying the connectivity, you wouldn't have a cube any more,\r\n% but you would still have a model of a hypercube.\r\n\r\n%%\r\n% Here is the adjacency matrix of a 3-d hypercube.  (It's so small that\r\n% it's not necessary to make use of the sparsity.)\r\n\r\n   A = hypercube(3)\r\n   \r\n%%\r\n% One view of this matrix is its |spy| plot.\r\n\r\n   spy(A)\r\n   \r\n%%\r\n% To get other views, let's use the new MATLAB graph object.\r\n% We'll label the nodes with '0' through '7'.\r\n\r\n   nodes = num2cellstr(0:7)\r\n   G = graph(A,nodes)\r\n \r\n%% Layouts\r\n% By itself, a graph doesn't have any geometric structure.  In order\r\n% to plot it you specify a _layout_, or coordinates, for the nodes.\r\n% Coming up with good layouts is an art, as well as a science.\r\n% Here are the currently available layouts.\r\n%\r\n%       'auto'      (Default) Automatic choice of layout method based on\r\n%                   the structure of the graph.\r\n%       'circle'    Circular layout.\r\n%       'force'     Force-directed layout. Uses attractive and repulsive \r\n%                   forces on nodes.\r\n%       'layered'   Layered layout. Places nodes in a set of layers.\r\n%       'subspace'  Subspace embedding layout. Uses projection onto an \r\n%                   embedded subspace.\r\n%       'force3'    3-D force-directed layout.\r\n%       'subspace3' 3-D Subspace embedding layout.\r\n\r\n%%\r\n% The default layout of the 3-d hypercube graph is a perspective view of\r\n% an ordinary cube.\r\n\r\n   plot(G)\r\n   axis square \r\n   \r\n%% 4d\r\n% Let's move up to four dimensions.\r\n\r\n   A = hypercube(4);\r\n   spy(A)\r\n   \r\n%%\r\n% I think the default layout of the 4-d hypercube is attractive.\r\n\r\n   nodes = num2cellstr(0:15)';\r\n   G = graph(A,nodes);\r\n   plot(G)\r\n   axis square\r\n   \r\n%%\r\n% But |'circle'| is another attractive layout.  Notice that '3' is not\r\n% connected to '4' because 0011 and 0100 differ by more than a single bit.\r\n% The blue dot in the center is not a node REPLACE_WITH_DASH_DASH it is just the point where\r\n% many edges cross.\r\n\r\n   plot(G,'layout','circle')\r\n   axis square\r\n   \r\n%%\r\n% Here is yet another view.\r\n\r\n   plot(G,'layout','layered')\r\n   axis square\r\n   \r\n%% Insider\r\n% I'm still not satisfied.  I want one cube inside of another.\r\n% I can supply my own coordinates for the vertices.\r\n\r\n    type cubelet\r\n    \r\n%%\r\n\r\n    x = cubelet;\r\n    x = [3*x; x];\r\n    plot(G,'xdata',x(:,1),'ydata',x(:,2),'zdata',x(:,3))\r\n    axis equal off\r\n    view(-20,11)\r\n    \r\n%%\r\n% This served as a logo for the IPSC.\r\n    \r\n%% Eigenvectors\r\n% The Laplacian of a graph is a matrix that has the degree of the nodes \r\n% on the diagonal and -1's off the diagonal marking the edges.  For the \r\n% 3-d hypercube the degrees are all 4.  So here the Laplacian.\r\n\r\n    L = full(laplacian(G));\r\n    frmt = ['   ' repmat('%3d',1,16) '\\n'];\r\n    fprintf('L = \\n')\r\n    fprintf(frmt,L)\r\n\r\n%%\r\n% The Laplacian could also be obtained from the original adjacency matrix.\r\n\r\n    L = diag(sum(A)) - A;\r\n    \r\n%%\r\n% The coordinates of possible layouts for the plot of the graph can be\r\n% obtained by picking three of the eigenvectors of the Laplacian.\r\n% Here are all of the eigenvalues and three of the eigenvectors.\r\n% (The eigenvalues are all integers.)\r\n\r\n    [V,E] = eig(L);\r\n    evals = round(diag(E)');\r\n    fprintf('evals = \\n')\r\n    fprintf(frmt,evals)\r\n    evecs3 = V(:,1:3)\r\n   \r\n%%\r\n% And here is the resulting plot.\r\n\r\n    G = graph(A,nodes);\r\n    plot(G,'xdata',V(:,1),'ydata',V(:,2),'zdata',V(:,3))\r\n    axis square off\r\n    set(gca,'clipping','off')\r\n    zoom(2)\r\n    view(-75,45)\r\n   \r\n%% 6d\r\n% The state space of both the puzzle that got me started\r\n% on this blog post and one of the models of the parallel computer that\r\n% consumed me thirty years ago is six dimensional.\r\n\r\n    A = hypercube(6);\r\n    spy(A)\r\n\r\n%%\r\n% A plot of a cube inside of a cube inside of a cube inside of a cube is\r\n% a bit messy.  The circle layout is an interesting design, but it is hard\r\n% to see which nodes are connected to which.\r\n    \r\n    nodes = num2cellstr(0:63)';\r\n    G = graph(A,nodes);\r\n    plot(G,'layout','circle')\r\n    axis square\r\n    \r\n%%\r\n% Here is a three-dimensional layout.\r\n\r\n    plot(G,'layout','subspace3')\r\n    axis off square\r\n    set(gca,'clipping','off')\r\n    zoom(2)\r\n    view(-108,-21)\r\n    \r\n%% Bend It Like Beckham\r\n% The Bucky Ball provides an elegant example of a graph.  Here's the\r\n% |help| entry.\r\n\r\n   help bucky\r\n   \r\n%%\r\n% When we put |bucky| into MATLAB years ago we went to a whole lot of\r\n% trouble to compute those vertex coordinates.  (To see how much trouble,\r\n% |type bucky|.)  But now, with the three dimensional |force3| layout,\r\n% the |graph\/plot| function does that work. Putting a little spin on it\r\n% makes it interesting to watch.\r\n\r\n   type bucky_gif\r\n   \r\n%%\r\n% <<bucky_spin.gif>>\r\n%   \r\n% It's more fun to use the |cameratoolbar| and put the spin on the ball\r\n% yourself.\r\n\r\n##### SOURCE END ##### 003a22074b4d4d6dbb2c9016aeb3b4f9\r\n-->","protected":false},"excerpt":{"rendered":"<div class=\"overview-image\"><img decoding=\"async\"  class=\"img-responsive\" src=\"https:\/\/blogs.mathworks.com\/cleve\/files\/graphs_blog_01.png\" onError=\"this.style.display ='none';\" \/><\/div><!--introduction--><p>The adjacency matrix of a hypercube demonstrates the new MATLAB graph object.... <a class=\"read-more\" href=\"https:\/\/blogs.mathworks.com\/cleve\/2017\/02\/20\/hypercubes-and-graphs\/\">read more >><\/a><\/p>","protected":false},"author":78,"featured_media":0,"comment_status":"open","ping_status":"closed","sticky":false,"template":"","format":"standard","meta":[],"categories":[13,5,23,4,6],"tags":[],"_links":{"self":[{"href":"https:\/\/blogs.mathworks.com\/cleve\/wp-json\/wp\/v2\/posts\/2336"}],"collection":[{"href":"https:\/\/blogs.mathworks.com\/cleve\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/blogs.mathworks.com\/cleve\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/blogs.mathworks.com\/cleve\/wp-json\/wp\/v2\/users\/78"}],"replies":[{"embeddable":true,"href":"https:\/\/blogs.mathworks.com\/cleve\/wp-json\/wp\/v2\/comments?post=2336"}],"version-history":[{"count":3,"href":"https:\/\/blogs.mathworks.com\/cleve\/wp-json\/wp\/v2\/posts\/2336\/revisions"}],"predecessor-version":[{"id":2354,"href":"https:\/\/blogs.mathworks.com\/cleve\/wp-json\/wp\/v2\/posts\/2336\/revisions\/2354"}],"wp:attachment":[{"href":"https:\/\/blogs.mathworks.com\/cleve\/wp-json\/wp\/v2\/media?parent=2336"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/blogs.mathworks.com\/cleve\/wp-json\/wp\/v2\/categories?post=2336"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/blogs.mathworks.com\/cleve\/wp-json\/wp\/v2\/tags?post=2336"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}