graph_coloring.cpp

Go to the documentation of this file.

 
#include <array>     
#include <iostream>  

namespace backtracking {
namespace graph_coloring {
template <size_t V>
void printSolution(const std::array<int, V>& color) {
    std::cout << "Following are the assigned colors\n";
    for (auto& col : color) {
        std::cout << col;
    }
    std::cout << "\n";
}

template <size_t V>
bool isSafe(int v, const std::array<std::array<int, V>, V>& graph,
            const std::array<int, V>& color, int c) {
    for (int i = 0; i < V; i++) {
        if (graph[v][i] && c == color[i]) {
            return false;
        }
    }
    return true;
}

template <size_t V>
void graphColoring(const std::array<std::array<int, V>, V>& graph, int m,
                   std::array<int, V> color, int v) {
    // base case:
    // If all vertices are assigned a color then return true
    if (v == V) {
        printSolution<V>(color);
        return;
    }
 
    // Consider this vertex v and try different colors
    for (int c = 1; c <= m; c++) {
        // Check if assignment of color c to v is fine
        if (isSafe<V>(v, graph, color, c)) {
            color[v] = c;
 
            // recur to assign colors to rest of the vertices
            graphColoring<V>(graph, m, color, v + 1);
 
            // If assigning color c doesn't lead to a solution then remove it
            color[v] = 0;
        }
    }
}
}  // namespace graph_coloring
}  // namespace backtracking

int main() {
    // Create following graph and test whether it is 3 colorable
    // (3)---(2)
    // |   / |
    // |  /  |
    // | /   |
    // (0)---(1)
 
    const int V = 4;  // number of vertices in the graph
    std::array<std::array<int, V>, V> graph = {
        std::array<int, V>({0, 1, 1, 1}), std::array<int, V>({1, 0, 1, 0}),
        std::array<int, V>({1, 1, 0, 1}), std::array<int, V>({1, 0, 1, 0})};
 
    int m = 3;  // Number of colors
    std::array<int, V> color{};
 
    backtracking::graph_coloring::graphColoring<V>(graph, m, color, 0);
    return 0;
}