<p><div><div><div><div data-show-faces="false" data-height="21" data-width="100" data-layout="button_count" data-send="true" data-href="https://www.r-bloggers.com/solving-the-chinese-postman-problem/"></div></div><div></div></div><div></div></div>
<div>
(This article was first published on <strong><a href="https://freakonometrics.hypotheses.org/53694"> R-english – Freakonometrics</a></strong>, and kindly contributed to <a rel="nofollow" href="https://www.r-bloggers.com/">R-bloggers)</a> </div>
<p>Some pre-Halloween post today. It started actually while I was in Barcelona : kids wanted to go back to some store we’ve seen the first day, in the <a rel="nofollow" href="https://en.wikipedia.org/wiki/Gothic_Quarter,_Barcelona" target="_blank">gothic part</a>, and I could not remember where it was. And I said to myself that would be quite long to do all the street of the neighborhood. And I discovered that it was actually an old problem. In 1962, <a rel="nofollow" href="https://en.wikipedia.org/wiki/Meigu_Guan" target="_blank">Meigu Guan</a> was interested in a postman delivering mail to a number of streets such that the total distance walked by the postman was as short as possible. How could the postman ensure that the distance walked was a minimum?</p>
<p>A very close notion is the concept of <strong>traversable graph</strong>, which is one that can be drawn without taking a pen from the paper and without retracing the same edge. In such a case the graph is said to have an <strong>Eulerian trail </strong>(yes, from <a rel="nofollow" href="https://ethkim.github.io/TA/251/eulerian.pdf" target="_blank">Euler’s bridges problem</a>). An Eulerian trail uses all the edges of a graph. For a graph to be Eulerian <strong>all the vertices must be of even order</strong>.</p>
<p>An algorithm for finding an optimal Chinese postman route is:</p>
<ol>
<li>List all odd vertices.</li>
<li>List all possible pairings of odd vertices.</li>
<li>For each pairing find the edges that connect the vertices with the minimum weight.</li>
<li>Find the pairings such that the sum of the weights is minimised.</li>
<li>On the original graph add the edges that have been found in Step 4.</li>
<li>The length of an optimal Chinese postman route is the sum of all the edges added to the total found in Step 4.</li>
<li>A route corresponding to this minimum weight can then be easily found.</li>
</ol>
<p>For the first steps, we can use the codes from Hurley &amp; Oldford’s <a rel="nofollow" href="https://link.springer.com/article/10.1007/s00180-011-0229-5" target="_blank">Eulerian tour algorithms for data visualization and the PairViz package</a>. First, we have to load some R packages</p>
<div><table><tr><td><pre>1
2
3
4
</pre></td><td><pre><span>require</span><span>(</span>igraph<span>)</span>
<span>require</span><span>(</span>graph<span>)</span>
<span>require</span><span>(</span>eulerian<span>)</span>
<span>require</span><span>(</span>GA<span>)</span></pre></td></tr></table></div>
<p>Then use the following function from <a rel="nofollow" href="https://stackoverflow.com/questions/40576910/solving-chinese-postman-algorithm-with-eulerization" target="_blank">stackoverflow</a>,</p>
<div><table><tr><td><pre>1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
</pre></td><td><pre>make_eulerian <span>=</span> <span>function</span><span>(</span>graph<span>)</span><span>{</span>
  info <span>=</span> <span>c</span><span>(</span><span>&quot;broken&quot;</span> <span>=</span> FALSE, <span>&quot;Added&quot;</span> <span>=</span> <span>0</span>, <span>&quot;Successfull&quot;</span> <span>=</span> TRUE<span>)</span>
  is.<span>even</span> <span>=</span> <span>function</span><span>(</span>x<span>)</span><span>{</span> x <span>%%</span> <span>2</span> <span>==</span> <span>0</span> <span>}</span>
  search.<span>for</span>.<span>even</span>.<span>neighbor</span> <span>=</span> <span>!</span>is.<span>even</span><span>(</span><span>sum</span><span>(</span><span>!</span>is.<span>even</span><span>(</span>degree<span>(</span>graph<span>)</span><span>)</span><span>)</span><span>)</span>
  <span>for</span><span>(</span>i <span>in</span> V<span>(</span>graph<span>)</span><span>)</span><span>{</span>
    set.<span>j</span> <span>=</span> NULL
    uneven.<span>neighbors</span> <span>=</span> <span>!</span>is.<span>even</span><span>(</span>degree<span>(</span>graph, neighbors<span>(</span>graph,i<span>)</span><span>)</span><span>)</span> 
<span>if</span><span>(</span><span>!</span>is.<span>even</span><span>(</span>degree<span>(</span>graph,i<span>)</span><span>)</span><span>)</span><span>{</span> 
<span>if</span><span>(</span><span>sum</span><span>(</span>uneven.<span>neighbors</span><span>)</span> <span>==</span> <span>0</span><span>)</span><span>{</span> 
<span>if</span><span>(</span><span>sum</span><span>(</span><span>!</span>is.<span>even</span><span>(</span>degree<span>(</span>graph<span>)</span><span>)</span><span>)</span> <span>&amp;</span>gt<span>;</span> <span>0</span><span>)</span><span>{</span>
          info<span>[</span><span>&quot;Broken&quot;</span><span>]</span> <span>=</span> TRUE
          uneven.<span>candidates</span> <span>&amp;</span>lt<span>;-</span> <span>!</span>is.<span>even</span><span>(</span>degree<span>(</span>graph, V<span>(</span>graph<span>)</span><span>)</span><span>)</span>
          <span>if</span><span>(</span><span>sum</span><span>(</span>uneven.<span>candidates</span><span>)</span> <span>!=</span> <span>0</span><span>)</span><span>{</span>
            set.<span>j</span> <span>&amp;</span>lt<span>;-</span> V<span>(</span>graph<span>)</span><span>[</span>uneven.<span>candidates</span><span>]</span><span>[</span><span>[</span><span>1</span><span>]</span><span>]</span>
          <span>}</span><span>else</span><span>{</span>
            info<span>[</span><span>&quot;Successfull&quot;</span><span>]</span> <span>&amp;</span>lt<span>;-</span> FALSE
          <span>}</span>
        <span>}</span>       
      <span>}</span><span>else</span><span>{</span>
        set.<span>j</span> <span>&amp;</span>lt<span>;-</span> neighbors<span>(</span>graph, i<span>)</span><span>[</span>uneven.<span>neighbors</span><span>]</span><span>[</span><span>[</span><span>1</span><span>]</span><span>]</span>
      <span>}</span>
    <span>}</span><span>else</span> <span>if</span><span>(</span>search.<span>for</span>.<span>even</span>.<span>neighbor</span> <span>==</span> TRUE <span>&amp;</span>amp<span>;</span> <span>is.<span>null</span></span><span>(</span>set.<span>j</span><span>)</span><span>)</span><span>{</span>
      info<span>[</span><span>&quot;Added&quot;</span><span>]</span> <span>&amp;</span>lt<span>;-</span> info<span>[</span><span>&quot;Added&quot;</span><span>]</span> <span>+</span> <span>1</span>     
      set.<span>j</span> <span>&amp;</span>lt<span>;-</span> neighbors<span>(</span>graph, i<span>)</span><span>[</span> <span>!</span>uneven.<span>neighbors</span> <span>]</span><span>[</span><span>[</span><span>1</span><span>]</span><span>]</span>
      <span>if</span><span>(</span><span>!</span><span>is.<span>null</span></span><span>(</span>set.<span>j</span><span>)</span><span>)</span><span>{</span>search.<span>for</span>.<span>even</span>.<span>neighbor</span> <span>&amp;</span>lt<span>;-</span> FALSE<span>}</span>
    <span>}</span>
    <span>if</span><span>(</span><span>!</span><span>is.<span>null</span></span><span>(</span>set.<span>j</span><span>)</span><span>)</span><span>{</span>
      <span>if</span><span>(</span>i <span>!=</span> set.<span>j</span><span>)</span><span>{</span>
        graph <span>&amp;</span>lt<span>;-</span> add_edges<span>(</span>graph, edges<span>=</span><span>c</span><span>(</span>i, set.<span>j</span><span>)</span><span>)</span>
        info<span>[</span><span>&quot;Added&quot;</span><span>]</span> <span>&amp;</span>lt<span>;-</span> info<span>[</span><span>&quot;Added&quot;</span><span>]</span> <span>+</span> <span>1</span>
      <span>}</span>
    <span>}</span>
  <span>}</span>
  <span>(</span><span>list</span><span>(</span><span>&quot;graph&quot;</span> <span>=</span> graph, <span>&quot;info&quot;</span> <span>=</span> info<span>)</span><span>)</span><span>}</span></pre></td></tr></table></div>
