This page is still being updated. FOR INFORMATION CONTACT
joe@cs.ualberta.ca
Information is currently unstable.
Descriptions of these algorithms and some experimental results can be found in References [1,2,3] below. (Available on-line). It is assumed throughout this document that the reader is familiar with these papers.
Each of the programs is initiated by
program filenameThe file filename should contain the graph description 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 .
The graphs may also include a hidden coloring description, called the cheat as output by the K-Colorable Graph Generator . Currently, only the Iterated Greedy(IG) program uses the cheat. If the user chooses to use the cheat in IG, then a proximity measure is output at regular intervals to indicate how close the coloring is to the hidden one. Reference [3] provides some analysis based on the proximity measure. For further references on on this measure, search the Coloring Bibliography for the term proximity.
The final coloring obtained by the program is appended to the file filename.res. For some programs, e.g. Iterated Greedy and TABU, this result file is also used to select initial colorings.
The final coloring is also verified before writing, with a statement of verification printed to standard output. Given the complexity of some of the coloring routines, it is a good idea to check this output, in case some error should occur. Iterated Greedy and TABU also verify the input colorings that are selected before starting the coloring process.
Each program requires a number of parameters in addition to the graph description. These parameters are prompted for interactively through standard input and output. Every program first prompts whether or not the user wants the cheat to be used.
Do you wish to use the cheat if present? (0-no, 1-yes)Only the Iterated Greedy uses it at this time. The next prompt requests a seed for the random generator.
Enter seed for search randomization:
Further descriptions of each program are provided below. The programs currently available are
As a result, the code shows its history. Careful examination will reveal to the reader sections of code that are not used (blocked out by #ifdef's), capabilities in current code that are not available in this implementation, data structures that are not the most efficient match to their current use, and parameters to routines that are locked down by constant declarations in mid-stream.
In short, the code has a lot of historical legacy. Well, it is part of on-going research into what works and what does not. This publication of the code is on an as-is basis, and if you wish to modify it or adapt portions for use elsewhere, you are strictly on your own.
PLEASE READ THE CONDITIONS OF USE .
If your system supports ``make'', first edit the makefile and change the BINPATH variable to indicate where you wish the output to go. Then typing
make allshould create each of the following programs. Reading the makefile should provide insight as to what pieces of code are required by each routine.
greedy fileThe greedy algorithm, also known as the sequential algorithm, has several variations. For further references, search the Coloring Bibliography for the term sequential | greedy. (The "|" means "OR" to the search engine). Another term to try is kempe.
The greedy algorithm takes each vertex in turn in some predefined order and tries to color the vertex with one of the colors used so far. In other words, it tries to add the vertex to one of the existing color classes. If it is not possible to color it with any existing color, then a new color class is created and the vertex is assigned the color of that class.
This leaves two apparent choices:
In addition to the cheat and random seed, greedy issues the following prompts.
GREEDY TYPE SELECTIONThis indicates how the program is to make the choice of which color class to use for the vertex. Each, except for ``Stir Color Greedy'' selects the first class encountered in the indicated search order.
1 Simple Greedy
2 Largest First Greedy
3 Smallest First Greedy
4 Random Sequence Greedy
5 Reverse Order Greedy
6 Stir Color Greedy
Which for this program
``Simple Greedy'' visits the classes in order 1..k, and is the technique
usually indicated when someone refers to the sequential algorithm.
``Largest First Greedy'' ranks the classes by number of vertices currently
in them, and searches by descending size. This should tend to build larger
independent sets.
``Smallest First Greedy'' ranks the classes by number of vertices currently
in them, and searches by ascending size. This should tend to equalize the
size of the color classes.
``Random Sequence Greedy'' searches the sets in a random order.
``Reverse Order Greedy'' searches the sets in the order k..1.
``Stir Color Greedy'' what the heck does it do? Ahh - read the code, it
does not seem to perform very well anyway.
The next prompt is for the ordering of the vertices.
Initial Vertex Ordering:Inorder presents the vertices in the order 1..n, the other three should be obvious. The inorder may possibly be useful if you think the construction of your graph could be providing hints to its coloring.
1 -- inorder
2 -- random
3 -- decreasing degree
4 -- increasing degree
Using:
The last requirement is whether or not to use a Kempe reduction after greedy has completed.
Use Kempe reductions y/nKempe chain reductions are basically done as follows, assuming k colors have been used and that S[i] refers to the vertices of the ith color class:
For 1 <= i < k,See the Reference [4] for further information.
For i < j <= k do
Compute the induced connected components
of the induced subgraph G[S[i]+S[j]].
Swap the vertices of any component that
has more vertices in S[j] than in S[i].
dsatur fileThis program is based on the paper by Daniel Brelaz [6] . It is like the sequential algorithm, except that the order in which vertices are chosen is determined dynamically based on the number of colors that cannot be used because of conflicts with previously colored vertices. Vertices with the fewest available colors are colored first.
For further references, search the Coloring Bibliography for the term dsatur.
In addition to the cheat and random seed, dsatur requires only one input:
DSATUR COLORINGThis is the secondary selection order used when two or more vertices have the same saturation.
Initial Vertex Ordering:
1 -- inorder
2 -- random
3 -- decreasing degree
4 -- increasing degree
Using:
maxis fileInitially, this program was based on the paper by Bollobas and Thomason [6] It has evolved somewhat over time. Further descriptions can be found in the references [1,2,3,] . It is also similar to the extremely greedy algorithm of Manvel [7] and the XRLF algorithm of Johnson et al[4]
MAXIS is based on an exponential backtrack algorithm for finding a large maximal independent set. (If given unbounded time, it will find a maximum set, but for large graphs the user will likely expire first.) These sets are the color classes. For random graphs in G(n,p) with p=1/2 it is one of the better algorithms. However, for sparser graphs it is less effective, because the independent sets are larger, meaning the backtrack tree is of greater depth and of larger branching factor. See [2] .
In addition to the cheat and random seed, maxis issues the following prompts.
The backtrack (depth first) search operates by adding vertices one at a time to an independent set. At each addition, several choices may be available as possibilities, and these are the backtrack choices. Since it is impractical to do a complete search for a maximum independent set, search tree pruning is accomplished through the following mechanism.
Vertex Num, Cutlim in decreasing order to 0In response, supposing a graph of 1000 vertices, the user might input
200 2This means that if the current set of available vertices has 200 or more vertices in it, then limit the choices to the first two (a branching factor of two). If there are less than 200 but more than 100, then allow up to 3 alternate searches (branching factor of 3), if less than 100 but more than 50 allow 4, and if less than 50 only allow two.
100 3
50 4
0 2
On a graph of 300 vertices the single response
0 3may produce a reasonable result fairly quickly.
Backtrack limit = 0 means no limit to backtrackA second pruning occurs with the Backtrack Limit. Suppose that we have one of the selections for pruning above. Intuitively, since it has to have some color, there is no reason to second guess the choice of the first vertex of a set. If we set Backtrack limit to 1, then the branching factor at depth one of the search will be one. However, intuition has not been strongly supported by experiments.
Backtrack limit = k means do not backtrack over first k
Upsort limit(U) and Midsort limit(M) with |G| =N
if NumRem > (U*N)/100 then sort by decreasing degree
else if NumRem > (M*N)/100 then sort by medium degree
else sort by increasing degree
Enter Backtrack Limit, UpSort Limit, Midsort Limit
Since we are pruning, and thus doing an incomplete search, heuristics as to which branch to choose first will be important for good performance. This is controlled in this program through the UpSort and MidSort limits. Suppose there are 300 vertices in the current subgraph of a 1000 vertex graph when the first vertex of the next independent set is to be chosen. Suppose also that U=75 and M=50 have been entered.
Then, while there are at least 75*300/100 = 225 vertices left as possibilities for the next selection, the selection will be by decreasing degree. And when there are between 150 and 225 possibilities, then selection will be by a sorting that places midrange degree vertices first. When there are fewer than 150 vertices, then selection will be in order of smallest degree first.
See references [1,2,6]
for a discussion of why such choices are important in random graphs. It
is less clear which choices might be best for other classes of graphs.
4. Backtrack DSATUR
Synopsis:
bktdsat fileThis program is based on a backtrack version of DSATUR with dynamic re-ordering of vertices during backtrack as in Korman's algorithm [8] , but with an attempt at additional heuristic guidance as well, using an idea similar to the prohibition of Campers et al [9] . (What was the final state of this program?) If the branching factor is set very large, and no backtrack region is excluded (see below) then this algorithm should guarantee an optimal (chromatic number) coloring for small graphs.
In practice the time required to do a backtrack search with this algorithm does not produce comparable increases in quality of solution as is obtained with similar effort by MAXIS or Iterated Greedy for most classes of graphs. An exception, noted in [3] occurs on geometric graphs.
In addition to the cheat and random seed, greedy issues the following prompts.
BACKTRACK DSATUR COLORINGIf you are searching a k-colorable graph, then this allows termination if such a coloring is found. Otherwise, enter one to allow a complete search.
Target Color - terminates if achieved:
Maximum branching factor:Entering a branching factor of 0 causes the algorithm to behave like DSATUR, essentially performing a sequential search. For larger values, L when the program backtracks to some point and takes an alternate branch, the branching factor is reduced by one for the entire subtree. If the branch factor at the root of a subtree is 0 then no further branching is allowed in the subtree.
Block off which areaWhile working with this program, Papp noticed that for many graphs the only improvements that were likely to occur in wider searches occurred as a result of alternatives either near the root or near the leaves of the search tree. Entering a pair of numbers such as 30 280 on a graph of 300 vertices means that no branching will occur at depths in that range.
('x y' means no branching in depth range x to y):
At each iteration choose vertex of minimum (0) or maximum (1) saturation?These prompts allow setting the selection and ordering of vertices. On some graphs Papp found that using a minimum saturation worked as well as a maximum (possibly when followed by iterated greedy).
Find maxclique? (0-no,1-yes)
Sort vertices by decreasing (0) or increasing (1) degree first?
If the maximal clique option is selected, then a subroutine to find a maximal clique is called. This is similar to the MAXIS program for finding a maximal independent set, with the obvious flip of meaning for edges versus non-edges. Once a first clique is found remaining vertices are sorted by degree as requested. If no clique is requested, then all vertices are sorted.
Vertex Num, Cutlim in decreasing order to 0These options are for the clique finding routine if requested, and are the same as described in the MAXIS section.
Backtrack limit = 0 means no limit to backtrack
Backtrack limit = k means do not backtrack over first k
Upsort limit(U) and Midsort limit(M) with |G| =N
if NumRem > (U*N)/100 then sort by decreasing degree
else if NumRem > (U*M)/100 then sort by medium degree
else sort by increasing degree
Enter Backtrack Limit, UpSort Limit, Midsort Limit0
itrgrdy fileThis program is is able to take a previous coloring from file.res and then try to improve on it by an iterated local improvement search. If no coloring is available, then the program uses a trivial n-coloring to start. The program generates many colorings, and outputs the best coloring it finds.
The method this program uses is to repeatedly call the Greedy program to find a new coloring. The key idea that makes this worthwhile doing is that for each call, the ordering of the vertices is determined by the previous coloring. This is done in such a way that it is guaranteed that each call will produce a new coloring using no more colors than the previous coloring. Several ways of reordering the vertices are available that satisfy this criterion.
This program requires quite a few control parameters.
This is the only program (at the time of writing) that uses the cheat to compute proximity measures. If the use of the cheat is selected, and a hidden coloring is included in the graph, then this coloring is read into the program and used to compute the proximity measure with respect to the current coloring at regular intervals throughout the search.
After the cheat is selected the user is asked for a number to seed the random number generator. Then the following prompts are given:
Enter target colorIf a coloring is obtained using this or fewer colors, then the program terminates.
GREEDY TYPE SELECTIONThese types are the same as described in the Greedy section. However, since the program makes many calls to greedy, it is possible to vary which type is used on different calls.
1 Simple Greedy
2 Largest First Greedy
3 Smallest First Greedy
4 Random Sequence Greedy
5 Reverse Order Greedy
6 Stir Color Greedy
For each greedy type, enter its weight for selection:
Enter weight for 1 100The selection of greedy type is probabilistic, and the inputs in the above example would select the simple type and the largest first type with probability 100/250 each, and would select random with probability 50/250.
Enter weight for 2 100
Enter weight for 3 0
Enter weight for 4 50
Enter weight for 5 0
Enter weight for 6 0
Enter the frequency for Kempe reductions:Kempe reductions are computationally expensive if done on every greedy call, and also tend to cause IG to hover around a local minima if used too frequently. Entering a number 30 means that the reductions will be done on every 30th call. A number in the range 20-50 seems most effective, although larger values may be appropriate for larger graphs.
Enter number of iterations before quitting (after last improvement)IG is a local search that can run for an arbitrarily long time. Entering a value of 1000 here means that 1000 calls to greedy will be made after the last improvement detected. The value of a coloring for this purpose is called the color sum and is computed as n*k + sum c[v], where n =|V| is the number of vertices, k is the current coloring number, and c[v] is the color of vertex v, with the sum taken over all vertices in |V|. A discussion of this measure is presented in [2] . Note that although k never increases as IG runs, the coloring sum may increase.
Suppose that on the 457th call to greedy a coloring sum was found less than any so far. The program would continue until at least 1457 calls to greedy were made. If a new minimum sum were found on 1329, then the program would continue on until at least 2329 calls were made. See section Future Changes for a much needed improvement.
The next set of prompts is concerned with the reordering of vertices between calls to greedy. The reader is referred to [1,2] for a discussion of these reorderings and their properties.
REORDER CONTROL INFORMATIONThe inputs in the last five lines above means that with probability 100/250 the vertices will be sorted so that color classes are in reverse order, with probability 100/250 the color classes will be randomly shuffled, and with probability 50/250 the classes will be sorted by decreasing size, with ties broken by reverse order.
Heuristic Controls
1 reverse order (else in order)
2 shuffle
4 largest first
8 smallest first
16 increasing total degree
32 decreasing total degree
Sum any subset, sorts [size[degree[shuffle,reverse,order]]]
Frequency, control - terminate by 0 0
100 1
100 2
50 5
0 0
[ 1] CLRS 32 FROM DSATURThe program looks for a file called file.res. If found then the file is scanned and a list of previously obtained colorings is presented. The user selects the coloring to start the iterated greedy process with.
[ 2] CLRS 17 FROM ITERATED GREEDY
[ 3] CLRS 23 FROM TABU
[ 4] CLRS 17 FROM ITERATED GREEDY
If the file file.res does not exist, or is empty, then the program starts with a trivial coloring, coloring the vertices with colors 1..n.
As the program runs, it outputs progress reports. When a reduction in the color sum occurs, a line beginning ``It='' is printed, with the iteration number, the current number of colors being uses, and the color sum. When a reduction in the number of colors used occurs, a line beginning ``COLOR'' is printed with number of colors, iteration number and the CPU time since the program started. Every 100 iterations, a line starting ``ITR'' is printed with the iteration number, number of colors and color sum.
In addition, if the cheat is present and requested by the user then proximity information is printed each time the number of colors is reduced and on every 1000 iterations, as well as at the beginning and end of the run. Typical lines look like
P= 761: 0 0 5 12 15 21 191 232 177 20 5 16 20 23 24These were output during a trial run on a 300 vertex graph with a hidden 15 coloring in which the color classes varied in size. The first line was output when a 31-coloring was obtained by the program, and the second was output when a 15 coloring was found.
P= 3121: 28 15 120 231 210 300 300 300 276 276 120 231 210 153 351
In this instance, there are 15 values printed following the ``:'', one for each of the hidden color classes. The number preceding the ``:'' is the sum of these numbers. Each of the trailing numbers represents the number of pairs of vertices from the color class that received the same color in the programs current coloring. For example, if hidden color class 3 had vertices <a,b,c,d,e,f> and the program assigned color 5 to <a,b,e>, color 9 to <c,f> and color 2 to <d>, then the proximity value for hidden class 3 would be 4.
In the above output, first line, classes 1 and 2 each have value 0, indicating that for each of these classes, no two vertices received the same color in the 31 coloring obtained by the program.
See reference [3]
for an example of how this information can be used to study the coloring
program behavior.
6. TABU
Synopsis:
tabu fileTABU is another local improvement search. It is based on partitioning the vertices of a graph into color classes that may not represent a legal coloring, then attempting to reduce the number of coloring violations, or conflicts , by moving vertices from one class to another. This program is based on the description in [10] , but see [1,2] for a description of differences from that paper.
Some of the differences will be apparent from the requested inputs listed below. In addition to the cheat and random seed, tabu issues the following prompts.
TABU CONTROL INFORMATIONEach iteration of TABU consists of generating a sample of neighbors; that is, partitions that can be obtained from the current one by moving one vertex to a different class. It then selects the neighbor partition that has the fewest conflicts, even if the neighbor has more conflicts than the current partition. The set of neighbors is restricted by a TABU list that prevents a vertex from moving back into a class that it was recently a member of in a previous iteration. This helps the program struggle out of local minima.
Maximum Iterations for tabu: 1000
Enter number of neighbors 100
Enter minimum number of neighbors 2
Enter tabu list size 7
The first input, 1000 in the above example, limits the number of iterations before quitting after the last improvement was detected. That is, if on iteration 247 a new (non-zero) global minimum in conflicts was obtained, then the program would continue to at least 1247 iterations before quitting. It will continue until either there is a sequence of 1000 iterations without improvement, or the number of conflicts is reduced to 0, indicating that a legal coloring has been obtained.
The second indicates that a maximum of 100 neighbors will be generated. TABU immediately stops generating neighbors if one of value lower than the current partition is found. However, the third input above indicates that this quick change will be limited in that before making the switch, TABU must examine at least two neighbors of lower value, picking the better of the two before switching to a new partition. Finally, in this example a vertex will not be allowed to move back into a partition from which it was previously removed for at least 7 iterations.
Enter the target color you want to try for: 15The first input tells TABU how many classes to use in the partition of the vertex set. The second asks how many times the program should increase the number of classes before giving up. For example, for the values above TABU will first try to find a 15 coloring, if that fails then it will increase the partitioning to 16 classes by adding an empty class, and try for a 16 coloring. If that fails, then it will add another empty class and try for a 17 coloring. If that fails, it will take the current partitioning as an ordering heuristic, apply the simple greedy algorithm and output that as its coloring.
If target not achieved, how many increases allowed: 2
[ 1] CLRS 32 FROM DSATURTABU will seed the partition it starts with by using the largest color sets from the indicated coloring as color classes, and then taking the remaining vertices and placing them one by one into the class in which they cause the fewest conflicts. For the example inputs, the vertices from the two smallest classes of the second coloring will be inserted into the largest 15 color classes. The hope is that this will give TABU a better start than a random partition. Note however that there is no guarantee that TABU will even find a coloring as good as the initial coloring.
[ 2] CLRS 17 FROM ITERATED GREEDY
[ 3] CLRS 23 FROM TABU
[ 4] CLRS 17 FROM ITERATED GREEDY
There are 4 colorings. Which do you want? 2
The proximity measure should be expanded to allow the values to be computed
as a cross between any two input sets of colorings, not just the cheat, as
a post mortem method of analysis. This would be even more useful
if the cheat were printed separately from the graph, and a further useful
feature of the generator program for evacuation graphs would be to output
the deceptive colorings as well as the hidden one, especially for graphs
with the hidden and deceptive colorings all having the same parameters.
References
Redistribution and use in source and binary forms, with or without modification, are permitted provided that the following conditions are met:
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.
This program was developed on SUN SPARC workstations running UNIX using the Gnu C compiler. It may or may not be portable to other systems.
Please send corrections, ideas for improvement, interesting results and random thoughts to joe@cs.ualberta.ca .