I have to find out if there is a Hamiltonian cycle in a giant graph (1000 vertices in the lowest instance and 5000 vertices in the largest).
My initial idea was to do backtracking, and in small instances, it worked fine. But for instance of 1000 vertices, I left 6 hours and no response.
My idea was to get a traveler's salesman code ready (I just found using matrix) and I put the edges that exist with weight 1, and those that do not exist with weight 9.
If the result of the function execution gives the number of vertices, there is a Hamiltonian cycle.
If you do not, then there is no Hamiltonian cycle (since you had to use some weight edge 9 to find the path).
For small instances, it continued to work, but with the instance of 1000 vertices, it also crashed.
No one in the class has the knowledge to do something that runs away from backtracking, so we're supposed to find some code already implemented on the internet. At most, we should make some minor changes.
Does anyone have a traveling salesman or a code that would detect a Hamiltonian cycle with adjacency list? Or instances up to 5000 in less than 3 hours?
Would anyone try to help me by giving at least one tip?
Links to the codes and entries I used:
-
Here is the code link I used (in C): link
-
Instances I need to pass: link
-
Follow the link in an adjacency list: link
-
Here is the link to a code that I made to transform the adjacency list into an array file: link
-
Follow the link for a small N = 18 array that contains a Hamiltonian cycle: link
-
Follow the link for a small array N = 18 that does not contain a Hamiltonian cycle: link