<p>Then, consider some network, with 12 nodes</p>
<div><table><tr><td><pre>1
2
3
</pre></td><td><pre>g1 <span>=</span> graph<span>(</span><span>c</span><span>(</span><span>1</span>,<span>2</span>, <span>1</span>,<span>3</span>, <span>2</span>,<span>4</span>, <span>2</span>,<span>5</span>, <span>1</span>,<span>5</span>, <span>3</span>,<span>5</span>, 
<span>4</span>,<span>7</span>, <span>5</span>,<span>7</span>, <span>5</span>,<span>8</span>, <span>3</span>,<span>6</span>, <span>6</span>,<span>8</span>, <span>6</span>,<span>9</span>, <span>9</span>,<span>11</span>, <span>8</span>,<span>11</span>, 
<span>8</span>,<span>10</span>, <span>8</span>,<span>12</span>, <span>7</span>,<span>10</span>, <span>10</span>,<span>12</span>, <span>11</span>,<span>12</span><span>)</span>, directed <span>=</span> FALSE<span>)</span></pre></td></tr></table></div>
<p>To plot that network, use</p>
<div><table><tr><td><pre>1
2
3
4
</pre></td><td><pre>V<span>(</span>g1<span>)</span>$name<span>=</span><span>LETTERS</span><span>[</span><span>1</span><span>:</span><span>12</span><span>]</span>
V<span>(</span>g1<span>)</span>$color<span>=</span><span>rgb</span><span>(</span><span>0</span>,<span>0</span>,<span>1</span>,.4<span>)</span>
ly<span>=</span>layout.<span>kamada</span>.<span>kawai</span><span>(</span>g1<span>)</span>
<span>plot</span><span>(</span>g1,vertex.<span>color</span><span>=</span>V<span>(</span>newg<span>)</span>$color,<span>layout</span><span>=</span>ly<span>)</span></pre></td></tr></table></div>
<p><img src="https://i1.wp.com/f-origin.hypotheses.org/wp-content/blogs.dir/253/files/2018/07/chinois-1.png?resize=338%2C318&ssl=1" alt="" width="338" data-recalc-dims="1" height="318"> Then we convert it to some traversable graph by adding 5 vertices</p>
<div><table><tr><td><pre>1
2
3
4
5
</pre></td><td><pre>eulerian <span>=</span> make_eulerian<span>(</span>g1<span>)</span>
eulerian$info
     broken       Added Successfull 
          <span>0</span>           <span>5</span>           <span>1</span> 
