TheAlgorithms/C++ 1.0.0
All the algorithms implemented in C++
Loading...
Searching...
No Matches
graph_coloring.cpp File Reference

prints the assigned colors using Graph Coloring algorithm More...

#include <array>
#include <iostream>
Include dependency graph for graph_coloring.cpp:

Go to the source code of this file.

Namespaces

namespace  backtracking
 for vector container
 
namespace  graph_coloring
 Functions for the Graph Coloring algorithm,.
 

Functions

template<size_t V>
void backtracking::graph_coloring::printSolution (const std::array< int, V > &color)
 A utility function to print the solution.
 
template<size_t V>
bool backtracking::graph_coloring::isSafe (int v, const std::array< std::array< int, V >, V > &graph, const std::array< int, V > &color, int c)
 Utility function to check if the current color assignment is safe for vertex v.
 
template<size_t V>
void backtracking::graph_coloring::graphColoring (const std::array< std::array< int, V >, V > &graph, int m, std::array< int, V > color, int v)
 Recursive utility function to solve m coloring problem.
 
int main ()
 Main function.
 

Detailed Description

prints the assigned colors using Graph Coloring algorithm

In graph theory, graph coloring is a special case of graph labeling; it is an assignment of labels traditionally called "colors" to elements of a graph subject to certain constraints. In its simplest form, it is a way of coloring the vertices of a graph such that no two adjacent vertices are of the same color; this is called a vertex coloring. Similarly, an edge coloring assigns a color to each edge so that no two adjacent edges are of the same color, and a face coloring of a planar graph assigns a color to each face or region so that no two faces that share a boundary have the same color.

Author
Anup Kumar Panwar
David Leal

Definition in file graph_coloring.cpp.

Function Documentation

◆ graphColoring()

template<size_t V>
void backtracking::graph_coloring::graphColoring ( const std::array< std::array< int, V >, V > & graph,
int m,
std::array< int, V > color,
int v )

Recursive utility function to solve m coloring problem.

Template Parameters
Vnumber of vertices in the graph
Parameters
graphmatrix of graph nonnectivity
mnumber of colors
[in,out]colordescription // used in,out to notify in documentation that this parameter gets modified by the function
vindex of graph vertex to check

Definition at line 81 of file graph_coloring.cpp.

82 {
83 // base case:
84 // If all vertices are assigned a color then return true
85 if (v == V) {
86 printSolution<V>(color);
87 return;
88 }
89
90 // Consider this vertex v and try different colors
91 for (int c = 1; c <= m; c++) {
92 // Check if assignment of color c to v is fine
93 if (isSafe<V>(v, graph, color, c)) {
94 color[v] = c;
95
96 // recur to assign colors to rest of the vertices
97 graphColoring<V>(graph, m, color, v + 1);
98
99 // If assigning color c doesn't lead to a solution then remove it
100 color[v] = 0;
101 }
102 }
103}
void printSolution(const std::array< int, V > &color)
A utility function to print the solution.
Graph Algorithms.

◆ isSafe()

template<size_t V>
bool backtracking::graph_coloring::isSafe ( int v,
const std::array< std::array< int, V >, V > & graph,
const std::array< int, V > & color,
int c )

Utility function to check if the current color assignment is safe for vertex v.

Template Parameters
Vnumber of vertices in the graph
Parameters
vindex of graph vertex to check
graphmatrix of graph nonnectivity
colorvector of colors assigned to the graph nodes/vertices
ccolor value to check for the node v
Returns
true if the color is safe to be assigned to the node
false if the color is not safe to be assigned to the node

Definition at line 61 of file graph_coloring.cpp.

62 {
63 for (int i = 0; i < V; i++) {
64 if (graph[v][i] && c == color[i]) {
65 return false;
66 }
67 }
68 return true;
69}

◆ main()

int main ( void )

Main function.

Returns
0 on exit

Definition at line 111 of file graph_coloring.cpp.

111 {
112 // Create following graph and test whether it is 3 colorable
113 // (3)---(2)
114 // | / |
115 // | / |
116 // | / |
117 // (0)---(1)
118
119 const int V = 4; // number of vertices in the graph
120 std::array<std::array<int, V>, V> graph = {
121 std::array<int, V>({0, 1, 1, 1}), std::array<int, V>({1, 0, 1, 0}),
122 std::array<int, V>({1, 1, 0, 1}), std::array<int, V>({1, 0, 1, 0})};
123
124 int m = 3; // Number of colors
125 std::array<int, V> color{};
126
128 return 0;
129}
void graphColoring(const std::array< std::array< int, V >, V > &graph, int m, std::array< int, V > color, int v)
Recursive utility function to solve m coloring problem.

◆ printSolution()

template<size_t V>
void backtracking::graph_coloring::printSolution ( const std::array< int, V > & color)

A utility function to print the solution.

Template Parameters
Vnumber of vertices in the graph
Parameters
colorarray of colors assigned to the nodes

Definition at line 41 of file graph_coloring.cpp.

41 {
42 std::cout << "Following are the assigned colors\n";
43 for (auto& col : color) {
44 std::cout << col;
45 }
46 std::cout << "\n";
47}