Graph coloring using Recursive-Large-First (RLF) algorithm

• Download source code - 5.04 KB

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 i^th and j^th 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).