The C code of the program can be obtained for three
versions:
version 1,
version 2, and
version 3.
Any C compiler can be used (for example,
gcc wclique.c -o wclique -O2). To run the program, simply
type
wclique infile
where infile is a file with the weighted graph in the
following format:
Line 1 holds two integers: the number of vertices and
the number of edges (this value is not used and may
be replace by any value). Each successive line gives the
cost, degree, and the adjacency list for a single vertex.
For example:
4 5
3 3 1 2 3
2 2 0 2
1 3 0 1 3
4 2 0 2
This graph has 4 vertices (numbered from 0 to 3) and 5
edges. Vertex 2 has weight 1 and is adjacent to 3
vertices, namely 0, 1, and 3.
When the program is run, it shows the largest weight found so far and the CPU time elapsed. When the search is ready, the vertex list of one maximum-weight clique is given.
The program may be used freely in academic work, as long as this is acknowledged with proper references. No guarantee is given for correctness of the program; it should be used on one's own risk. The author is grateful for any comments and bug reports; please email me at patric.ostergard@hut.fi. If you want to use the program for commercial purposes, please contact me at the same address.
Note that if this program is used with unweighted graphs, that is, with all weights 1, it is not as fast as programs tailor-made for that purpose. The difference in speed is, however, often negligible.
It is important to note that the constant MAX_VERTEX gives the largest order of a graph that can be considered. This is now set to 2000 but can, of course, be made larger. This value is restricted by the memory size of the computer; a too large value will result in "Segmentation fault" or some other outcome that is not wanted.
I finally list fifteen (compressed) files with graphs obtained from the the problem of constructing maximal constant weight codes with prescribed automorphism groups. These graphs are used in tests in the aforementioned maximum-weight clique paper. The paremeters are (n,d,w) = (11,4,4), (12,4,6), (14,4,7), (14,6,6), (16,4,5), (16,8,8), (17,4,4), (17,6,6), (19,4,6), (19,8,8), (20,6,5), (20,6,6), (20,8,10), (21,10,9), (22,10,10). On May 21, 2001, these were replaced by isomorphic graphs obtained by applying a random permutation to the vertices. The reason for this was to destroy the earlier nonrandom order of the vertices, which turned out to have a great impact on the speed of many algorithms.