Enjoy finding out Hamiltonian Cycles

This app has won the "2021 March's MIT APP INVENTOR OF THE MONTH" award. 

 Abstract 

This app solves the Hamiltonian cycle problem for a given graph. The problem is to find out paths in a directed graph of n vertices, starting from one starting point, visiting all vertices only once, and returning to the starting point. This is known as an NP-complete problem and no efficient solution is known in general. From the perspective of programming education, I provide a solution for small graphs with six or fewer vertices, along with an easy-to-use user interface. 

Basically, it searches all possible paths, but the method is not so trivial and you need to think carefully about the procedure. The use of multiple lists and recursive functions in implementing the algorithm is useful for improving programming capabilities. You should also consider the graphical user interface for setting up and displaying graphs. The sense of accomplishment gained by completing this app enhances the educational effect. It's also fun to run the finished app and see the results on the graph. 

This time, I used MIT App Inventor to create this app. The use of App Inventor's familiar feature blocks (especially Lists, AnyComponent, Canvas, Checkboxes, etc.) was very useful for efficient program development. 

●This app is published on the Google Play Store:
https://play.google.com/store/apps/details?id=appinventor.ai_Fujio_YAMAMOTO.HamiltonianCycles1

●The source code of this app is published below :
https://gallery.appinventor.mit.edu/?galleryid=3048beec-25b8-46ba-a746-25c0dc3702b6

Directed graphs and the Hamiltonian cycle

Figure 1 shows an example of a directed graph and the Hamiltonian cycle. A single matrix can be used to represent the connections between nodes. In this matrix, the "From" node is in the row and the "To" node is in the column. In the example, there are two Hamiltonian cycles. This app provides both a way to give a directed graph with such a matrix and a way to automatically generate a random graph. 

How to use the app for the Hamiltonian cycle problem

Fig.2 shows the GUI of the app developed this time. The number of nodes can be specified in the range of 2 to 6. If you want to specify a directed graph in the matrix on the left, check the check box "prefer Matrix". After that, when you press the button "genGraph", a graph with an arrow will be drawn on the canvas at the top. Next, if you press the button "solve", the Hamiltonian cycle will be searched, and as a result, the number of cycles and the path of each cycle will be displayed. On the other hand, if you want to generate a graph randomly instead of specifying the graph yourself, uncheck the check box "prefer Matrix". Even then, the matrix corresponding to the generated graph is automatically displayed. It would be fun to discover such a cycle for different graphs.

Acknowledgments

In this app, I referred to the following documents when generating permutations:

Asao Kasai, "Introduction to algorithms in Java”, chapter 4, Gijyutsu-Hyouron-sha, July 2001.(in Japanese)