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 <number_of_vertices> [options]

Valid options are:
  g<x>: Searches for graphs with girth at least <x>.
  planar: Only output planar graphs.
  maxdeg <x>: Only output graphs with max degree at most 3.
  mod <rest> <modulo>: Splits the generation in <modulo> (more or less equally big) parts. Here part <rest> 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).
  platypus: Generate platypus graphs (non-hamiltonian graphs for which every vertex-deleted subgraph is traceable).


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
---------

2018-09-18: Fixed bug related to destroying type A obstructions. We reran all previously reported computations and no graphs were missed by the old version of the program.
2017-10-10: Added support for generating platypus graphs.
2016-06-13: Added support for generating 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