g <span>=</span> eulerian$graph</pre></td></tr></table></div>
<p>as shown below</p>
<div><table><tr><td><pre>1
2
</pre></td><td><pre>ly<span>=</span>layout.<span>kamada</span>.<span>kawai</span><span>(</span>g<span>)</span>
<span>plot</span><span>(</span>g,vertex.<span>color</span><span>=</span>V<span>(</span>newg<span>)</span>$color,<span>layout</span><span>=</span>ly<span>)</span></pre></td></tr></table></div>
<p><img src="https://i0.wp.com/f-origin.hypotheses.org/wp-content/blogs.dir/253/files/2018/07/chinois-2.png?resize=338%2C318&ssl=1" alt="" width="338" data-recalc-dims="1" height="318">We cut those 5 vertices in two part, and therefore, we add 5 artificial nodes</p>
<div><table><tr><td><pre>1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
</pre></td><td><pre>A<span>=</span><span>as.<span>matrix</span></span><span>(</span>as_adj<span>(</span>g<span>)</span><span>)</span>
A1<span>=</span><span>as.<span>matrix</span></span><span>(</span>as_adj<span>(</span>g1<span>)</span><span>)</span>
newA<span>=</span><span>lower.<span>tri</span></span><span>(</span>A, <span>diag</span> <span>=</span> FALSE<span>)</span><span>*</span>A1<span>+</span><span>upper.<span>tri</span></span><span>(</span>A, <span>diag</span> <span>=</span> FALSE<span>)</span><span>*</span>A
<span>for</span><span>(</span>i <span>in</span> <span>1</span><span>:</span><span>sum</span><span>(</span>newA<span>==</span><span>2</span><span>)</span><span>)</span> newA <span>=</span> <span>cbind</span><span>(</span>newA,<span>0</span><span>)</span>
<span>for</span><span>(</span>i <span>in</span> <span>1</span><span>:</span><span>sum</span><span>(</span>newA<span>==</span><span>2</span><span>)</span><span>)</span> newA <span>=</span> <span>rbind</span><span>(</span>newA,<span>0</span><span>)</span>
s<span>=</span><span>nrow</span><span>(</span>A<span>)</span>
<span>for</span><span>(</span>i <span>in</span> <span>1</span><span>:</span><span>nrow</span><span>(</span>A<span>)</span><span>)</span><span>{</span>
  Aj<span>=</span><span>which</span><span>(</span>newA<span>[</span>i,<span>]</span><span>==</span><span>2</span><span>)</span>
  <span>if</span><span>(</span><span>!</span><span>is.<span>null</span></span><span>(</span>Aj<span>)</span><span>)</span><span>{</span>
      <span>for</span><span>(</span>j <span>in</span> Aj<span>)</span><span>{</span>
        newA<span>[</span>i,s<span>+</span><span>1</span><span>]</span><span>=</span>newA<span>[</span>s<span>+</span><span>1</span>,i<span>]</span><span>=</span><span>1</span>
        newA<span>[</span>j,s<span>+</span><span>1</span><span>]</span><span>=</span>newA<span>[</span>s<span>+</span><span>1</span>,j<span>]</span><span>=</span><span>1</span>
        newA<span>[</span>i,j<span>]</span><span>=</span><span>1</span>
        s<span>=</span>s<span>+</span><span>1</span>
      <span>}</span><span>}</span><span>}</span></pre></td></tr></table></div>
