{"id":3769,"date":"2018-09-03T12:00:33","date_gmt":"2018-09-03T17:00:33","guid":{"rendered":"https:\/\/blogs.mathworks.com\/cleve\/?p=3769"},"modified":"2018-09-10T19:17:38","modified_gmt":"2018-09-11T00:17:38","slug":"graph-object-of-48-usa-states","status":"publish","type":"post","link":"https:\/\/blogs.mathworks.com\/cleve\/2018\/09\/03\/graph-object-of-48-usa-states\/","title":{"rendered":"Graph Object of 48 USA States"},"content":{"rendered":"<div class=\"content\"><!--introduction--><p>Create a MATLAB&reg; graph object from information about neighbors among the 48 contiguous states in the USA.<\/p><!--\/introduction--><h3>Contents<\/h3><div><ul><li><a href=\"#d449fce8-b172-4c52-99a1-288cf3f3dcab\">Car Talk Puzzler<\/a><\/li><li><a href=\"#53fe7612-4a5e-4d23-a1ca-13fe3e76d71a\">States<\/a><\/li><li><a href=\"#f9cd9f27-d722-45a6-ad11-06932ba6a70b\">Neighboring States<\/a><\/li><li><a href=\"#d74eec29-698b-4954-ba9f-0e3d75065aed\">Most Neighbors<\/a><\/li><li><a href=\"#62f15a37-7396-4a33-8f65-16a609d14bb1\">Fewest Neighbors<\/a><\/li><li><a href=\"#2098d134-0036-4f49-a83f-a3c5cc28ada5\">Graph<\/a><\/li><li><a href=\"#b8a20a67-f70e-416e-b590-87253b17aea5\">Next<\/a><\/li><li><a href=\"#fa19ae2b-5c45-4700-a4ee-d2561216d2cd\">Thanks<\/a><\/li><\/ul><\/div><h4>Car Talk Puzzler<a name=\"d449fce8-b172-4c52-99a1-288cf3f3dcab\"><\/a><\/h4><p>A few years ago, MathWorks asked Tom and Ray Magliozzi, MIT alumni and hosts of the popular show Car Talk on National Public Radio, to come to our offices and meet some visiting students. They said yes on one condition.  They figured MathWorkers would be a good source of new material for the puzzler segment of their show. It turned out that we had only one puzzle to offer that they hadn't heard before.  But one was enough, and they came for the visit.<\/p><p>Here is that puzzle.<\/p><p>\r\n<p style=\"margin-left:3ex;\">\r\n<i>\r\nMy friend tells me that she is about to take a road trip.\r\nShe plans to visit each of the 48 contiguous states in the\r\nUSA exactly once.  She tells me she is going to start someplace\r\nin the West and doesn't tell me where she is going to finish.\r\nHowever, I am able to agree to meet her in the last state she\r\nwill visit.  Which state is that?\r\n<\/i>\r\n<\/p>\r\n<\/p><p>I will reveal the state later in this post, but try to answer the puzzle before I do.  (Readers who are not familiar with USA geography don't have to worry -- few Americans can provide the answer.)<\/p><h4>States<a name=\"53fe7612-4a5e-4d23-a1ca-13fe3e76d71a\"><\/a><\/h4><p>The <a href=\"https:\/\/people.sc.fsu.edu\/~jburkardt\">web site of John Burkardt<\/a> at Florida State University is a tremendous repository of software, data sets and other goodies.  I am going to use <a href=\"https:\/\/people.sc.fsu.edu\/~jburkardt\/datasets\/states\/state_neighbors.txt\">state neighbors<\/a>. The first column in this file provides the two-letter abbreviations of the names of the 48 contiguous states.<\/p><pre class=\"codeinput\">    S = get_state_neighbors;\r\n    names = S{:,1};\r\n    fmt = [repmat(<span class=\"string\">'%s '<\/span>,1,16) <span class=\"string\">'\\n'<\/span>];\r\n    fprintf(fmt,names)\r\n<\/pre><pre class=\"codeoutput\">AL AZ AR CA CO CT DE FL GA ID IL IN IA KS KY LA \r\nME MD MA MI MN MS MO MT NE NV NH NJ NM NY NC ND \r\nOH OK OR PA RI SC SD TN TX UT VT VA WA WV WI WY \r\n<\/pre><p>The list is ordered alphabetically by the full state name, so Wyoming is last.<\/p><pre class=\"codeinput\">    last = names(end)\r\n<\/pre><pre class=\"codeoutput\">last = \r\n    \"WY\"\r\n<\/pre><h4>Neighboring States<a name=\"f9cd9f27-d722-45a6-ad11-06932ba6a70b\"><\/a><\/h4><p>Burkardt's data also gives us the neighbors of each state.  We can form an adjacency matrix <tt>A<\/tt> where <tt>A(i,j)<\/tt> is one if states <tt>i<\/tt> and <tt>j<\/tt> share a common border and zero otherwise.<\/p><pre class=\"codeinput\">    A = adjacency(S);\r\n<\/pre><p>For example, Wyoming has six neighbors.<\/p><pre class=\"codeinput\">    last_neighbors = names(A(end,:))\r\n<\/pre><pre class=\"codeoutput\">last_neighbors = \r\n  6&times;1 string array\r\n    \"CO\"\r\n    \"ID\"\r\n    \"MT\"\r\n    \"NE\"\r\n    \"SD\"\r\n    \"UT\"\r\n<\/pre><p>Every good adjacency deserves a <tt>spy<\/tt> plot.<\/p><pre class=\"codeinput\">    spy(A)\r\n<\/pre><img decoding=\"async\" vspace=\"5\" hspace=\"5\" src=\"http:\/\/blogs.mathworks.com\/cleve\/files\/usa_blog_1_01.png\" alt=\"\"> <p>The last row (and column) has six nonzeros for Wyoming's six neighbors.<\/p><h4>Most Neighbors<a name=\"d74eec29-698b-4954-ba9f-0e3d75065aed\"><\/a><\/h4><p>Which states have the most neighbors?<\/p><pre class=\"codeinput\">    num_neigh = sum(A);\r\n    max_num_neigh = max(num_neigh)\r\n    max_neigh = names(num_neigh == max_num_neigh)\r\n<\/pre><pre class=\"codeoutput\">max_num_neigh =\r\n     8\r\nmax_neigh = \r\n  2&times;1 string array\r\n    \"MO\"\r\n    \"TN\"\r\n<\/pre><p>Missouri and Tennessee each have eight neighbors.<\/p><h4>Fewest Neighbors<a name=\"62f15a37-7396-4a33-8f65-16a609d14bb1\"><\/a><\/h4><p>Which state has the fewest neighbors?<\/p><pre class=\"codeinput\">    min_num_neigh = min(num_neigh)\r\n    min_neigh = names(num_neigh == min_num_neigh)\r\n<\/pre><pre class=\"codeoutput\">min_num_neigh =\r\n     1\r\nmin_neigh = \r\n    \"ME\"\r\n<\/pre><p>Maine has only one neighbor, namely New Hampshire. This provides the answer to the <a href=\"https:\/\/www.cartalk.com\/puzzler\/bobos-dont-look-back-tour\">MathWorks Car Talk puzzle<\/a>. My friend's trip must either start or finish in in Maine. Once she's in Maine, she can't leave without going through New Hampshire.  Since she is starting in the West, she must finish in Maine.<\/p><h4>Graph<a name=\"2098d134-0036-4f49-a83f-a3c5cc28ada5\"><\/a><\/h4><p>Every adjacency matrix also has an associated graph.<\/p><pre class=\"codeinput\">    G = graph(A,cellstr(names))\r\n<\/pre><pre class=\"codeoutput\">G = \r\n  graph with properties:\r\n\r\n    Edges: [105&times;1 table]\r\n    Nodes: [48&times;1 table]\r\n<\/pre><p>The default layout for plotting this graph is <tt>force<\/tt>, which uses attractive and repulsive forces on the nodes.<\/p><pre class=\"codeinput\">    plot(G)\r\n<\/pre><img decoding=\"async\" vspace=\"5\" hspace=\"5\" src=\"http:\/\/blogs.mathworks.com\/cleve\/files\/usa_blog_1_02.png\" alt=\"\"> <p>Interchange the axes by switching the viewpoint.<\/p><pre class=\"codeinput\">    view(-90,-90)\r\n<\/pre><img decoding=\"async\" vspace=\"5\" hspace=\"5\" src=\"http:\/\/blogs.mathworks.com\/cleve\/files\/usa_blog_1_03.png\" alt=\"\"> <p>The plot now resembles the United States.  California, Oregon and Washington are on the west coast.  Florida is a peninsula in the southeast.  The New England states dominate the northeast.  MO and TN show off their many neighbors.<\/p><p>Utah, Arizona, New Mexico and Colorado are the corners of one of two quadrilaterals in the graph, mimicking their actual meeting at Four Corners.  The other quadrilateral involves the four states that surround Lake Michigan.<\/p><p>All this without any coordinates, just knowing the connectivity of neighboring states.<\/p><h4>Next<a name=\"b8a20a67-f70e-416e-b590-87253b17aea5\"><\/a><\/h4><p>My next post will add the coordinates of the state capitals and tackle the classic Traveling Salesman Problem.<\/p><h4>Thanks<a name=\"fa19ae2b-5c45-4700-a4ee-d2561216d2cd\"><\/a><\/h4><p>Thanks to John Burkhardt for his data sets and for pointing out that the wording of the puzzle needs to preclude starting in Maine.<\/p><script language=\"JavaScript\"> <!-- \r\n    function grabCode_09e8672af2a54201aaf5e6a788e26df1() {\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='09e8672af2a54201aaf5e6a788e26df1 ' + '##### ' + 'SOURCE BEGIN' + ' #####';\r\n        t2='##### ' + 'SOURCE END' + ' #####' + ' 09e8672af2a54201aaf5e6a788e26df1';\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 2018 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_09e8672af2a54201aaf5e6a788e26df1()\"><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; R2018a<br><\/p><\/div><!--\r\n09e8672af2a54201aaf5e6a788e26df1 ##### SOURCE BEGIN #####\r\n%% Graph Object of 48 USA States\r\n% Create a MATLAB(R) graph object from information about\r\n% neighbors among the 48 contiguous states in the USA.\r\n \r\n%% Car Talk Puzzler\r\n% A few years ago, MathWorks asked Tom and Ray Magliozzi, MIT alumni\r\n% and hosts of the popular show Car Talk on National Public Radio,\r\n% to come to our offices and meet some visiting students.  \r\n% They said yes on one condition.  They figured MathWorkers would be\r\n% a good source of new material for the puzzler segment of their show.\r\n% It turned out that we had only one puzzle to offer that they hadn't\r\n% heard before.  But one was enough, and they came for the visit.\r\n%\r\n% Here is that puzzle.\r\n%\r\n% <html>\r\n% <p style=\"margin-left:3ex;\">\r\n% <i>\r\n% My friend tells me that she is about to take a road trip.\r\n% She plans to visit each of the 48 contiguous states in the \r\n% USA exactly once.  She tells me she is going to start someplace\r\n% in the West and doesn't tell me where she is going to finish.\r\n% However, I am able to agree to meet her in the last state she\r\n% will visit.  Which state is that?\r\n% <\/i>\r\n% <\/p>\r\n% <\/html>\r\n\r\n%%\r\n% I will reveal the state later in this post, but try to answer the\r\n% puzzle before I do.  (Readers who are not familiar with USA\r\n% geography don't have to worry REPLACE_WITH_DASH_DASH few Americans can provide the answer.)\r\n\r\n%% States\r\n% The <https:\/\/people.sc.fsu.edu\/~jburkardt\r\n% web site of John Burkardt> at Florida State University\r\n% is a tremendous repository of software, data sets and other\r\n% goodies.  I am going to use\r\n% <https:\/\/people.sc.fsu.edu\/~jburkardt\/datasets\/states\/state_neighbors.txt\r\n% state neighbors>.\r\n% The first column in this file provides the two-letter abbreviations \r\n% of the names of the 48 contiguous states.\r\n \r\n    S = get_state_neighbors;\r\n    names = S{:,1};\r\n    fmt = [repmat('%s ',1,16) '\\n'];\r\n    fprintf(fmt,names)\r\n    \r\n%%\r\n% The list is ordered alphabetically by the full state name, so\r\n% Wyoming is last.\r\n\r\n    last = names(end)\r\n\r\n%% Neighboring States\r\n% Burkardt's data also gives us the neighbors of each state.  We can form\r\n% an adjacency matrix |A| where |A(i,j)| is one if states |i| and |j|\r\n% share a common border and zero otherwise.\r\n\r\n    A = adjacency(S);\r\n    \r\n%%\r\n% For example, Wyoming has six neighbors.\r\n\r\n    last_neighbors = names(A(end,:))\r\n    \r\n%%\r\n% Every good adjacency deserves a |spy| plot.\r\n\r\n    spy(A)\r\n    \r\n%%\r\n% The last row (and column) has six nonzeros for Wyoming's six\r\n% neighbors.\r\n\r\n%% Most Neighbors\r\n% Which states have the most neighbors?\r\n\r\n    num_neigh = sum(A);\r\n    max_num_neigh = max(num_neigh)\r\n    max_neigh = names(num_neigh == max_num_neigh)\r\n\r\n%%\r\n% Missouri and Tennessee each have eight neighbors.\r\n\r\n%% Fewest Neighbors\r\n% Which state has the fewest neighbors?\r\n\r\n    min_num_neigh = min(num_neigh)\r\n    min_neigh = names(num_neigh == min_num_neigh)\r\n    \r\n%%\r\n% Maine has only one neighbor, namely New Hampshire.\r\n% This provides the answer to the\r\n% <https:\/\/www.cartalk.com\/puzzler\/bobos-dont-look-back-tour\r\n% MathWorks Car Talk puzzle>.\r\n% My friend's trip must either start or finish in in Maine.\r\n% Once she's in Maine, she can't leave without going through\r\n% New Hampshire.  Since she is starting in the West, she must\r\n% finish in Maine.\r\n\r\n%% Graph\r\n% Every adjacency matrix also has an associated graph. \r\n\r\n    G = graph(A,cellstr(names))\r\n    \r\n%%\r\n% The default layout for plotting this graph is |force|,\r\n% which uses attractive and repulsive forces on the nodes.\r\n\r\n    plot(G)\r\n    \r\n%%\r\n% Interchange the axes by switching the viewpoint.\r\n\r\n    view(-90,-90)\r\n    \r\n%%\r\n% The plot now resembles the United States.  California, Oregon\r\n% and Washington are on the west coast.  Florida is a peninsula\r\n% in the southeast.  The New England states dominate the\r\n% northeast.  MO and TN show off their many neighbors.\r\n%\r\n% Utah, Arizona, New Mexico and Colorado are the corners of one of\r\n% two quadrilaterals in the graph, mimicking their actual meeting\r\n% at Four Corners.  The other quadrilateral involves the\r\n% four states that surround Lake Michigan.\r\n%\r\n% All this without any coordinates, just knowing the connectivity\r\n% of neighboring states.\r\n\r\n%% Next\r\n% My next post will add the coordinates of the state\r\n% capitals and tackle the classic Traveling Salesman Problem.\r\n\r\n%% Thanks\r\n% Thanks to John Burkhardt for his data sets and for pointing out\r\n% that the wording of the puzzle needs to preclude starting in Maine.\r\n##### SOURCE END ##### 09e8672af2a54201aaf5e6a788e26df1\r\n-->","protected":false},"excerpt":{"rendered":"<div class=\"overview-image\"><img src=\"https:\/\/blogs.mathworks.com\/cleve\/files\/usa_blog_1_03-1.png\" class=\"img-responsive attachment-post-thumbnail size-post-thumbnail wp-post-image\" alt=\"\" decoding=\"async\" loading=\"lazy\" \/><\/div><!--introduction--><p>Create a MATLAB&reg; graph object from information about neighbors among the 48 contiguous states in the USA.... <a class=\"read-more\" href=\"https:\/\/blogs.mathworks.com\/cleve\/2018\/09\/03\/graph-object-of-48-usa-states\/\">read more >><\/a><\/p>","protected":false},"author":78,"featured_media":3815,"comment_status":"open","ping_status":"closed","sticky":false,"template":"","format":"standard","meta":[],"categories":[23,4],"tags":[],"_links":{"self":[{"href":"https:\/\/blogs.mathworks.com\/cleve\/wp-json\/wp\/v2\/posts\/3769"}],"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=3769"}],"version-history":[{"count":5,"href":"https:\/\/blogs.mathworks.com\/cleve\/wp-json\/wp\/v2\/posts\/3769\/revisions"}],"predecessor-version":[{"id":3803,"href":"https:\/\/blogs.mathworks.com\/cleve\/wp-json\/wp\/v2\/posts\/3769\/revisions\/3803"}],"wp:featuredmedia":[{"embeddable":true,"href":"https:\/\/blogs.mathworks.com\/cleve\/wp-json\/wp\/v2\/media\/3815"}],"wp:attachment":[{"href":"https:\/\/blogs.mathworks.com\/cleve\/wp-json\/wp\/v2\/media?parent=3769"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/blogs.mathworks.com\/cleve\/wp-json\/wp\/v2\/categories?post=3769"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/blogs.mathworks.com\/cleve\/wp-json\/wp\/v2\/tags?post=3769"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}