Department of Computing Science

University of Alberta

Edmonton, Alberta, Canada

T6G 2H1

This page is still being updated. FOR INFORMATION CONTACT
joe@cs.ualberta.ca

Information is currently unstable.

- Introduction and Overview
- A Note on the Source Code Structure
- Greedy
- DSATUR
- MAXIS
- Backtrack DSATUR
- Iterated Greedy
- TABU
- Future Changes
- References
- Conditions of Use

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

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

greedy fileThe

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:

**first**when there is more than one existing color class the vertex can enter, which one should be chosen;-
**second**what preordering to assign to the vertices.

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

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

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

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

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

Target Color - terminates if achieved:

Maximum branching factor:Entering a branching factor of

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

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

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

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

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

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

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.

- Culberson and Luo
DIMACS Series
, Volume 26
, "Cliques, Coloring and Satisfiability" Editors: David S. Johnson and Michael
A. Trick, 245-284, 1996.
- Culberson ``Iterated Greedy Graph Coloring and the Difficulty Landscape
'' Technical
Report TR92-07
- Culberson, Beacham and Papp
Hiding our colors
in CP'95 Workshop, Studying and Solving Really Hard Problems, Cassis, France,
pages 31--42, September 1995.
- Johnson, Aragon, McGeoch and Schevon ``Optimization by Simulated Annealing:
An Experimental Evaluation; Part {II}, Graph Coloring and Number Partitioning''
in Operations Research vol. 39, 378-406, 1991.
- Korman ``The Graph-Colouring Problem'' in Combinatorial Optimization,
Christofides, Mingozzi, Toth and Sandi Editors, 211--235, 1979.
- Daniel Brelaz ``New Methods to Color the Vertices of a Graph'' in
CACM(22), 251-256, 1979.
- Bollobas and Thomason ``Random Graphs of Small Order'' in Random Graphs
'83, 47-97, 1985.
- Bennet Manvel ``Extremely Greedy Coloring Algorithms'' in Graphs and
Applications (Proceedings of the First Colorado Symposium on Graph Theory,
1982), Frank Harary and John S. Maybee (Eds.) 257-270, 1985.
- G. Campers and O. Henkes and J. P. Leclerq ``Graph Coloring Heuristics:
A Survey, Some New Propositions and Computational Experiences on Random and
`{L}eighton's' Graphs'' in Operational Research '87 (Buenos Aires, 1987)
917-932, 1988.
- A. Hertz and D. de Werra ``Using Tabu Search Techniques for Graph Coloring'' in Computing(39) 345-351, 1987.

Redistribution and use in source and binary forms, with or without modification, are permitted provided that the following conditions are met:

- Redistributions of source code must retain the above copyright notice, this list of conditions and the following disclaimer.
- Redistributions in binary form must reproduce the above copyright notice, this list of conditions and the following disclaimer in the documentation and/or other materials provided with the distribution.
- All advertising materials mentioning features or use of this software must display the following acknowledgement: This product includes software developed by Joseph Culberson at the University of Alberta.
- 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.

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 .