Graph coloring using Recursive-Large-First (RLF) algorithm
4.20/5 (5 votes)
An implement of the Recursive-Large_First graph coloring in C/C++ language.
What is graph coloring
A coloring of a simple graph is the assignment of a color to each vertex of the graph so that no two adjacent vertices are assigned the same color. The chromatic number of a graph is the least number of colors needed for coloring of the graph. The problem here is to color a graph with its chromatic number.
Suppose that we are coloring a simple undirected graph.
Given a graph with n vertices. This algorithm will color each vertex with a number. F(x) is the color of vertex x.
In this article, I am using the Recursive-Largest-First algorithm by F. T. Leighton. Here is the pseudo code:
colornumber = 0; //number of used colors
while (number_of_uncolored_vertex > 0){
determine a vertex x of maximal degree in G;
colornumber = colornumber + 1;
F(x) = colornumber;
NN = set of non-neighbors of x;
while (cardinality_of_NN > 0){ //Find y in NN to be contracted into x
maxcn = 1; //becomes the maximal number of common neighbors
ydegree = 1; //becomes degree(y)
for every vertex z in NN{
cn=number of common neighbors of z and x;
if (cn > maxcn or (cn == maxcn and degree(z) < ydegree)){
y = z;
ydegree = degree(y);
maxcn = cn;
}
}
if (maxcn == 0){ //in this case G is unconnected
y=vertex of maximal degree in NN;
}
F(y) = colornumber;
contract y into x;
update the set NN of non-neighbors of x;
}
G = G x; //remove x from G
}
Data structure
We can use an adjacency matrix to store the adjacent status of the vertices. If the graph has n vertices, there will be an n-degree square adjacency matrix.
a[i][j] will be 1 if the ith and jth vertices are adjacent, and 0 otherwise. For example:
// below is the adjacency matrix
7 // number of vertices
0 1 1 0 1 1 0
1 0 0 1 0 1 1
1 0 0 1 1 1 0
0 1 1 0 0 1 1
1 0 1 0 0 0 1
1 1 1 1 0 0 0
0 1 0 1 1 0 0
We will color the vertices with numbers instead of color, uUsing an array color[n] to store the numbers. For example: color[0] stores the color number of the first vertex, so color[0] = 3 means we colored vertex 1 with color 3.
C/C++ code
Here is the ariables declaration:
// this program will work with graphs
// of which number of vertices is smaller or equal to 100
const int MAX = 100;
// necessary variables
// n is the number of vertices of the graph
int n;
// a[n][n] is the adjacency matrix of the graph
// a[i][j] = 1 if i-th and j-th vertices are adjacent
int a[MAX][MAX];
// array color[n] stores the colors of the vertices
// color[i] = 0 if we 've not colored it yet
int color[MAX];
// array degree[n] stores the degrees of the vertices
int degree[MAX];
// array NN[] stores all the vertices that is not adjacent to current vertex
int NN[MAX];
// NNCount is the number of that set
int NNCount;
// unprocessed is the number of vertices with which we 've not worked
int unprocessed;
Here is the coloring function:
// processing function
void Coloring()
{
int x,y;
int ColorNumber = 0;
int VerticesInCommon = 0;
while (unprocessed>0) // while there is an uncolored vertex
{
x = MaxDegreeVertex(); // find the one with maximum degree
ColorNumber ++;
color[x] = ColorNumber; // give it a new color
unprocessed --;
UpdateNN(ColorNumber); // find the set of non-neighbors of x
while (NNCount>0)
{
// find y, the vertex has the maximum neighbors in common with x
// VerticesInCommon is this maximum number
y = FindSuitableY(ColorNumber, VerticesInCommon);
// in case VerticesInCommon = 0
// y is determined that the vertex with max degree in NN
if (VerticesInCommon == 0)
y = MaxDegreeInNN();
// color y the same to x
color[y] = ColorNumber;
unprocessed --;
UpdateNN(ColorNumber);
// find the new set of non-neighbors of x
}
}
}
Other necessary functions:
// function that reads input from file named "input.txt" in the same folder
void GetInput()
{
ifstream in("input.txt");
in >> n; // read the number of vertices first
for (int i=0; i < n; i++) // then read the adjacency matrix
for (int j=0; j < n; j++)
in >> a[i][j]; // read the element one by one
in.close();
}
// initializing function
void Init()
{
for (int i=0; i < n; i++)
{
color[i] = 0; // be sure that at first, no vertex is colored
degree[i] = 0; // count the degree of each vertex
for (int j = 0; j < n; j++)
if (a[i][j] == 1) // if i-th vertex is adjacent to another
degree[i] ++; // increase its degree by 1
}
NNCount = 0; // number of element in NN set
unprocessed = n;
}
// this function finds the unprocessed vertex of which degree is maximum
int MaxDegreeVertex()
{
int max = -1;
int max_i;
for (int i =0; i < n; i++)
if (color[i] == 0)
if (degree[i]>max)
{
max = degree[i];
max_i = i;
}
return max_i;
}
// this function is for UpdateNN function
// it reset the value of scanned array
void scannedInit(int scanned[MAX])
{
for (int i=0; i < n; i++)
scanned[i] = 0;
}
// this function updates NN array
void UpdateNN(int ColorNumber)
{
NNCount = 0;
// firstly, add all the uncolored vertices into NN set
for (int i=0; i < n; i++)
if (color[i] == 0)
{
NN[NNCount] = i;
NNCount ++; // when we add a vertex, increase the NNCount
}
// then, remove all the vertices in NN that
// is adjacent to the vertices colored ColorNumber
for (int i=0; i < n; i++)
if (color[i] == ColorNumber) // find one vertex colored ColorNumber
for (int j=0; j < NNCount; j++)
while (a[i][NN[j]] == 1)
// remove vertex that adjacent to the found vertex
{
NN[j] = NN[NNCount - 1];
NNCount --; // decrease the NNCount
}
}
// this function will find suitable y from NN
int FindSuitableY(int ColorNumber, int& VerticesInCommon)
{
int temp,tmp_y,y;
// array scanned stores uncolored vertices
// except the vertex is being processing
int scanned[MAX];
VerticesInCommon = 0;
for (int i=0; i < NNCount; i++) // check the i-th vertex in NN
{
// tmp_y is the vertex we are processing
tmp_y = NN[i];
// temp is the neighbors in common of tmp_y
// and the vertices colored ColorNumber
temp = 0;
scannedInit(scanned);
//reset scanned array in order to check all
//the vertices if they are adjacent to i-th vertex in NN
for (int x=0; x < n; x++)
if (color[x] == ColorNumber) // find one vertex colored ColorNumber
for (int k=0; k < n; k++)
if (color[k] == 0 && scanned[k] == 0)
if (a[x][k] == 1 && a[tmp_y][k] == 1)
// if k is a neighbor in common of x and tmp_y
{
temp ++;
scanned[k] = 1; // k is scanned
}
if (temp > VerticesInCommon)
{
VerticesInCommon = temp;
y = tmp_y;
}
}
return y;
}
// find the vertex in NN of which degree is maximum
int MaxDegreeInNN()
{
int tmp_y; // the vertex has the current maximum degree
int temp, max = 0;
for (int i=0; i < NNCount; i++)
{
temp = 0;
for (int j=0; j < n; j++)
if (color[j] == 0 && a[NN[i]][j] == 1)
temp ++;
if (temp>max) // if the degree of vertex NN[i] is higher than tmp_y's one
{
max = temp; // assignment NN[i] to tmp_y
tmp_y = NN[i];
}
}
if (max == 0) // so all the vertices have degree 0
return NN[0];
else // exist a maximum, return it
return tmp_y;
}
// print out the output
void PrintOutput()
{
for (int i=0; i < n; i++)
// element i-th of array color stores the color of (i+1)-th vertex
cout << "Vertex " << i+1
<< " is colored " << color[i] << endl;
}
// main function
void main()
{
GetInput(); // read the input adjacency matrix from file
Init(); // initialize the data : degree, color array ..
Coloring(); // working function
PrintOutput(); // print the result onto the console lines
getch();
}
Result
This is the result for the above example:
Reference
- Graph coloring in Wiki
- Leighton, F. T., A graph coloring algorithm for large scheduling problems, Journal of Research of the National Bureau of Standards 84 (1979).