Short manual of GenHypohamiltonian
----------------------------------
Author: Jan Goedgebeur (jan.goedgebeur@ugent.be)
In collaboration with Carol Zamfirescu
GenHypohamiltonian is a generator for hypohamiltonian and almost hypohamiltonian graphs.
This program has been tested on Linux and Mac OS X.
Installation
------------
The latest version of GenHypohamiltonian can be obtained from http://caagt.ugent.be/hypo/
- Download, extract and configure nauty from http://users.cecs.anu.edu.au/~bdm/nauty/ (GenHypohamiltonian requires nauty 2.5 or a more recent version).
- Compile the nauty libraries using: "make nautyW1.a"
- Copy the following files to the GenHypohamiltonian directory: nausparse.h nauty.h nautyW1.a naututil.h planarity.c naurng.h splay.c planarity.h
- Compile GenHypohamiltonian using the command "make".
(Alternatively, compile GenHypohamiltonian using the command: cc -DWORDSIZE=32 -DMAXN=WORDSIZE -mpopcnt -O4 gen_hypohamiltonian.c planarity.c nautyW1.a -o gen_hypohamiltonian)
Usage
-----
An overview of all options can also be found by executing "./gen_hypohamiltonian -h".
Usage: ./gen_hypohamiltonian [options]
Valid options are:
g: Searches for graphs with girth at least .
planar: Only output planar graphs.
maxdeg : Only output graphs with max degree at most 3.
mod : Splits the generation in (more or less equally big) parts. Here part will be executed.
almostcomplete: Generate almost hypohamiltonian graphs (is exhaustive).
almostspecial: Heuristic which generates almost hypohamiltonian graphs (is faster than almostcomplete, but may be incomplete).
The generated graphs are written to stdout and are encoded in multicode format (see Appendix A).
Don't hesitate to contact me at jan.goedgebeur@ugent.be if you have any further questions or suggestions.
Changelog
---------
2016-06-13: Added support for almost hypohamiltonian graphs.
2016-02-19: First release.
Appendix A: definition of the multicode format
----------------------------------------------
This code is binary. The first entry is the number of vertices.
Vertices are numbered 1,...,n. For each vertex x there is a list of
neighbours with higher labels than x, followed by a zero.
The last list is always empty (there are no neighbours of n with a higher number than n),
therefore the last "list" is not followed by a zero.
After the last byte the next graph follows.
The codelength of a graph in multicode is number of vertices + number of edges.
More information about this format + a program to translate multicode to adjacency lists can be found at: http://hog.grinvin.org/Formats.action#multicode