<p>We get the following graph, where all nodes have an even number of vertices !</p>
<div><table><tr><td><pre>1
2
3
4
5
6
7
8
9
10
11
12
</pre></td><td><pre>newg<span>=</span>graph_from_adjacency_matrix<span>(</span>newA<span>)</span>
newg<span>=</span>as.<span>undirected</span><span>(</span>newg<span>)</span>
V<span>(</span>newg<span>)</span>$name<span>=</span><span>LETTERS</span><span>[</span><span>1</span><span>:</span><span>17</span><span>]</span>
V<span>(</span>newg<span>)</span>$color<span>=</span><span>c</span><span>(</span><span>rep</span><span>(</span><span>rgb</span><span>(</span><span>0</span>,<span>0</span>,<span>1</span>,.4<span>)</span>,<span>12</span><span>)</span>,<span>rep</span><span>(</span><span>rgb</span><span>(</span><span>1</span>,<span>0</span>,<span>0</span>,.4<span>)</span>,<span>5</span><span>)</span><span>)</span>
ly2<span>=</span>ly
transl<span>=</span><span>cbind</span><span>(</span><span>c</span><span>(</span><span>0</span>,<span>0</span>,<span>0</span>,.2,<span>0</span><span>)</span>,<span>c</span><span>(</span>.2,<span>-</span>.2,<span>-</span>.2,<span>0</span>,<span>-</span>.2<span>)</span><span>)</span>
<span>for</span><span>(</span>i <span>in</span> <span>13</span><span>:</span><span>17</span><span>)</span><span>{</span>
  j<span>=</span><span>which</span><span>(</span>newA<span>[</span>i,<span>]</span><span>&amp;</span>gt<span>;</span><span>0</span><span>)</span>
  lc<span>=</span>ly<span>[</span>j,<span>]</span>
  ly2<span>=</span><span>rbind</span><span>(</span>ly2,<span>apply</span><span>(</span>lc,<span>2</span>,<span>mean</span><span>)</span><span>+</span>transl<span>[</span>i<span>-</span><span>12</span>,<span>]</span><span>)</span>
<span>}</span>
<span>plot</span><span>(</span>newg,<span>layout</span><span>=</span>ly2<span>)</span></pre></td></tr></table></div>
<p><img src="https://i1.wp.com/f-origin.hypotheses.org/wp-content/blogs.dir/253/files/2018/07/chinois-3.png?resize=338%2C318&ssl=1" alt="" width="338" data-recalc-dims="1" height="318"> Our network is now the following (new nodes are small because actually, they don’t really matter, it’s just for computational reasons)</p>
<div><table><tr><td><pre>1
2
3
</pre></td><td><pre><span>plot</span><span>(</span>newg,vertex.<span>color</span><span>=</span>V<span>(</span>newg<span>)</span>$color,<span>layout</span><span>=</span>ly2,
     vertex.<span>size</span><span>=</span><span>c</span><span>(</span><span>rep</span><span>(</span><span>20</span>,<span>12</span><span>)</span>,<span>rep</span><span>(</span><span>0</span>,<span>5</span><span>)</span><span>)</span>,
     vertex.<span>label</span>.<span>cex</span><span>=</span><span>c</span><span>(</span><span>rep</span><span>(</span><span>1</span>,<span>12</span><span>)</span>,<span>rep</span><span>(</span>.1,<span>5</span><span>)</span><span>)</span><span>)</span></pre></td></tr></table></div>
