Algorithms_in_C++ 1.0.0
Set of algorithms implemented in C++.
|
prints the assigned colors using Graph Coloring algorithm More...
#include <array>
#include <iostream>
#include <vector>
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. | |
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.
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.
V | number of vertices in the graph |
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 |
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.
V | number of vertices in the graph |
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 |
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 int main | ( | void | ) |
Main function.
void backtracking::graph_coloring::printSolution | ( | const std::array< int, V > & | color | ) |
A utility function to print the solution.
V | number of vertices in the graph |
color | array of colors assigned to the nodes |