Smallk Coloring Program Manual
J. Culberson
This manual is currently very brief. Smallk is a backtrack based program
for coloring graphs which are expected to have a small chromatic
number, e.g. from 3 to 8 colors. This link provides a brief
overview of the algorithm(postscript).
This is also available as an appendix to the paper "Frozen Development
in Graph Coloring" to appear in the TCS special issue on phase transitions.
Please read the CONDITIONS OF USE
.
To use this program, first create a directory and copy the
source code (gzipped tar file)
into it. Unpack this, and if you have the make program simply type make
to create an executable in the current directory. The source code is in C.
To execute
smallk filename seed colors [timeout]
Where
- filename is the name of the file containing the graph in either
the DIMACS standard ASCII format or DIMACS standard binary format. Descriptions
of these and translators to/from binary formats can be found in Michael Trick's
Graph Coloring
Instances
.
- seed is a positive integer to seed a random number generator
(there are some choices made randomly during search)
- colors is the number of colors you wish to test the graph for.
Currently this must be between 2 and 8. As this number is increased, the
efficiency of the search goes down dramatically. If you wish to attempt more
colors change the values of SMALLLIMIT and SMALLVECTOR in the smallk.h
file as indicated in the comments. But be warned this has not been tested
very well. The value of SMALLVECTOR must be 2 to the power of SMALLLIMIT,
and it is the size of various arrays and matrices, so it is not likely practical
to attempt values larger than 16.
- timeout is an optional parameter that should limit the execution
time. If this time is exceeded the program gets 15 seconds to clean up from
its last call and print out the summary statistics. If this time fails then
it should exit immediately. I have not tested this across platforms.
Smallk outputs statistics and other info to standard output. If it is successful
in coloring the graph then it creates a graph filename.res or appends
to it if it already exists, and writes out the coloring found. This is a list
of colors 1..k for each vertex. The list is preceded by a one line comment.
The program catches SIGINT (cntrl-C on my linux machines) and tries to
clean up and print out statistics of the current search. A second interrupt
should terminate it immediately.
If you do not want all of the statistics, then simply edit the printstats()
routine in stats.c. (As I said this is research code, so you are
on your own as to modifications.)
Enjoy!