Introduction
In this blog, we will discuss a problem based on graph coloring. Graphs-based coding problems are widely asked in competitive programming contests and various coding interviews. Here we will discuss the DSatur algorithm for graph coloring. The DSatur algorithm is the most efficient algorithm for graph coloring.
Problem Statement
You are given a graph with ‘V’ vertices and ‘E’ edges connecting them. Your task is to color all the vertices such that it satisfies the following two conditions:
- The pair of adjacent vertices will always be of different colors.
- The count of different colors should be minimum.
Explanation
Before moving further, we need to understand what is a chromatic number. The minimum number of colors required to color the graph such that adjacent vertices have different colors is known as the chromatic number, denoted by X(G). Here, we need to calculate the chromatic number of the given graph. For example, we need three different colors to color all the vertices in the following diagram. Hence, the chromatic number of the given graph is 3.
The brute force for this problem is less efficient and very complex to implement as we need to check each possible coloring and optimally find the minimum out of them. Therefore we need to find it optimally using the DSatur algorithm. Let’s start with the DSatur algorithm,
DSatur Algorithm abbreviated from “degree of saturation algorithm.” It is based on the Greedy Algorithm. The count of different colors assigned to the adjacent vertices of the given vertex is known as its saturation degree.
Algorithm
The DSatur algorithm is as follows:
- Select uncolored vertex ‘V’ among all uncolored vertex whose saturation degree is maximum. If two or more vertices have the same saturation degree, select one with the maximum degree subgraph induced by the uncolored graph.
- Find the smallest integer between 0 to ‘V’, which is not assigned to its neighbor vertices, and assign that color to the vertex ‘V’. This integer value represents the color of that vertex.
- Repeat the above steps for all the vertices.
Code
// Program for DSatur Algorithm for graph coloring.
#include <iostream>
#include <vector>
#include <set>
#include <tuple>
using namespace std;
// Function to add edge between two vertices.
void addEdgeBetween(vector<int> graph[], int a, int b)
{
graph[a].push_back(b);
graph[b].push_back(a);
}
// For storing information related to vertices.
class vertexInfo
{
public:
// Saturation degree of the vertex.
int sat;
// degree in uncolored graph
int deg;
// index of vertex.
int vertex;
};
struct maxSat
{
bool operator()(const vertexInfo &lhs,
const vertexInfo &rhs) const
{
return tie(lhs.sat, lhs.deg, lhs.vertex) > tie(rhs.sat, rhs.deg, rhs.vertex);
}
};
// Function to print color of each vertex of graph.
void printcolor(vector<int> &color)
{
for (int i = 0; i < color.size(); i++)
{
cout << "The Color of the vertex " << i << " is " << color[i] << endl;
}
}
// Function for DSatur algo.
int DSatur(vector<int> graph[], int V)
{
int u, i;
// Create vector to store status of used colors.
vector<bool> use(V, false);
// Create vector to store colors.
vector<int> color(V), d(V);
vector<set<int>> adjCols(V);
set<vertexInfo, maxSat> Q;
set<vertexInfo, maxSat>::iterator maxPtr;
for (u = 0; u < V; u++)
{
color[u] = -1;
d[u] = graph[u].size();
adjCols[u] = set<int>();
Q.emplace(vertexInfo{0, d[u], u});
}
while (!Q.empty())
{
maxPtr = Q.begin();
u = (*maxPtr).vertex;
Q.erase(maxPtr);
for (int v : graph[u])
if (color[v] != -1)
use[color[v]] = true;
i = 0;
while (i != use.size())
{
if (use[i] == false)
break;
i++;
}
for (auto v : graph[u])
if (color[v] != -1)
use[color[v]] = false;
color[u] = i;
for (auto v : graph[u])
{
if (color[v] == -1)
{
Q.erase(
{int(adjCols[v].size()),
d[v], v});
adjCols[v].insert(i);
d[v]--;
Q.emplace(vertexInfo{
int(adjCols[v].size()),
d[v], v});
}
}
}
set<int> ans;
for (int i = 0; i < V; i++)
ans.insert(color[i]);
printcolor(color);
// Return Chromatic number.
// Print the Chromatic number of graph coloring.
cout << "The Chromatic number is : ";
return ans.size();
}
// Function to calculate Chromatic numvber.
int getChromaticNumber()
{
// Input number of vertices 'V' and edges 'E'.
int V, E;
cin >> V >> E;
// Create graph of ‘V’ vertices from 0 to V - 1.
vector<int> graph[V];
for (int i = 0; i < E; i++)
{
// Input edge from vertex 'A' to vertex 'B'.
int a, b;
cin >> a >> b;
// Insert edge between the vertices.
addEdgeBetween(graph, a, b);
}
return DSatur(graph, V);
}
int main()
{
cout << getChromaticNumber();
return 0;
}
Input
5 7
1 2
0 3
4 1
2 1
4 2
1 3
4 2
Output
The Color of the vertex 0 is 1
The Color of vertex 1 is 1
The Color of vertex 2 is 0
The Color of vertex 3 is 0
The Color of vertex 4 is 2
The chromatic number is : 3
Complexity Analysis
O((V + E) * log(V)), where ‘V’ is the number of vertices, and ‘E’ is the number of Edges.
As traversing of adjacency list takes O(V+E) and searching in the set takes O(log(V)).
The creation of an adjacency list takes O(V+E) space where ‘V’ is the number of vertices, and ‘E’ is the total number of edges. Hence, its space complexity is O(V+E).