Example use of FindHamiltonianCycle[...] Mathematica graph algorithm (JSCAD)

Print view

1 post • Page 1 of 1

User avatar HermannSW: Posts: 6583; Joined: Fri Jul 22, 2016 9:09 pm

Example use of FindHamiltonianCycle[...] Mathematica graph algorithm (JSCAD)

Quote

Thu May 29, 2025 11:33 am

In this thread I wrote about first experiences with Wolfram language:
viewtopic.php?t=352146

And this Raspberry license:
https://www.wolfram.com/legal/agreement ... pberry-pi/

Permitted Uses and Installations
Subject to the terms of this Agreement and Your acceptance thereof, WRI grants You a non-exclusive license to use the Product solely for personal or educational purposes on a Raspberry Pi computer.

Yesterday I was at Heidelberg University and saw this sculpture in front of Mathematikon building:
(I entered passive phase of early retirement at age of 60 after 30 years at IBM, will become student of Mathematics in 10/2025)

IMG_20250528_115410_HDR.part.20pc.jpg: IMG_20250528_115410_HDR.part.20pc.jpg; IMG_20250528_115410_HDR.part.20pc.jpg (58.87 KiB) Viewed 6213 times

I noticed that it is a Hamiltonian Cycle of C60 or football fullerene graph:

330px-Comparison_of_truncated_icosahedron_and_soccer_ball.webp.jpg: 330px-Comparison_of_truncated_icosahedron_and_soccer_ball.webp.jpg; 330px-Comparison_of_truncated_icosahedron_and_soccer_ball.webp.jpg (10.83 KiB) Viewed 6213 times

I wanted to create a JSCAD model of it, but did not want to specify all vertices.
So I created the vertices from three golden ratio related vectors:
https://gist.github.com/Hermann-SW/981f ... cad-L9-L25

Then I did not want to specify between which pairs of the 60 vertices edges exist.
I used the fact that the edge length is exactly 2 for the given vertex coordinates to determine the 90 edges:
https://gist.github.com/Hermann-SW/981f ... ad-L27-L43

That allowed to draw the complete C60 with all edges.
Again I did not want to specify which 30 edges are not part of a Hamiltonian Cycle of C60.
The first plan was to implement Hamiltonian Cycle finding algorithm in JSCAD script.
But then I realized that Mathematica has the algorithm for use:
https://reference.wolfram.com/language/ ... Cycle.html

So in JSCAD script I did log a Mathematica command to console ...
https://gist.github.com/Hermann-SW/981f ... ad-L70-L76

... did run from browser log with wolframscript and then used the result. This is the model to play with in your browser:
https://jscad.app/#https://gist.githubu ... ycle.jscad

C60.Hamilton_Cycle.jpg: C60.Hamilton_Cycle.jpg; C60.Hamilton_Cycle.jpg (77.21 KiB) Viewed 6213 times

Later I learned from doc that 2nd arg "All" allows to determine all (1090) Hamiltonian Cycles:

Code: Select all

