The DSatur algorithm created by Daniel Brelaz in 1979 is designed to achieve graph coloring by effectively assigning colors to the vertices of a graph in order to reduce the overall number of colors utilized. DSatur proves to be extremely effective and uncomplicated, particularly when dealing with large-scale graphs. The algorithm's title, Degree of Saturation, holds significant relevance within the algorithm as it elucidates the core principle behind its operation.
The core principle of DSatur revolves around arranging vertices according to their saturation degree metric. This metric indicates how many colors are already assigned to neighboring vertices. By leveraging the saturation degree concept, DSatur aims to selectively choose vertices, giving priority to those with higher saturation degrees during the coloring process. This approach ensures that vertices with a wider range of coloring choices are prioritized, potentially leading to an optimal coloring outcome.
The algorithm reveals its process through a meticulously crafted series of actions. Initially, an empty priority queue is initialized, and the saturation degree of each node is initialized to zero. Subsequently, vertices are dequeued based on their saturation degree from the priority queue, with random selection in case of ties. These selected vertices are then colored, ensuring that adjacent vertices have distinct colors. As new colors are assigned to neighboring vertices, the saturation level of each vertex is updated accordingly. This process iterates until all vertices are colored, marking the conclusion of the procedure.
Expanding on this, the DSatur technique facilitates the merging of high-degree selection and strategic color assignment. It focuses on nodes with higher saturation levels to prioritize those with limited color choices initially. This can involve utilizing the minimum amount of color necessary to cover all the nodes. Additionally, the straightforward nature and broad applicability of DSatur prove beneficial for handling both undirected and directed graphs, as well as graph coloring tasks.
Graph Colouring:
Assigning colors to the vertices of a graph in such a way that adjacent vertices have different colors is known as graph coloring. The main objective is to reduce the total number of colors used while maintaining this rule. This challenge is significant in practical scenarios like scheduling, register assignment, and geographical map coloring.
Saturation Degree:
The saturation level of a vertex indicates the number of distinct colors assigned to its adjacent vertices. Vertices with increased saturation levels face more restrictions, as they have fewer color options. Consequently, vertices with higher saturation levels are typically given precedence during the coloring phase, as coloring them could impose fewer constraints on neighboring vertices. Having a good grasp of saturation levels is essential for effectively coloring graphs and reducing the overall color count.
Approach-1: Adjacency List Representation with Priority Queue
The technique known as "Adjacency List Representation with Priority Queue" for implementing the DSatur algorithm in C++ involves using an adjacency list to depict the graph, with each vertex keeping track of its neighboring vertices. By employing a priority queue to organize vertices according to their saturation levels, this method facilitates the effective selection process during the coloring phase. It adeptly handles the saturation degree updates and prioritizes vertices with higher saturation levels for coloring purposes. This strategy strikes a harmonious balance between simplicity and efficiency, establishing it as a favored option for executing the DSatur algorithm in C++, especially when dealing with extensive graphs.
Program:
#include <iostream>
#include <vector>
#include <queue>
#include <algorithm>
#include <unordered_set>
using namespace std;
// Structure to represent a vertex in the graph
struct Vertex {
int id;
int colour;
int saturationDegree;
unordered_set<int> neighbors;
Vertex(int id) : id(id), colour(-1), saturationDegree(0) {}
};
//Function to print the adjacency list representation of the graph
void printGraph(const vector<Vertex>& graph) {
for (const Vertex& v : graph) {
cout << "Vertex " << v.id << ": ";
for (int neighbor : v.neighbors) {
cout << neighbor << " ";
}
cout << endl;
}
}
//Function to implement DSatur algorithm for graph colouring
void DSaturColouring(vector<Vertex>& graph) {
// Priority queue to manage vertices based on saturation degree
auto cmp = [](const Vertex& v1, const Vertex& v2) {
return v1.saturationDegree < v2.saturationDegree;
};
priority_queue<Vertex, vector<Vertex>, decltype(cmp)> pq(cmp);
// Initialize the saturation degree of each vertex
for (Vertex& v : graph) {
for (int neighbor : v.neighbors) {
v.saturationDegree++;
}
pq.push(v);
}
// Colouring process
while (!pq.empty()) {
Vertex current = pq.top();
pq.pop();
// Find the smallest available colour for the current vertex
unordered_set<int> usedColours;
for (int neighbor : current.neighbors) {
if (graph[neighbor].colour != -1) {
usedColours.insert(graph[neighbor].colour);
}
}
int colour = 0;
while (usedColours.find(colour) != usedColours.end()) {
colour++;
}
// Assign colour to the current vertex
graph[current.id].colour = colour;
// Update saturation degrees of neighbours
for (int neighbor : current.neighbors) {
if (graph[neighbor].colour == -1) {
graph[neighbor].saturationDegree--;
pq.push(graph[neighbor]); // Re-insert into priority queue
}
}
}
}
int main() {
// Sample graph 1
vector<Vertex> graph1 = {
Vertex(0),
Vertex(1),
Vertex(2),
Vertex(3),
Vertex(4)
};
graph1[0].neighbors = {1, 2};
graph1[1].neighbors = {0, 2, 3};
graph1[2].neighbors = {0, 1, 3, 4};
graph1[3].neighbors = {1, 2, 4};
graph1[4].neighbors = {2, 3};
// Sample graph 2
vector<Vertex> graph2 = {
Vertex(0),
Vertex(1),
Vertex(2),
Vertex(3)
};
graph2[0].neighbors = {1, 2};
graph2[1].neighbors = {0, 2, 3};
graph2[2].neighbors = {0, 1};
graph2[3].neighbors = {1};
// Print the adjacency list representations of the graphs
cout << "Graph 1:" << endl;
printGraph(graph1);
cout << "Graph 2:" << endl;
printGraph(graph2);
// Colour the graphs using the DSatur algorithm
DSaturColouring(graph1);
DSaturColouring(graph2);
// Print the colours assigned to vertices
cout << "\nColours for Graph 1:" << endl;
for (const Vertex& v : graph1) {
cout << "Vertex " << v.id << ": Colour " << v.colour << endl;
}
cout << "\nColours for Graph 2:" << endl;
for (const Vertex& v : graph2) {
cout << "Vertex " << v.id << ": Colour " << v.colour << endl;
}
return 0;
}
Output:
Graph 1:
Vertex 0: 2 1
Vertex 1: 2 3 0
Vertex 2: 4 3 1 0
Vertex 3: 2 4 1
Vertex 4: 3 2
Graph 2:
Vertex 0: 2 1
Vertex 1: 2 3 0
Vertex 2: 1 0
Vertex 3: 1
Colours for Graph 1:
Vertex 0: Colour 2
Vertex 1: Colour 1
Vertex 2: Colour 0
Vertex 3: Colour 2
Vertex 4: Colour 1
Colours for Graph 2:
Vertex 0: Colour 2
Vertex 1: Colour 0
Vertex 2: Colour 1
Vertex 3: Colour 1
Explanation:
The given code showcases a thorough example of the DSatur algorithm for coloring graphs in C++. It utilizes an adjacency list structure and a priority queue for efficient implementation.
It demonstrates the procedure of determining saturation levels, choosing vertices according to saturation levels, and allocating colors to vertices with the constraint that neighboring vertices must have distinct colors. This approach is versatile and can be used for solving different graph coloring issues, serving as a fundamental illustration of the DSatur algorithm in real-world scenarios.
- Graph Representation:
The code introduces a Vertex struct to depict every vertex within the graph. Each vertex comprises of an identifier, a color value (set to -1 by default), a saturation level, and a collection of adjacent vertices kept in an unordered set.
Two example charts are generated using arrays of Vertex objects. The adjacency lists of these charts are set by hand through indicating the adjacent vertices for each vertex.
- Initializing the Priority Queue:
The DSatur algorithm depends on a priority queue to organize vertices according to their saturation levels. A specialized comparator function is established to assess vertices by their saturation levels, and a priority queue named pq is initialized using this comparator.
- Calculating Saturation Degrees:
The saturation level of every node is determined by traversing its adjacent nodes and increasing the saturation level for each adjacent node. Subsequently, each node is added to the priority queue pq for additional processing.
- Coloring Algorithm:
The primary DSatur algorithm initiates by iteratively picking vertices with the greatest saturation degree from the priority queue. When a vertex is selected, the algorithm identifies the smallest unused color among its neighboring vertices.
Subsequently, the chosen vertex receives this hue, and the saturation levels of its adjacent vertices are adjusted accordingly. This sequence persists until the priority queue pq becomes vacant, signifying that all vertices have been assigned colors.
Once the graphs have been colored with the DSatur algorithm, the program will output the assigned colors for every vertex in both graphs. The colors will be shown following the pattern "Vertex ID: Color".
Complexity Analysis:
Time Complexity:
Initialization (Graph Creation):
Generating the adjacency list depiction of the graph requires traversing through each vertex along with its adjacent nodes.
The time complexity is O(V + E), with V representing the quantity of vertices and E representing the number of edges in the graph.
Saturation Degree Calculation:
The process loops through each neighboring vertex to compute the saturation level.
The time complexity of the algorithm is O(V * avgdegree), where avgdegree represents the mean degree of vertices within the graph.
Priority Queue Operations:
During the primary loop of the DSatur algorithm, tasks such as adding, removing, and identifying the highest element in the priority queue are executed. Within each cycle, the algorithm might carry out tasks on the priority queue corresponding to the quantity of vertices.
The time complexity averages at O(V * log(V)) by taking into account the operations of the priority queue.
Colour Assignment and Saturation Degree Updates:
Assigning colors to nodes and adjusting the saturation levels of adjacent nodes are tasks carried out within the DSatur algorithm iteration. These procedures entail looping through neighboring nodes, with the iteration count varying based on the saturation levels.
Overall time complexity inside the loop is O(V * avg_degree), which closely resembles the computation for saturation degree.
Total Time Complexity:
The primary elements influencing the time complexity include the setup process (O(V + E)) and the iteration of the DSatur algorithm (O(V * log(V))).
Therefore, the general time complexity of executing the DSatur algorithm is commonly O(V * log(V)).
Space Complexity:
Adjacency List Representation:
The DSatur algorithm utilizes an adjacency list to hold vertices and their adjacent vertices. This method necessitates extra memory that scales with the number of vertices and edges, resulting in a space complexity of O(V + E).
Priority Queue:
DSatur employs a priority queue to hold vertices according to their saturation degrees. This priority queue necessitates storage space for all vertices, adding O(V) to the total space complexity.
Additional Data Structures:
Different supplementary data structures are utilized, like collections for holding utilized colors, unsorted collections for adjacent vertices, and variables for saturation levels. While they usually need space in proportion to the number of vertices, they introduce an extra O(V) to the overall space complexity.
Total Space Complexity:
The primary element influencing space complexity is the adjacency list structure, resulting in an overall space complexity of O(V + E) when implementing the DSatur algorithm.
Approach-2: Adjacency Matrix Representation with Priority Queue
The technique known as "Utilizing Adjacency Matrix with Priority Queue" involves using an adjacency matrix to illustrate the graph. In this representation, each cell within the matrix denotes the presence or absence of a connection between two vertices. Furthermore, a priority queue is utilized to organize vertices according to their saturation levels, facilitating effective selection during the coloring process. The saturation levels are promptly adjusted following each color assignment to uphold the precision of vertex prioritization.
This technique presents a direct and effective approach for applying the DSatur algorithm to color graphs in C++. It is especially beneficial for dense graphs, where adjacency matrices offer a more compact storage solution compared to adjacency lists. By leveraging the adjacency matrix to depict the graph's connections concisely and utilizing a priority queue for streamlined vertex handling, this strategy harmonizes ease of implementation with computational efficiency when addressing graph coloring challenges.
Program:
#include <iostream>
#include <vector>
#include <queue>
#include <unordered_set>
using namespace std;
// Structure to represent a vertex in the graph
struct Vertex {
int id;
int colour;
int saturationDegree;
Vertex(int id) : id(id), colour(-1), saturationDegree(0) {}
};
//Function to print the adjacency matrix representation of the graph
void printGraph(const vector<vector<int>>& adjacencyMatrix, int vertices) {
cout << "Adjacency Matrix:" << endl;
for (int i = 0; i < vertices; ++i) {
for (int j = 0; j < vertices; ++j) {
cout << adjacencyMatrix[i][j] << " ";
}
cout << endl;
}
}
//Function to implement DSatur algorithm for graph colouring using adjacency matrix
void DSaturColouring(vector<vector<int>>& adjacencyMatrix, vector<Vertex>& graph, int vertices) {
// Priority queue to manage vertices based on saturation degree
auto cmp = [](const Vertex& v1, const Vertex& v2) {
return v1.saturationDegree < v2.saturationDegree;
};
priority_queue<Vertex, vector<Vertex>, decltype(cmp)> pq(cmp);
// Initialize the saturation degree of each vertex
for (int i = 0; i < vertices; ++i) {
for (int j = 0; j < vertices; ++j) {
if (adjacencyMatrix[i][j] == 1) {
graph[i].saturationDegree++;
}
}
pq.push(graph[i]);
}
// Colouring process
while (!pq.empty()) {
Vertex current = pq.top();
pq.pop();
// Find the smallest available colour for the current vertex
unordered_set<int> usedColours;
for (int i = 0; i < vertices; ++i) {
if (adjacencyMatrix[current.id][i] == 1 && graph[i].colour != -1) {
usedColours.insert(graph[i].colour);
}
}
int colour = 0;
while (usedColours.find(colour) != usedColours.end()) {
colour++;
}
// Assign colour to the current vertex
graph[current.id].colour = colour;
// Update saturation degrees of neighbors
for (int i = 0; i < vertices; ++i) {
if (adjacencyMatrix[current.id][i] == 1 && graph[i].colour == -1) {
graph[i].saturationDegree--;
pq.push(graph[i]); // Re-insert into priority queue
}
}
}
}
int main() {
// Sample graph 1
int vertices1 = 5;
vector<vector<int>> adjacencyMatrix1 = {
{0, 1, 1, 0, 0},
{1, 0, 1, 1, 0},
{1, 1, 0, 1, 1},
{0, 1, 1, 0, 1},
{0, 0, 1, 1, 0}
};
vector<Vertex> graph1;
for (int i = 0; i < vertices1; ++i) {
graph1.push_back(Vertex(i));
}
// Sample graph 2
int vertices2 = 4;
vector<vector<int>> adjacencyMatrix2 = {
{0, 1, 1, 0},
{1, 0, 1, 1},
{1, 1, 0, 0},
{0, 1, 0, 0}
};
vector<Vertex> graph2;
for (int i = 0; i < vertices2; ++i) {
graph2.push_back(Vertex(i));
}
// Print the adjacency matrix representations of the graphs
cout << "Graph 1:" << endl;
printGraph(adjacencyMatrix1, vertices1);
cout << "Graph 2:" << endl;
printGraph(adjacencyMatrix2, vertices2);
// Colour the graphs using the DSatur algorithm
DSaturColouring(adjacencyMatrix1, graph1, vertices1);
DSaturColouring(adjacencyMatrix2, graph2, vertices2);
// Print the colours assigned to vertices
cout << "\nColours for Graph 1:" << endl;
for (const Vertex& v : graph1) {
cout << "Vertex " << v.id << ": Colour " << v.colour << endl;
}
cout << "\nColours for Graph 2:" << endl;
for (const Vertex& v : graph2) {
cout << "Vertex " << v.id << ": Colour " << v.colour << endl;
}
return 0;
}
Output:
Graph 1:
Adjacency Matrix:
0 1 1 0 0
1 0 1 1 0
1 1 0 1 1
0 1 1 0 1
0 0 1 1 0
Graph 2:
Adjacency Matrix:
0 1 1 0
1 0 1 1
1 1 0 0
0 1 0 0
Colours for Graph 1:
Vertex 0: Colour 2
Vertex 1: Colour 1
Vertex 2: Colour 0
Vertex 3: Colour 2
Vertex 4: Colour 1
Colours for Graph 2:
Vertex 0: Colour 2
Vertex 1: Colour 0
Vertex 2: Colour 1
Vertex 3: Colour 1
Explanation:
- Graph Representation:
The code establishes a Vertex struct to depict individual vertices within the graph. Every vertex encompasses an ID, a color value (set to -1 by default), and a saturation level.
Generating two example diagrams involves the utilization of adjacency matrices, with each cell denoting the presence or absence of a connection between two vertices.
- Displaying Adjacency Matrices:
The printGraph method is responsible for displaying the adjacency matrix representation of graphs. It loops through the elements within the adjacency matrix and outputs them sequentially, row by row.
- Implementing the DSatur Algorithm:
The DSatur algorithm is coded within the DSaturColouring Function. It accepts input parameters such as the adjacency matrix, a vector containing Vertex objects that depict the graph, and the total number of vertices.
The Function sets up a priority queue to handle vertices according to their saturation degrees. Initially, the vertices are added to the priority queue after computing their saturation degrees. The primary DSatur algorithm loop starts by removing vertices from the priority queue based on their saturation degrees.
For every vertex that is removed from the queue, the procedure identifies the smallest available color that has not been utilized by its adjacent vertices. Subsequently, the vertex is allocated this color, and its saturation level is adjusted. The saturation levels of adjacent vertices are modified correspondingly, and the impacted vertices are placed back into the priority queue. This sequence persists until the priority queue is devoid of elements, signifying that all vertices have been assigned colors.
Once the graphs have been colored utilizing the DSatur algorithm, the script outputs the assigned colors for every vertex in the graphs. The color assignments are shown in the following format: "Vertex ID: Color".
Complexity Analysis:
Time Complexity:
Initialization (Graph Creation):
Generating the adjacency matrix requires iterating through each vertex and its possible connections, leading to a time complexity of O(V^2), with V representing the quantity of vertices.
Saturation Degree Calculation:
Determining saturation levels includes navigating through the adjacency matrix to tally adjacent vertices, necessitating O(V^2) computations.
Priority Queue Operations:
Performing actions within the priority queue while executing the DSatur algorithm loop, like adding, removing, and identifying the highest element, generally demand O(log V) time for each action. Considering there are V vertices, the total time complexity for priority queue activities stands at O(V * log V).
Colour Assignment and Saturation Degree:
When inside the DSatur algorithm loop, assigning colors and updating saturation levels includes looping through adjacent vertices, potentially requiring O(V) time in the most unfavorable scenario. This process is executed for every vertex within the graph, leading to an overall time complexity of O(V^2).
Total Time Complexity:
The primary elements influencing the time complexity include the setup phase (O(V^2)) and the execution loop of the DSatur algorithm (O(V^2)).
Therefore, the total time complexity of utilizing the DSatur algorithm with an adjacency matrix and a priority queue is O(V^2).
Space Complexity:
Adjacency Matrix:
Storing the connectivity between vertices using the adjacency matrix representation requires O(V^2) space, where V represents the total number of vertices in the graph.
Priority Queue:
The priority queue organizes vertices according to their saturation degrees, necessitating extra storage that scales with the number of vertices, denoted as O(V).
Additional Data Structures:
Utilizing data structures like sets to store colors and variables to represent saturation levels results in extra memory usage, which scales in direct proportion to the number of vertices, denoted as O(V).
Total Space Complexity:
The primary factor that impacts space complexity in the DSatur algorithm implementation is the adjacency matrix representation, which has a time complexity of O(V^2). Thus, the overall space complexity of the DSatur algorithm implementation is O(V^2).