<p><img src="https://i0.wp.com/f-origin.hypotheses.org/wp-content/blogs.dir/253/files/2018/07/chinois-4.png?resize=266%2C282&ssl=1" alt="" width="266" data-recalc-dims="1" height="282"> Now we can get the optimal path</p>
<div><table><tr><td><pre>1
2
3
4
5
6
7
</pre></td><td><pre>n <span>&amp;</span>lt<span>;-</span> <span>LETTERS</span><span>[</span><span>1</span><span>:</span><span>nrow</span><span>(</span>newA<span>)</span><span>]</span>
g_2 <span>&amp;</span>lt<span>;-</span> <span>new</span><span>(</span><span>&quot;graphNEL&quot;</span>,nodes<span>=</span>n<span>)</span> <span>for</span><span>(</span>i <span>in</span> <span>1</span><span>:</span><span>nrow</span><span>(</span>newA<span>)</span><span>)</span><span>{</span> <span>for</span><span>(</span>j <span>in</span> <span>which</span><span>(</span>newA<span>[</span>i,<span>]</span><span>&amp;</span>gt<span>;</span><span>0</span><span>)</span><span>)</span><span>{</span>
    g_2 <span>&amp;</span>lt<span>;-</span> addEdge<span>(</span>n<span>[</span>i<span>]</span>,n<span>[</span>j<span>]</span>,g_2,<span>1</span><span>)</span> 
  <span>}</span><span>}</span>
etour<span>(</span>g_2,weighted<span>=</span>FALSE<span>)</span>
 <span>[</span><span>1</span><span>]</span> <span>&quot;A&quot;</span> <span>&quot;B&quot;</span> <span>&quot;D&quot;</span> <span>&quot;G&quot;</span> <span>&quot;E&quot;</span> <span>&quot;A&quot;</span> <span>&quot;C&quot;</span> <span>&quot;E&quot;</span> <span>&quot;H&quot;</span> <span>&quot;F&quot;</span> <span>&quot;I&quot;</span> <span>&quot;K&quot;</span> <span>&quot;H&quot;</span> <span>&quot;J&quot;</span> <span>&quot;G&quot;</span> <span>&quot;P&quot;</span> <span>&quot;J&quot;</span> <span>&quot;L&quot;</span> <span>&quot;K&quot;</span> <span>&quot;Q&quot;</span> <span>&quot;L&quot;</span> <span>&quot;H&quot;</span> <span>&quot;O&quot;</span> <span>&quot;F&quot;</span> <span>&quot;C&quot;</span>