pi@raspberrypi5:~ $ wolframscript 
Wolfram Language 14.1.0 Engine for Linux ARM (64-bit)
Copyright 1988-2024 Wolfram Research, Inc.
In[1]:= HCs=FindHamiltonianCycle[Graph[{UndirectedEdge[0,2],UndirectedEdge[0,36]
,UndirectedEdge[0,40],UndirectedEdge[1,3],UndirectedEdge[1,37],UndirectedEdge[1,
41],UndirectedEdge[2,38],UndirectedEdge[2,42],UndirectedEdge[3,39],UndirectedEdg
e[3,43],UndirectedEdge[4,6],UndirectedEdge[4,44],UndirectedEdge[4,45],Undirected
Edge[5,7],UndirectedEdge[5,46],UndirectedEdge[5,47],UndirectedEdge[6,48],Undirec
tedEdge[6,49],UndirectedEdge[7,50],UndirectedEdge[7,51],UndirectedEdge[8,9],Undi
rectedEdge[8,52],UndirectedEdge[8,54],UndirectedEdge[9,53],UndirectedEdge[9,55],
UndirectedEdge[10,11],UndirectedEdge[10,56],UndirectedEdge[10,58],UndirectedEdge
[11,57],UndirectedEdge[11,59],UndirectedEdge[12,16],UndirectedEdge[12,36],Undire
ctedEdge[12,44],UndirectedEdge[13,17],UndirectedEdge[13,37],UndirectedEdge[13,45
],UndirectedEdge[14,18],UndirectedEdge[14,38],UndirectedEdge[14,46],UndirectedEd
ge[15,19],UndirectedEdge[15,39],UndirectedEdge[15,47],UndirectedEdge[16,40],Undi
rectedEdge[16,48],UndirectedEdge[17,41],UndirectedEdge[17,49],UndirectedEdge[18,
42],UndirectedEdge[18,50],UndirectedEdge[19,43],UndirectedEdge[19,51],Undirected
Edge[20,21],UndirectedEdge[20,44],UndirectedEdge[20,52],UndirectedEdge[21,45],Un
directedEdge[21,53],UndirectedEdge[22,23],UndirectedEdge[22,46],UndirectedEdge[2
2,54],UndirectedEdge[23,47],UndirectedEdge[23,55],UndirectedEdge[24,25],Undirect
edEdge[24,48],UndirectedEdge[24,56],UndirectedEdge[25,49],UndirectedEdge[25,57],
UndirectedEdge[26,27],UndirectedEdge[26,50],UndirectedEdge[26,58],UndirectedEdge
[27,51],UndirectedEdge[27,59],UndirectedEdge[28,30],UndirectedEdge[28,36],Undire
ctedEdge[28,52],UndirectedEdge[29,31],UndirectedEdge[29,37],UndirectedEdge[29,53
],UndirectedEdge[30,38],UndirectedEdge[30,54],UndirectedEdge[31,39],UndirectedEd
ge[31,55],UndirectedEdge[32,34],UndirectedEdge[32,40],UndirectedEdge[32,56],Undi
rectedEdge[33,35],UndirectedEdge[33,41],UndirectedEdge[33,57],UndirectedEdge[34,
42],UndirectedEdge[34,58],UndirectedEdge[35,43],UndirectedEdge[35,59]}],All]; 
In[2]:= Length[HCs] 
Out[2]= 1090
In[3]:= HCs[[1]] 
Out[3]= {0  36, 36  28, 28  52, 52  8, 8  9, 9  55, 
 
> 55  31, 31  39, 39  3, 3  43, 43  35, 35  59, 
 
> 59  27, 27  26, 26  50, 50  18, 18  14, 14  46, 
 
> 46  5, 5  7, 7  51, 51  19, 19  15, 15  47, 47  23, 
 
> 23  22, 22  54, 54  30, 30  38, 38  2, 2  42, 
 
> 42  34, 34  58, 58  10, 10  11, 11  57, 57  33, 
 
> 33  41, 41  1, 1  37, 37  29, 29  53, 53  21, 
 
> 21  20, 20  44, 44  12, 12  16, 16  48, 48  6, 6  4, 
 
> 4  45, 45  13, 13  17, 17  49, 49  25, 25  24, 
 
> 24  56, 56  32, 32  40, 40  0}
In[4]:= HCs[[1090]] 
Out[4]= {0  2, 2  38, 38  14, 14  18, 18  42, 42  34, 
 
> 34  32, 32  40, 40  16, 16  48, 48  24, 24  56, 
 
> 56  10, 10  58, 58  26, 26  50, 50  7, 7  51, 
 
> 51  27, 27  59, 59  11, 11  57, 57  25, 25  49, 
 
> 49  6, 6  4, 4  45, 45  21, 21  53, 53  29, 29  31, 
 
> 31  39, 39  3, 3  1, 1  37, 37  13, 13  17, 17  41, 
 
> 41  33, 33  35, 35  43, 43  19, 19  15, 15  47, 
 
> 47  5, 5  46, 46  22, 22  23, 23  55, 55  9, 9  8, 
 
> 8  54, 54  30, 30  28, 28  52, 52  20, 20  44, 
 
> 44  12, 12  36, 36  0}
In[5]:= For[i=1,i<=60,i++,WriteString[OutputStream["stdout",1],HCs[[1]][[i]][[1]
],","]] 
0,36,28,52,8,9,55,31,39,3,43,35,59,27,26,50,18,14,46,5,7,51,19,15,47,23,22,54,30,38,2,42,34,58,10,11,57,33,41,1,37,29,53,21,20,44,12,16,48,6,4,45,13,17,49,25,24,56,32,40,
In[6]:=

I bought my Pi5 especially for using free license wolframscript, but more with number theoretic algorithms in mind.
Nice that it has quite some graph algorithms as well.

https://github.com/Hermann-SW/RSA_numbers_factored
https://stamm-wilbrandt.de/GS [304+402+536fps]
https://hermann-sw.github.io/planar_graph_playground
https://github.com/Hermann-SW/Raspberry_v1_camera_global_external_shutter
https://stamm-wilbrandt.de