R. M. R. Lewis, School of Mathematics, Cardiff University, Wales,
Last Updated: Wednesday, 09 March 2022
This document contains descriptions on how to compile and use the graph colouring algorithm implementations described in the following publication:
These implementations can be downloaded fromSection 9 of this document also contains a short list of typos found in the above edition of this book. If you spot any more, please get in contact with the author.
Once downloaded and unzipped, we see that this directory contains six sub-directories. Different algorithms are contained within each of these. Specifically,
• AntCol: The AntCol algorithm, based on ant colony optimisation.
• BacktrackingDSatur: The Backtracking algorithm based on the DSatur heuristic’
• Constructive: The Greedy, Welsh-Powell, DSatur, Greedy-IS and RFL algorithms.
• HillClimber: The hill-climbing algorithm.
• HybridEA: The hybrid evolutionary algorithm.
• PartialColAndTabuCol: The PartialCol and TabuCol algorithms.
Full descriptions of these algorithms can be found in the above publication. All algorithms are programmed in C++ and can be compiled in both Windows (using Microsoft Visual Studio) and Linux (using g++). Instructions on how to do this now follow.
To compile and execute using Microsoft Visual Studio, use the following steps.
1. Open Visual Studio and click File, then New, and then Project from Existing Code.
2. In the dialogue box, select Visual C++ and click Next.
3. Select one of the sub-directories above, give the project a name, and click Next.
4. Finally, select Console Application Project for the project type, and then click Finish.
The source code for the chosen algorithm can then be viewed and executed from the Visual Studio application. Release mode should be used during compilation to make the programs execute at maximum speed.
To compile the source code using g++, please use the included makefiles.
Input files are used to specify individual problem instances for the algorithms. These are simple undirected graphs and should be specified using the.
Below are the first few lines of the file graph.txt, which is included in each subdirectory as an example. The initial lines begin with the character “c”. These are comments that give the user textual information about the graph, which are ignored by the programs. The single line beginning with “p edge” then specifies that edges will be used to specify the graph, and that it contains 250 vertices and 17,083 edges. Note that vertices are labelled from 1 upwards. Finally, lines beginning with “e” give the edges of the graph. As a result, there are 17,803 lines beginning with “e”.
Once generated, the executable files in each sub-directory can be run from the command line. If the programs are called with no arguments, usage information is printed to the screen. For example, suppose we are using the executable file HillClimber. Running this program with no arguments from the command line gives the following output:
The input file should contain the graph colouring problem to be solved. This is the only mandatory argument. The remaining arguments for each of the programs are optional and are allocated default values if left unspecified. Here are some example commands using the HillClimber executable:
This will execute the algorithm on the problem given in the file graph.txt, using the default of 1000 iterations of local search per cycle and a random seed of 1. The algorithm will halt when 100,000,000 constraint checks have been performed. No output will be written to the screen. Another example command is:
This run will be similar to the previous but will use the random seed 1234 and will halt either when 500,000,000,000 constraint checks have been performed, or when a feasible solution using 50 or fewer colours has been found. The presence of -v means that output will be written to the screen. Including -v more than once will increase the amount of output.
The arguments -r and -v are used with all of the algorithms supplied here. Similarly, -T and -s are used with all algorithms except for the constructive algorithms. Descriptions of arguments particular to just one algorithm are found by typing the name of the program with no arguments, as described above. Interpretations of the run-time parameters for the various algorithms can be found by consulting the publication at the top of this document. A full listing of all run time parameters for each algorithm is given below.
When a run of any of the programs is completed, three files are created, and one file is added to. The three created file are ceffort.txt (computational effort), teffort.txt (time effort) and solution.txt. The first two specify how long (in terms of constraint checks and milliseconds respectively) solutions with certain numbers of colours took to produce during the run. For example, we might get the following computational effort file:
This file is interpreted as follows: The first feasible solution observed used 40 colours, and this took 126,186 constraint checks to achieve. A solution using 39 colours was then found after 427,143 constraint checks, and so on. To find a solution using 34 colours, a total of 6,849,302 constraint checks were required. Once a row with an X is encountered, this indicates that no further improvements were made – that is, no solution using fewer colours than that indicated in the previous row was achieved. Therefore, in this example, the best solution found used 34 colours. For consistency, the X is always present in a file, even if a specified target has been met.
The file teffort.txt is interpreted in the same way as ceffort.txt, with the right-hand column giving the time (in milliseconds) as opposed to the number of constraint checks. Both files are useful for analysing algorithm speed and performance. For example, the computational effort file above can be used to generate the following plot:
The file solution.txt contains the best feasible solution (i.e., the solution with the fewest colours) that was achieved during the run. The first line of this file gives the number of vertices n; the remaining n lines then state the colour of each vertex, using colour labels from zero upwards. For example, the following solution file:
is interpreted as follows: There are 5 vertices. The 1st and 4th vertices are assigned to colour 0, the 3rd and 5th vertices are assigned to colour 1, and the 2nd vertex is assigned to colour 2. Hence, three colours are used in total.
Finally, on completion of a run, information is also appended to the file resultsLog.log. This appears on a single line and contains the following pieces of information (in this order), separated by tabs.
1. Name of the algorithm;
2. Number of colours used in the best feasible solution observed during the run;
3. Total run time (in milliseconds);
4. Total number of constraint checks performed during the run.
If the run resulted in an error (due to unrecognised input parameters or an invalid input file), then appropriate single-line error messages are also appended to the file.
If you are interested in using one of these algorithms and you don’t know which one to choose (or you don’t really care how they work), here are some recommendations:
1. Hybrid EA (HEA): In general, this algorithm has been found to produce the best results (in terms of the number of colours used in its solutions) in the book cited at the beginning of the document. The default parameters for the algorithm are a reasonable choice in most cases.
2. BacktrackingDSatur: If you require a complete algorithm (i.e., you want to find the provably optimal solution to a particular problem), then use this algorithm. However, be warned that for larger problems, this algorithm may not be able to give you the proven optimal in reasonable time. Also, if halted early, it may not give you a solution of comparable quality to some of the other methods.
Further information on the relative performance of these algorithms can be found in the book cited at the start of this document.
Below is a list of run-time parameters for each available algorithm. As mentioned, this information is generated by the programs when they are executed with no arguments.
Redistribution and use in source and binary forms, with or without modification, of the code associated with this document are permitted provided that a citation is made to the publication given at the start of this document. 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.
The following is a list of typos that have been identified in the 2021 edition of this book (second edition). If you spot any others, please send them to the author atand he will be happy to note them here.
• Page 65, Fig. 3.17. On Line (4) of the pseudocode, replace the i with a j.
• Page 98, Fig. 4.10. In Step (2), replace “come” with “some”.
• Page 195, Section 6.9.2, second paragraph, first line: should read “…taking a graph G = (V, E, w)…”.
• Page 197, first line: should read “expressed as a polynomial”.
• Page 200, Reference 7. Year should be “1977”, not “1997”.
• Page 206. Please note that the wedding seat planner tool requires Adobe Flash player to operate. However, as of December 202 Flash Player is no longer supported by most web browsers. Indeed, Adobe strongly recommends all users immediately uninstall Flash Player to help protect their systems. As an alternative, a command-based C++ implementation of the wedding seat planner is available at http://www.rhydlewis.eu/resources/wsp.zip.
The author would like to give his thanks to Paulo Neis (email:) from Brazil who produced the attached makefiles and who also helped to spot a small number of bugs in an earlier version of this code.