<span>[</span><span>26</span><span>]</span> <span>&quot;N&quot;</span> <span>&quot;E&quot;</span> <span>&quot;B&quot;</span> <span>&quot;M&quot;</span> <span>&quot;A&quot;</span></pre></td></tr></table></div>
<p>or</p>
<div><table><tr><td><pre>1
2
3
4
5
6
7
8
9
10
11
12
13
14
</pre></td><td><pre>edg<span>=</span><span>attr</span><span>(</span>E<span>(</span>newg<span>)</span>, <span>&quot;vnames&quot;</span><span>)</span>
ET<span>=</span>etour<span>(</span>g_2,weighted<span>=</span>FALSE<span>)</span>
parcours<span>=</span>trajet<span>=</span><span>rep</span><span>(</span>NA,<span>length</span><span>(</span>ET<span>)</span><span>-</span><span>1</span><span>)</span>
<span>for</span><span>(</span>i <span>in</span> <span>1</span><span>:</span><span>length</span><span>(</span>parcours<span>)</span><span>)</span><span>{</span>
  u<span>=</span><span>c</span><span>(</span>ET<span>[</span>i<span>]</span>,ET<span>[</span>i<span>+</span><span>1</span><span>]</span><span>)</span>
  ou<span>=</span><span>order</span><span>(</span>u<span>)</span>
  parcours<span>[</span>i<span>]</span><span>=</span><span>paste</span><span>(</span>u<span>[</span>ou<span>[</span><span>1</span><span>]</span><span>]</span>,u<span>[</span>ou<span>[</span><span>2</span><span>]</span><span>]</span>,sep<span>=</span><span>&quot;|&quot;</span><span>)</span>
  trajet<span>[</span>i<span>]</span><span>=</span><span>which</span><span>(</span>edg<span>==</span>parcours<span>[</span>i<span>]</span><span>)</span>
<span>}</span>
parcours
 <span>[</span><span>1</span><span>]</span> <span>&quot;A|B&quot;</span> <span>&quot;B|D&quot;</span> <span>&quot;D|G&quot;</span> <span>&quot;E|G&quot;</span> <span>&quot;A|E&quot;</span> <span>&quot;A|C&quot;</span> <span>&quot;C|E&quot;</span> <span>&quot;E|H&quot;</span> <span>&quot;F|H&quot;</span> <span>&quot;F|I&quot;</span> <span>&quot;I|K&quot;</span> <span>&quot;H|K&quot;</span> <span>&quot;H|J&quot;</span> <span>&quot;G|J&quot;</span> <span>&quot;G|P&quot;</span> <span>&quot;J|P&quot;</span>
<span>[</span><span>17</span><span>]</span> <span>&quot;J|L&quot;</span> <span>&quot;K|L&quot;</span> <span>&quot;K|Q&quot;</span> <span>&quot;L|Q&quot;</span> <span>&quot;H|L&quot;</span> <span>&quot;H|O&quot;</span> <span>&quot;F|O&quot;</span> <span>&quot;C|F&quot;</span> <span>&quot;C|N&quot;</span> <span>&quot;E|N&quot;</span> <span>&quot;B|E&quot;</span> <span>&quot;B|M&quot;</span> <span>&quot;A|M&quot;</span>
trajet
 <span>[</span><span>1</span><span>]</span>  <span>1</span>  <span>3</span>  <span>8</span>  <span>9</span>  <span>4</span>  <span>2</span>  <span>6</span> <span>10</span> <span>11</span> <span>12</span> <span>16</span> <span>15</span> <span>14</span> <span>13</span> <span>26</span> <span>27</span> <span>18</span> <span>19</span> <span>28</span> <span>29</span> <span>17</span> <span>25</span> <span>24</span>  <span>7</span> <span>22</span> <span>23</span>  <span>5</span> <span>21</span> <span>20</span></pre></td></tr></table></div>
