********************************************************************** Hamiltonian Cycle Program: Manual ********************************************************************** Author: Basil Vandegriend Email: basil@cs.ualberta.ca Last Updated: August 12, 1998 Copyright (c) 1998 Basil Vandegriend and Joseph Culberson. All rights reserved. Redistribution and use in source and binary forms, with or without modification, are permitted provided that the following conditions are met: 1. Redistributions of source code must retain the above copyright notice, this list of conditions and the following disclaimer. 2. Redistributions in binary form must reproduce the above copyright notice, this list of conditions and the following disclaimer in the documentation and/or other materials provided with the distribution. 3. All advertising materials mentioning features or use of this software must display the following acknowledgement: "This product includes software developed by the University of Alberta, Edmonton." 4. Neither the name of the University nor the names of its contributors may be used to endorse or promote products derived from this software without specific prior written permission. THIS SOFTWARE IS PROVIDED BY THE CONTRIBUTORS ``AS IS'' AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. THIS SOFTWARE IS SUPPLIED WITHOUT ANY SUPPORT SERVICES. ********************************************************************** 0. Table of Contents -------------------- 1. Introduction 2. An Overview of the Program 3. The Option File Format 4. The Test File Format 5. Result Files 6. Modifiying the Code to Get Multiple Versions of DegreeBound Graphs 1. Introduction ----------------------------- This is the user's manual for the Hamiltonian Cycle Program. It describes how to use the program to execute various algorithms on various classes of graphs. Many terms used in this manual come from Basil Vandegriend's master's thesis: Finding Hamiltonian Cycles: Algorithms, Graphs and Performance, for which this program was written. 2. An Overview of the Program ----------------------------- The program consists of C source code for the UNIX operating system and is divided into various source and include files. A makefile is also included. Compile the program using make: it will create the executable file "main". The program uses files for the majority of its operation. Experiments are listed by the researcher within a text file (the experiment file). The program is executed with the filename of the experiment file passed on the command line. The program then performs the specified experiment(s) and saves the results in one or more text files (result files) which can be examined by the researcher. There are two different formats for the experiment file: the option file and the test file. The option file allows for detailed specification of a single experiment. A single experiment may consist of many trials, but can only use one algorithm and one graph. All possible options can be set in the option file. The test file allows for a single experiment to be specified per line, in a condensed format. This allows for multiple experiments using different algorithms, different graphs and graphs with different parameters. The condensed format however limits the number of options that can be specified for any particular experiment: the result are set to values as specified by the test code inside "tester.c". When processing a test file, the program reads a single experiment, builds an option file for that experiment, then makes a system call to re-execute itself using the option file. When this experiment is completed, the next experiment is executed. Thus, the results of a test file experiment are identical to a series of option file experiments. The program is executed as follows for each experiment file format: To use an option file called : >main -o To use a test file called : >main -t Note that all option filenames should end with the extension ".opt" and that all test filenames should end with the extension ".test". A sample option file (sampleopt.opt) and a sample test file (sampletest.test) are provided with the program. Section 2 describes the option file format, Section 3 describes the test file format, and Section 4 describes the various result files that the program produces. 3. The Option File Format -------------------------- The option file consists of one or more arguments. Unspecified arguments use a default value (the default values for the different arguments are given below). The basic format of an argument is as follows: - [parameter list] OR - [] OR - The parameter list is specified as follows: +algparm1 [+algparm2=value2] [-algparm3] [...] Certain arguments have values associated with the argument that are either mandetory or optional. In additional, certain arguments have optional parameters which can be specified. Any line can be made into a comment by placing the '#' character at the start of the line. All commented lines are ignored. The rest of this section lists the different arguments and describes the format of each. 3.1 Graph Generation Argument ------------------------------ This argument specifies which type of graph to generate to find Hamiltonian Cycles on. Format: -graphgen Values Description (all have parameters) --------------------------------------------------------- nograph do not generate a graph (default) geometric generate a geometic graph random generate a Gn,m random graph degreebound generate a degreebound graph knighttour generate a generalized knight's circuit graph crossroads generate a crossroads graph addcycle generate an addcycle graph addpath generate an addpath graph iccs generate an interconnected cutset graph Common Parameters for all graph types (except for knighttour, crossroads and iccs graphs) +nvertex= number of vertices in graph +ensureham The +ensureham flag guarantees that the generated graph is Hamiltonian. This is done by generating the graph, running the backtrack algorithm on it, and regenerating the graph if it turns out to be non-Hamiltonian. This option should be used with caution, and is only intended for random and degreebound graphs (usually in conjunction with the posa_heur algorithm). Parameters for: -graphgen geometric +mindeg= minimum degree of all vertices +dist= distance or distance squared OR note that range is from 0 to 1 +dist2= +dim # of dimensions +near OR +far flag to specify if connect near or connect far +wrap OR +nowrap flag to specify if sides connect up (WRAP) or not (NOWRAP) Parameters for: -graphgen random +meandeg= the mean degree of the graph OR num edges = mean degree * n / 2 +degconst= the degree constant (d) mean degree = d * (log n + log log n) Parameters for: -graphgen degreebound +d= A percentage of the vertices will have degree d Example: a 200 vertex graph with 17% of vertices degree 2, 60% of vertices degree 3, and 23% of vertices degree 4: -graphgen degreebound +nvertex=200 +d2=0.17 +d3=0.6 +d4=0.23 Parameters for: -graphgen knighttour +move1= GKC parameter A +move2= GKC parameter B +board1= GKC parameter n +board2= GKC parameter m Example: A standard generalized knight's circuit (GKC) instance is (A,B) - n x m where the move is (A,B) and the board size is (n,m). The standard knight's tour consists of a (1,2) move on an (8,8) board which would result in the following argument: -graphgen knighttour +move1=1 +move2=2 +board1=8 +board2=8 Parameters for: -graphgen crossroads +subgraphs=<# of crossroads subgraphs> number of minimum-sized crossroads subgraphs with which to make the crossroads graph Parameters for: -graphgen addcycle +numcycles=<# of cycles to add> Example: An addcycle graph adds the specified number of Hamiltonian cycles to an empty graph. The fractional component of the number specifies that a path of length proportional to the fraction be added on top of the cycles. If we want to generate a 300 vertex graph made of 2 Hamiltonian Cycles and a path of 150 vertices, then we want the numcycles parameters to have a value of 2.5, which would result in the following argument: -graphgen addcycle +nvertex=300 +numcycles=2.5 Parameters for: -graphgen addpath +path1= +path2= Parameters for: -graphgen iccs +subgraphs=<# of iccs subgraphs> +indsetsize=<# of vertices in independent set of each subgraph> 3.2 Algorithm Argument ----------------------- This argument specifies which algorithm to use to find Hamiltonian Cycles Format: -algorithm [parameters] Values Description ( [P] means has parameters ) ---------------------------------------------------------------- nosolve no algorithm execution(default) noprune_bt standard backtrack without pruning backtrack backtrack algorithm with pruning [P] posa_heur posa-like heuristic algorithm [P] Parameters for: -algorithm backtrack +initvert= how to select the initial vertex ---------------------------------------------------------------- random at random (default) maxdeg a random vertex of maximum degree randeg probability of selection proportional to degree first select first vertex in graph +degsort= how to sort neighbours to get order in which to visit them ---------------------------------------------------------------- rand random order (default) min min degree first, increasing order max max degree first, decreasing order +pruneopt=[n][b][c][o][a] specify which pruning to do ---------------------------------------------------------------- n no pruning done (default) b basic pruning only (deg 2) c forced path / cycle pruning o connected components pruning a articulation (cutpoint) pruning +restart=n use the iterated restart technique ---------------------------------------------------------------- n size of increase in maximum node limit per iteration. Parameters for: -algorithm posa_heur (The default is having none of these flags.) +smartvist Use a better-than-random strategy for choosing the next neighbour to go to. +smartcomplete Use order-1 crossovers (a single rotational transformation) when trying to form a Hamiltonian Cycle from a Hamiltonian Path. +cycleextend Use the cycle extension technique. Using this flag automatically sets the +smartvisit and +smartcomplete flags 3.3 Report Argument -------------------- This argument controls what information and results are reported back to the user. Format: -report [report parameters] (The default setting is to have no report flags set.) Report Parameters Description ------------------------------------------------------------------------- +options report option settings in .option file +graph report graph statistics in .log file +alg report information about algorithm execution in .log file +solution list the Hamiltonian Cycle (if found) in .sol file +summary summarize the experiment results using the one-line experiment format of the tester file in .summary file Example: -report +options +solution +summary See Section 5 for a more detailed description of the various files produced by the program. 3.4 Other Arguments -------------------- -instancetests perform tests (algorithm executions) per graph instance -graphtests generate graphs for testing (one at a time) -loadgraph instead of generating a graph, load the graph from file -savegraph [] save the generated graph to the file . If no filename is specified, use the base name (the name of the option file without the ".opt" extension) and add a ".graph" extension. If multiple graphs are being used, use a ".graph" extension. -randseed specify the random number generator seed. If none is specified, a seed is generated using the current time. -timelimit