graph_coloring.cpp File Reference

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

#include <array>
#include <iostream>
#include <vector>

Include dependency graph for graph_coloring.cpp:

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

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

V	number of vertices in the graph

Parameters

	graph	matrix of graph nonnectivity
	m	number of colors
[in,out]	color	description // used in,out to notify in documentation that this parameter gets modified by the function
	v	index of graph vertex to check

                                                  {
    // 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;
        }
    }
}

Here is the call graph for this function:

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

V	number of vertices in the graph

Parameters

v	index of graph vertex to check
graph	matrix of graph nonnectivity
color	vector of colors assigned to the graph nodes/vertices
c	color 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

                                                  {
    for (int i = 0; i < V; i++) {
        if (graph[v][i] && c == color[i]) {
            return false;
        }
    }
    return true;
}

Here is the call graph for this function:

main()

int main

(

void

)

Main function.

Returns

0 on exit

           {
    // 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;
}

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

V	number of vertices in the graph

Parameters

color

array of colors assigned to the nodes

                                                  {
    std::cout << "Following are the assigned colors\n";
    for (auto& col : color) {
        std::cout << col;
    }
    std::cout << "\n";
}

Here is the call graph for this function: