Note

Graph coloring is a way of assigning colors to the vertices of a graph so that no two adjacent vertices share the same color. This is a classical problem in the field of graph theory and has applications in various domains like scheduling, map coloring, and solving Sudoku puzzles.

The simplest form of graph coloring is vertex coloring, where the aim is to minimize the number of colors used. This problem is NP-hard, meaning there is no known algorithm that can solve all instances of the problem efficiently (in polynomial time).

Greedy Coloring Algorithm:

  • Assign the first color to the first vertex.
  • Proceed to the next vertex and assign the lowest numbered color that hasn’t been used by its adjacent vertices.
  • Repeat this process for all vertices.

Code

#include <iostream>
#include <vector>

std::vector<int> greedy_coloring(const std::vector<int> &row_ptr,
                                 const std::vector<int> &col_idx) {
    int num_nodes = row_ptr.size() - 1;
    std::vector<int> colors(num_nodes,
                            -1);  // one element is modified by every node
    std::vector<bool> used(num_nodes, false);  // reset by every node
    colors[0] = 0;

    for (int i = 1; i < num_nodes; i++) {
        for (int j = row_ptr[i]; j < row_ptr[i + 1]; j++) {
            auto neighbor = col_idx[j];
            // mark the neighbor's color as used
            if (colors[neighbor] != -1) {
                used[colors[neighbor]] = true;
            }
        }
        int color = 0;
        // find the first unused color
        for (; color < num_nodes; color++) {
            if (!used[color]) {
                break;
            }
        }
        colors[i] = color;

        for (int j = row_ptr[i]; j < row_ptr[i + 1]; j++) {
            auto neighbor = col_idx[j];
            // reset the used array
            if (colors[neighbor] != -1) {
                used[colors[neighbor]] = false;
            }
        }
    }
    return colors;
}

int main() {
    /* Graph:
    0 -- 1
    |    |
    3 -- 2
    \  /
     4
    */
    std::vector<int> rowPtr = {0, 2, 4, 6, 8, 10};
    std::vector<int> colIndex = {1, 3, 0, 2, 1, 4, 0, 4, 2, 3};

    std::vector<int> colors = greedy_coloring(rowPtr, colIndex);

    // Print the result
    for (int i = 0; i < colors.size(); ++i) {
        std::cout << "Vertex " << i << " ---> Color " << colors[i] << std::endl;
    }

    return 0;
}