Introduction:
This page demonstrates two examples of step-by-step calculation (under a Microsoft® Windows® 32-bit operation system) of different Hamiltonian cycle problems taken from... |
| more...
|
Example 1: ALB1000 with 25 random tests
The step-by-step instruction for unzipping the HCP_Solver package, running calculations for the above listed graph, and saving the results of testing is as follows: |
| more...
|
Example 2: {7,8}-leaper on a 15x106 board with 2 random tests
The step-by-step instruction for unzipping the HCP_Solver package, generating the LEAPER_7_8_15_106 example, running the process of calculation for the above listed graph, and saving the results of testing is as follows: |
| more...
|
|
|
|
|
This page demonstrates two examples of step-by-step calculation (under a Microsoft ® Windows ® 32-bit operation system) of different Hamiltonian cycle problems taken from the famous Internet library TSPLIB at http://www.iwr.uni-heidelberg.de/groups/comopt/software/TSPLIB95/. The first one is a common graph “ALB1000.hcp” and the second one is a “{7,8}-leaper on a 15x106 board” graph obtained with the use of the LEAPER generator ( TSPLIB/HCP). Both examples have the same TSPLIB-format (hcp-type) and Hamiltonian cycles. The Hamiltonian cycles are found using our HCP Solver, while the results (Hamiltonian tours) as well as the initial graphs can be viewed through the WinHcp32 graphical viewer. For the graphs tested you can use any numbers of randomly generated initial cycles. General data on each example and test results are stored in a special text file. Information on generating a leaper file, on finding Hamiltonian cycles, and on viewing graphs for the examples described is included in this instruction.
On our website http://www.pcgrate.com/ or http://www.iigrate.com/ you can find more computation examples using the HCP Solver program with data files, plots, and tables.
|
| Back to the Top |
|
1. ALB1000 with 25 Random Tests
The step-by-step instruction for unzipping the HCP_Solver package, running calculations for the above listed graph, and saving the results of testing is as follows:
Unzip files from the “HCP_Solver.zip” archive into the main “HCP_Solver” directory.
Run Command Prompt application using the “Start Menu\All Programs\Accessories\Command Prompt” command.
Choose the main “HCP_Solver” directory using, for example, the command “cd c:\...\HCP_Solver”.
Run the “HCP.exe” command to see information about using the HCP Solver.
Run HCP Solver to find a Hamiltonian cycle in the “ALB1000.hcp” graph for 25 random tests using the “hcp.exe ALB1000.hcp 25” command. The string “Hamiltonian cycle problem solver” appears and calculation starts.
To save the results of calculation for a future analysis, rename the current “HCP.txt” file with the default name from the main “HCP_Solver” directory into, for example, a “HCP_ALB1000.txt” file.
During the calculation you can track the status information about the solution process in the strings. If you would like to stop the calculation, press the combination “Ctrl-C”. After completing the calculation, you can see the results of testing for 25 tests and different times for the solving process in the Command Prompt window. General statistical data for this example and its test results are stored in the “HCP.txt” file (see Figure 8). The Hamiltonian cycle thereby obtained is stored in the “ALB1000.tou” file (as an example, see Figure 7).
The step-by-step instruction for downloading graphical views of the input graph and of its Hamiltonian cycle is as follows:
Run the “WINHCP.exe” command to open the WinHcp32 application.
Choose the “File\Open\ALB1000.hcp” item in the main menu of the WinHcp32 application and click the “Open” button in the “Open” dialog window. You can see a graphical view of the “ALB1000.hcp” example with a default cycle {1,2,3,4,...1000} (see Figure 3).
Choose the “View\Rearrange cycle” item in the main menu or click the “Rearrange cycle” button on the main toolbar of the WinHcp32 application.
Click the “Browse” button in the “Rearrange cycle” dialog window and then choose the “ALB1000.tou” file in the “Open” dialog window from the main “HCP_Solver” directory.
Click the “OK” button in the “Rearrange cycle” dialog window (see Figure 3). You can see a graphical view of the “ALB1000.hcp” example with a Hamiltonian cycle {328,287,288,28,...327} (see Figure 4).
|
| Back to the Top |
|
2. {7,8}-leaper on a 15x106 Board with 2 Random Tests
The step-by-step instruction for unzipping the HCP_Solver package, generating the LEAPER_7_8_15_106 example, running the process of calculation for the above listed graph, and saving the results of testing is as follows:
Unzip files from the “HCP_Solver.zip” archive into the main “HCP_Solver” directory.
Run the Command Prompt application using the “Start Menu\All Programs\Accessories\Command Prompt” command.
Choose the main “HCP_Solver” directory using, for example, the “cd c:\...\HCP_Solver” command.
Run the “LEAPER.exe” command to see information about using LEAPER.
Run the “LEAPER 7 8 15 106” command to generate the “LEAPER_7_8_15_106.hcp” graph.
Run the “HCP.exe” command to see the information about using HCP Solver.
Run HCP Solver to find a Hamiltonian cycle in the “LEAPER_7_8_15_106.hcp” graph for 2 random tests using the “hcp.exe LEAPER_7_8_15_106.hcp 2” command. The “Hamiltonian cycle problem solver” string appears and the calculation starts.
To save the results of calculation for further analysis, rename the current “HCP.txt” file with the default name from the main “HCP_Solver” directory into, for example, “HCP_LEAPER_7_8_15_106.txt” file.
During the calculations, you can track status information about the solution process in the strings. If you would like to stop the calculation, press the combination “Ctrl-C”. After completing the calculation, you can see the results of testing for 2 tests and different times for the solving process in the Command Prompt window.
General statistic data for this example and test results are stored in the “HCP.txt” file. A Hamiltonian cycle which has been obtained is stored in the “HCP_LEAPER_7_8_15_106.tou” file. For the step-by-step instruction for downloading a graphical view of the input graph and its Hamiltonian cycle, see Sample 1.
|
| Back to the Top |
|
|
|
|