<p><img alt="" src="https://i1.wp.com/f-origin.hypotheses.org/wp-content/blogs.dir/253/files/2018/07/dessin-chinois-network.gif?w=456&ssl=1" data-recalc-dims="1"></p>
<p>Let us try now on a real network of streets. Like <a rel="nofollow" href="https://en.wikipedia.org/wiki/Missoula,_Montana" target="_blank">Missoula</a>, Montana.</p>
<p><img alt="" src="https://i2.wp.com/f-origin.hypotheses.org/wp-content/blogs.dir/253/files/2018/07/Missoula-Montana_US.png?w=456&ssl=1" data-recalc-dims="1"></p>
<p>I will not try to get the shapefile of the city, I will just try to replicate the photography above.</p>
<p><img src="https://i0.wp.com/freakonometrics.hypotheses.org/files/2018/10/net1.png?resize=300%2C285&ssl=1" alt="" width="300" data-recalc-dims="1" height="285"></p>
<p>If you look carefully, you will see some problem : 10 and 93 have an odd number of vertices (3 here), so one strategy is to connect them (which explains the grey line).</p>
<p><img src="https://i1.wp.com/freakonometrics.hypotheses.org/files/2018/10/net2.png?resize=321%2C315&ssl=1" alt="" width="321" data-recalc-dims="1" height="315"></p>
<p>But actually, to be more realistic, we start in 93, and we end in 10. Here is the optimal (shortest) path which goes through all vertices.</p>
<p><img alt="" src="https://i1.wp.com/freakonometrics.hypotheses.org/files/2018/10/dessin-chinois-network-v3.gif?w=456&ssl=1" data-recalc-dims="1"></p>
<p>Now, we are ready for Halloween, to go through all streets in the neighborhood !</p>
	<p>
<div>
<div>To <strong>leave a comment</strong> for the author, please follow the link and comment on their blog: <strong><a href="https://freakonometrics.hypotheses.org/53694"> R-english – Freakonometrics</a></strong>.</div>
<hr>
<a rel="nofollow" href="https://www.r-bloggers.com/">R-bloggers.com</a> offers <strong><a rel="nofollow" href="https://feedburner.google.com/fb/a/mailverify?uri=RBloggers">daily e-mail updates</a></strong> about <a rel="nofollow" href="https://www.r-project.org/" title="The R Project for Statistical Computing">R</a> news and <a rel="nofollow" href="https://www.r-bloggers.com/search/tutorial" title="R tutorials">tutorials</a> on topics such as: <a rel="nofollow" href="https://www.r-bloggers.com/search/data%20science" title="Data science">Data science</a>, <a rel="nofollow" href="https://www.r-bloggers.com/search/Big%20Data" title="Big Data">Big Data, <a rel="nofollow" href="https://www.r-users.com/" title="R jobs">R jobs</a>, visualization (<a rel="nofollow" href="https://www.r-bloggers.com/search/ggplot2" title="ggplot and ggplot2 tutorials">ggplot2</a>, <a rel="nofollow" href="https://www.r-bloggers.com/search/boxplot" title="Boxplots using lattice and ggplot2 tutorials">Boxplots</a>, <a rel="nofollow" href="https://www.r-bloggers.com/search/map" title="Maps and gis">maps</a>, <a rel="nofollow" href="https://www.r-bloggers.com/search/animation" title="Animation in R">animation</a>), programming (<a rel="nofollow" href="https://www.r-bloggers.com/search/RStudio" title="RStudio IDE for R">RStudio</a>, <a rel="nofollow" href="https://www.r-bloggers.com/search/sweave" title="Sweave and literate programming">Sweave</a>, <a rel="nofollow" href="https://www.r-bloggers.com/search/LaTeX" title="LaTeX in R">LaTeX</a>, <a rel="nofollow" href="https://www.r-bloggers.com/search/SQL" title="SQL and databases">SQL</a>, <a rel="nofollow" href="https://www.r-bloggers.com/search/eclipse" title="Eclipse IDE for R">Eclipse</a>, <a rel="nofollow" href="https://www.r-bloggers.com/search/git" title="git and github, Version Control System">git</a>, <a rel="nofollow" href="https://www.r-bloggers.com/search/hadoop" title="Large data in R using Hadoop">hadoop</a>, <a rel="nofollow" href="https://www.r-bloggers.com/search/Web+Scraping" title="Web Scraping of google, facebook, yahoo, twitter and more using R">Web Scraping</a>) statistics (<a rel="nofollow" href="https://www.r-bloggers.com/search/regression" title="Regressions and ANOVA analysis tutorials">regression</a>, <a rel="nofollow" href="https://www.r-bloggers.com/search/PCA" title="principal component analysis tutorial">PCA</a>, <a rel="nofollow" href="https://www.r-bloggers.com/search/time+series" title="Time series">time series</a>, <a rel="nofollow" href="https://www.r-bloggers.com/search/trading" title="finance trading">trading</a>) and more...
<img width="1" alt="" src="http://feeds.feedburner.com/~r/RBloggers/~4/1mANQ0gkVeU" height="1"></a></div>