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:

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

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

Definition at line 82 of file graph_coloring.cpp.

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

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

Definition at line 62 of file graph_coloring.cpp.

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

main()

int main

(

void

)

Main function.

Returns

0 on exit

Definition at line 112 of file graph_coloring.cpp.

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

Definition at line 42 of file graph_coloring.cpp.

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