Graph coloring
Here given code implementation process.
// C program
// Graph coloring
#include <stdio.h>
// Define size of adjacency matrix
#define N 6
// Sets the default color of each vertex in graph
void defult_color(int color[N])
{
for (int i = 0; i < N; ++i)
{
color[i] = 0;
}
}
// This function is assigning node color,
// And check adjacent node color are valid or not
int fill_color(int graph[N][N], int color[N], int max_color, int node_color, int node)
{
if (node_color > max_color)
{
return 0;
}
if (node == N)
{
//When color are vaild
return 1;
}
if (color[node] == 0)
{
//When need to set color
int status = 1;
//Check neighbors
for (int i = 0; i < N && status == 1; ++i)
{
if (graph[node][i] == 1 && color[i] == node_color)
{
// When need to change color
if (fill_color(graph, color, max_color, node_color + 1, node))
{
return 1;
}
else
{
status = 0;
}
}
}
if (status == 1)
{
//When color is valid to node
color[node] = node_color;
//Visit to next node
if (fill_color(graph, color, max_color, 1, node + 1))
{
return 1;
}
//reset node color
color[node] = 0;
}
}
return 0;
}
// Handles the request of find given graph node color
void graph_color(int graph[N][N], int max_color)
{
if (max_color <= 0)
{
return;
}
// This are used to store vertex color
int color[N];
defult_color(color);
if (fill_color(graph, color, max_color, 1, 0))
{
//When given color are suitable
printf("\n Graph Color");
for (int i = 0; i < N; ++i)
{
//Display node color
printf("\n Node [%d]->color [%d]", i, color[i]);
}
}
else
{
//In case if, given color are not suitable to fill all adjacent vertices.
// (violation of color) Then
printf("\n Given colors [%d] are not enough\n", max_color);
}
}
int main()
{
//Define node relation in adjacency matrix
int graph[N][N] = {
{
0 , 1 , 0 , 1 , 0 , 1
} ,
{
1 , 0 , 1 , 0 , 1 , 0
} ,
{
0 , 1 , 0 , 1 , 1 , 1
} ,
{
1 , 0 , 1 , 0 , 1 , 0
} ,
{
0 , 1 , 1 , 1 , 0 , 1
} ,
{
1 , 0 , 1 , 0 , 1 , 0
} , };
//Define number of possible color
int max_color = 3;
graph_color(graph, max_color);
return 0;
}
Output
Graph Color
Node [0]->color [1]
Node [1]->color [2]
Node [2]->color [1]
Node [3]->color [2]
Node [4]->color [3]
Node [5]->color [2]
/*
Java program
Graph coloring
*/
class MyGraph
{
// Sets the default color of each vertex in graph
public void defult_color(int[] color,int size)
{
for (int i = 0; i < size; ++i)
{
color[i] = 0;
}
}
// This function is assigning node color,
// And check adjacent node color are valid or not
public boolean fill_color(int [][]graph, int[] color, int max_color, int node_color, int node,int size)
{
if (node_color > max_color)
{
return false;
}
if (node == size)
{
//When color are vaild
return true;
}
if (color[node] == 0)
{
//When need to set color
boolean status = true;
//Check neighbors
for (int i = 0; i < size && status == true; ++i)
{
if (graph[node][i] == 1 && color[i] == node_color)
{
// When need to change color
if (fill_color(graph, color, max_color, node_color + 1, node, size))
{
return true;
}
else
{
status = false;
}
}
}
if (status == true)
{
//When color is valid to node
color[node] = node_color;
//Visit to next node
if (fill_color(graph, color, max_color, 1, node + 1,size))
{
return true;
}
//reset node color
color[node] = 0;
}
}
return false;
}
// Handles the request of find given graph node color
public void graph_color(int[][] graph, int max_color,int size)
{
if (max_color <= 0)
{
return;
}
// This are used to store vertex color
int[] color = new int[size];
defult_color(color,size);
if (fill_color(graph, color, max_color, 1, 0,size))
{
//When given color are suitable
System.out.print("\n Graph Color");
for (int i = 0; i < size; ++i)
{
//Display node color
System.out.print("\n Node [" + i + "]->color [" + color[i] + "]");
}
}
else
{
//In case if, given color are not suitable to fill all adjacent vertices.
// (violation of color) Then
System.out.print("\n Given colors [" + max_color + "] are not enough\n");
}
}
public static void main(String[] args)
{
MyGraph obj = new MyGraph();
//Define node relation in adjacency matrix
int [][] graph =
{
{
0 , 1 , 0 , 1 , 0 , 1
} ,
{
1 , 0 , 1 , 0 , 1 , 0
} ,
{
0 , 1 , 0 , 1 , 1 , 1
} ,
{
1 , 0 , 1 , 0 , 1 , 0
} ,
{
0 , 1 , 1 , 1 , 0 , 1
} ,
{
1 , 0 , 1 , 0 , 1 , 0
} ,
};
// Get size of adjacency matrix
int size = graph.length;
//Define number of possible color
int max_color = 3;
//Test
obj.graph_color(graph, max_color,size);
}
}
Output
Graph Color
Node [0]->color [1]
Node [1]->color [2]
Node [2]->color [1]
Node [3]->color [2]
Node [4]->color [3]
Node [5]->color [2]
//Include header file
#include <iostream>
#define N 6
using namespace std;
/*
C++ program
Graph coloring
*/
class MyGraph
{
public:
// Sets the default color of each vertex in graph
void defult_color(int color[], int size)
{
for (int i = 0; i < size; ++i)
{
color[i] = 0;
}
}
// This function is assigning node color,
// And check adjacent node color are valid or not
bool fill_color(int graph[N][N], int color[], int max_color, int node_color, int node, int size)
{
if (node_color > max_color)
{
return false;
}
if (node == size)
{
//When color are vaild
return true;
}
if (color[node] == 0)
{
//When need to set color
bool status = true;
//Check neighbors
for (int i = 0; i < size && status == true; ++i)
{
if (graph[node][i] == 1 && color[i] == node_color)
{
// When need to change color
if (this->fill_color(graph, color, max_color, node_color + 1, node, size))
{
return true;
}
else
{
status = false;
}
}
}
if (status == true)
{
//When color is valid to node
color[node] = node_color;
//Visit to next node
if (this->fill_color(graph, color, max_color, 1, node + 1, size))
{
return true;
}
//reset node color
color[node] = 0;
}
}
return false;
}
// Handles the request of find given graph node color
void graph_color(int graph[N][N], int max_color, int size)
{
if (max_color <= 0)
{
return;
}
// This are used to store vertex color
int color[size];
this->defult_color(color, size);
if (this->fill_color(graph, color, max_color, 1, 0, size))
{
//When given color are suitable
cout << "\n Graph Color";
for (int i = 0; i < size; ++i)
{
//Display node color
cout << "\n Node [" << i << "] -> color [" << color[i] << "]";
}
}
else
{
//In case if, given color are not suitable to fill all adjacent vertices.
// (violation of color) Then
cout << "\n Given colors [" << max_color << "] are not enough\n";
}
}
};
int main()
{
MyGraph obj = MyGraph();
//Define node relation in adjacency matrix
int graph[N][N] = {
{
0 , 1 , 0 , 1 , 0 , 1
} , {
1 , 0 , 1 , 0 , 1 , 0
} , {
0 , 1 , 0 , 1 , 1 , 1
} , {
1 , 0 , 1 , 0 , 1 , 0
} , {
0 , 1 , 1 , 1 , 0 , 1
} , {
1 , 0 , 1 , 0 , 1 , 0
} };
// Get size of adjacency matrix
int size = N;
//Define number of possible color
int max_color = 3;
//Test
obj.graph_color(graph, max_color, size);
return 0;
}
Output
Graph Color
Node [0] -> color [1]
Node [1] -> color [2]
Node [2] -> color [1]
Node [3] -> color [2]
Node [4] -> color [3]
Node [5] -> color [2]
//Include namespace system
using System;
/*
C# program
Graph coloring
*/
class MyGraph
{
// Sets the default color of each vertex in graph
public void defult_color(int[] color, int size)
{
for (int i = 0; i < size; ++i)
{
color[i] = 0;
}
}
// This function is assigning node color,
// And check adjacent node color are valid or not
public Boolean fill_color(int[,] graph, int[] color, int max_color, int node_color, int node, int size)
{
if (node_color > max_color)
{
return false;
}
if (node == size)
{
//When color are vaild
return true;
}
if (color[node] == 0)
{
//When need to set color
Boolean status = true;
//Check neighbors
for (int i = 0; i < size && status == true; ++i)
{
if (graph[node,i] == 1 && color[i] == node_color)
{
// When need to change color
if (fill_color(graph, color, max_color, node_color + 1, node, size))
{
return true;
}
else
{
status = false;
}
}
}
if (status == true)
{
//When color is valid to node
color[node] = node_color;
//Visit to next node
if (fill_color(graph, color, max_color, 1, node + 1, size))
{
return true;
}
//reset node color
color[node] = 0;
}
}
return false;
}
// Handles the request of find given graph node color
public void graph_color(int[,] graph, int max_color, int size)
{
if (max_color <= 0)
{
return;
}
// This are used to store vertex color
int[] color = new int[size];
defult_color(color, size);
if (fill_color(graph, color, max_color, 1, 0, size))
{
//When given color are suitable
Console.Write("\n Graph Color");
for (int i = 0; i < size; ++i)
{
//Display node color
Console.Write("\n Node [" + i + "] -> color [" + color[i] + "]");
}
}
else
{
//In case if, given color are not suitable to fill all adjacent vertices.
// (violation of color) Then
Console.Write("\n Given colors [" + max_color + "] are not enough\n");
}
}
public static void Main(String[] args)
{
MyGraph obj = new MyGraph();
//Define node relation in adjacency matrix
int[,] graph = {
{
0 , 1 , 0 , 1 , 0 , 1
} , {
1 , 0 , 1 , 0 , 1 , 0
} , {
0 , 1 , 0 , 1 , 1 , 1
} , {
1 , 0 , 1 , 0 , 1 , 0
} , {
0 , 1 , 1 , 1 , 0 , 1
} , {
1 , 0 , 1 , 0 , 1 , 0
}
};
// Get size of adjacency matrix
int size = graph.GetLength(0);
//Define number of possible color
int max_color = 3;
//Test
obj.graph_color(graph, max_color, size);
}
}
Output
Graph Color
Node [0] -> color [1]
Node [1] -> color [2]
Node [2] -> color [1]
Node [3] -> color [2]
Node [4] -> color [3]
Node [5] -> color [2]
<?php
/*
Php program
Graph coloring
*/
class MyGraph
{
// This function is assigning node color,
// And check adjacent node color are valid or not
public function fill_color( & $graph, & $color, $max_color, $node_color, $node, $size)
{
if ($node_color > $max_color)
{
return false;
}
if ($node == $size)
{
//When color are vaild
return true;
}
if ($color[$node] == 0)
{
//When need to set color
$status = true;
//Check neighbors
for ($i = 0; $i < $size && $status == true; ++$i)
{
if ($graph[$node][$i] == 1 && $color[$i] == $node_color)
{
// When need to change color
if ($this->fill_color($graph, $color, $max_color, $node_color + 1, $node, $size))
{
return true;
}
else
{
$status = false;
}
}
}
if ($status == true)
{
//When color is valid to node
$color[$node] = $node_color;
//Visit to next node
if ($this->fill_color($graph, $color, $max_color, 1, $node + 1, $size))
{
return true;
}
//reset node color
$color[$node] = 0;
}
}
return false;
}
// Handles the request of find given graph node color
public function graph_color( & $graph, $max_color, $size)
{
if ($max_color <= 0)
{
return;
}
// This are used to store vertex color
$color = array_fill(0, $size, 0);
if ($this->fill_color($graph, $color, $max_color, 1, 0, $size))
{
//When given color are suitable
echo "\n Graph Color";
for ($i = 0; $i < $size; ++$i)
{
//Display node color
echo "\n Node [". $i ."] -> color [". $color[$i] ."]";
}
}
else
{
//In case if, given color are not suitable to fill all adjacent vertices.
// (violation of color) Then
echo "\n Given colors [". $max_color ."] are not enough\n";
}
}
}
function main()
{
$obj = new MyGraph();
//Define node relation in adjacency matrix
$graph = array(array(0, 1, 0, 1, 0, 1), array(1, 0, 1, 0, 1, 0), array(0, 1, 0, 1, 1, 1), array(1, 0, 1, 0, 1, 0), array(0, 1, 1, 1, 0, 1), array(1, 0, 1, 0, 1, 0));
// Get size of adjacency matrix
$size = count($graph);
//Define number of possible color
$max_color = 3;
//Test
$obj->graph_color($graph, $max_color, $size);
}
main();
Output
Graph Color
Node [0] -> color [1]
Node [1] -> color [2]
Node [2] -> color [1]
Node [3] -> color [2]
Node [4] -> color [3]
Node [5] -> color [2]
/*
Node Js program
Graph coloring
*/
class MyGraph
{
// This function is assigning node color,
// And check adjacent node color are valid or not
fill_color(graph, color, max_color, node_color, node, size)
{
if (node_color > max_color)
{
return false;
}
if (node == size)
{
//When color are vaild
return true;
}
if (color[node] == 0)
{
//When need to set color
var status = true;
//Check neighbors
for (var i = 0; i < size && status == true; ++i)
{
if (graph[node][i] == 1 && color[i] == node_color)
{
// When need to change color
if (this.fill_color(graph, color, max_color, node_color + 1, node, size))
{
return true;
}
else
{
status = false;
}
}
}
if (status == true)
{
//When color is valid to node
color[node] = node_color;
//Visit to next node
if (this.fill_color(graph, color, max_color, 1, node + 1, size))
{
return true;
}
//reset node color
color[node] = 0;
}
}
return false;
}
// Handles the request of find given graph node color
graph_color(graph, max_color, size)
{
if (max_color <= 0)
{
return;
}
// This are used to store vertex color
var color = Array(size).fill(0);
if (this.fill_color(graph, color, max_color, 1, 0, size))
{
//When given color are suitable
process.stdout.write("\n Graph Color");
for (var i = 0; i < size; ++i)
{
//Display node color
process.stdout.write("\n Node [" + i + "] -> color [" + color[i] + "]");
}
}
else
{
//In case if, given color are not suitable to fill all adjacent vertices.
// (violation of color) Then
process.stdout.write("\n Given colors [" + max_color + "] are not enough\n");
}
}
}
function main()
{
var obj = new MyGraph();
//Define node relation in adjacency matrix
var graph = [
[0, 1, 0, 1, 0, 1],
[1, 0, 1, 0, 1, 0],
[0, 1, 0, 1, 1, 1],
[1, 0, 1, 0, 1, 0],
[0, 1, 1, 1, 0, 1],
[1, 0, 1, 0, 1, 0]
];
// Get size of adjacency matrix
var size = graph.length;
//Define number of possible color
var max_color = 3;
//Test
obj.graph_color(graph, max_color, size);
}
main();
Output
Graph Color
Node [0] -> color [1]
Node [1] -> color [2]
Node [2] -> color [1]
Node [3] -> color [2]
Node [4] -> color [3]
Node [5] -> color [2]
# Python 3 program
# Graph coloring
class MyGraph :
# This function is assigning node color,
# And check adjacent node color are valid or not
def fill_color(self, graph, color, max_color, node_color, node, size) :
if (node_color > max_color) :
return False
if (node == size) :
# When color are vaild
return True
if (color[node] == 0) :
# When need to set color
status = True
# Check neighbors
i = 0
while (i < size and status == True) :
if (graph[node][i] == 1 and color[i] == node_color) :
# When need to change color
if (self.fill_color(graph, color, max_color, node_color + 1, node, size)) :
return True
else :
status = False
i += 1
if (status == True) :
# When color is valid to node
color[node] = node_color
# Visit to next node
if (self.fill_color(graph, color, max_color, 1, node + 1, size)) :
return True
# reset node color
color[node] = 0
return False
# Handles the request of find given graph node color
def graph_color(self, graph, max_color, size) :
if (max_color <= 0) :
return
# This are used to store vertex color
color = [0] * (size)
if (self.fill_color(graph, color, max_color, 1, 0, size)) :
# When given color are suitable
print("\n Graph Color", end = "")
i = 0
while (i < size) :
# Display node color
print("\n Node [", i ,"] -> color [", color[i] ,"]", end = "")
i += 1
else :
# In case if, given color are not suitable to fill all adjacent vertices.
# (violation of color) Then
print("\n Given colors [", max_color ,"] are not enough\n", end = "")
def main() :
obj = MyGraph()
# Define node relation in adjacency matrix
graph = [
[0, 1, 0, 1, 0, 1],
[1, 0, 1, 0, 1, 0],
[0, 1, 0, 1, 1, 1],
[1, 0, 1, 0, 1, 0],
[0, 1, 1, 1, 0, 1],
[1, 0, 1, 0, 1, 0]
]
# Get size of adjacency matrix
size = len(graph)
# Define number of possible color
max_color = 3
# Test
obj.graph_color(graph, max_color, size)
if __name__ == "__main__": main()
Output
Graph Color
Node [ 0 ] -> color [ 1 ]
Node [ 1 ] -> color [ 2 ]
Node [ 2 ] -> color [ 1 ]
Node [ 3 ] -> color [ 2 ]
Node [ 4 ] -> color [ 3 ]
Node [ 5 ] -> color [ 2 ]
# Ruby program
# Graph coloring
class MyGraph
# This function is assigning node color,
# And check adjacent node color are valid or not
def fill_color(graph, color, max_color, node_color, node, size)
if (node_color > max_color)
return false
end
if (node == size)
# When color are vaild
return true
end
if (color[node] == 0)
# When need to set color
status = true
# Check neighbors
i = 0
while (i < size && status == true)
if (graph[node][i] == 1 && color[i] == node_color)
# When need to change color
if (self.fill_color(graph, color, max_color, node_color + 1, node, size))
return true
else
status = false
end
end
i += 1
end
if (status == true)
# When color is valid to node
color[node] = node_color
# Visit to next node
if (self.fill_color(graph, color, max_color, 1, node + 1, size))
return true
end
# reset node color
color[node] = 0
end
end
return false
end
# Handles the request of find given graph node color
def graph_color(graph, max_color, size)
if (max_color <= 0)
return
end
# This are used to store vertex color
color = Array.new(size) {0}
if (self.fill_color(graph, color, max_color, 1, 0, size))
# When given color are suitable
print("\n Graph Color")
i = 0
while (i < size)
# Display node color
print("\n Node [", i ,"] -> color [", color[i] ,"]")
i += 1
end
else
# In case if, given color are not suitable to fill all adjacent vertices.
# (violation of color) Then
print("\n Given colors [", max_color ,"] are not enough\n")
end
end
end
def main()
obj = MyGraph.new()
# Define node relation in adjacency matrix
graph = [
[0, 1, 0, 1, 0, 1],
[1, 0, 1, 0, 1, 0],
[0, 1, 0, 1, 1, 1],
[1, 0, 1, 0, 1, 0],
[0, 1, 1, 1, 0, 1],
[1, 0, 1, 0, 1, 0]
]
# Get size of adjacency matrix
size = graph.length
# Define number of possible color
max_color = 3
# Test
obj.graph_color(graph, max_color, size)
end
main()
Output
Graph Color
Node [0] -> color [1]
Node [1] -> color [2]
Node [2] -> color [1]
Node [3] -> color [2]
Node [4] -> color [3]
Node [5] -> color [2]
/*
Scala program
Graph coloring
*/
class MyGraph
{
// This function is assigning node color,
// And check adjacent node color are valid or not
def fill_color(graph: Array[Array[Int]], color: Array[Int], max_color: Int, node_color: Int, node: Int, size: Int): Boolean = {
if (node_color > max_color)
{
return false;
}
if (node == size)
{
//When color are vaild
return true;
}
if (color(node) == 0)
{
//When need to set color
var status: Boolean = true;
//Check neighbors
var i: Int = 0;
while (i < size && status == true)
{
if (graph(node)(i) == 1 && color(i) == node_color)
{
// When need to change color
if (fill_color(graph, color, max_color, node_color + 1, node, size))
{
return true;
}
else
{
status = false;
}
}
i += 1;
}
if (status == true)
{
//When color is valid to node
color(node) = node_color;
//Visit to next node
if (fill_color(graph, color, max_color, 1, node + 1, size))
{
return true;
}
//reset node color
color(node) = 0;
}
}
return false;
}
// Handles the request of find given graph node color
def graph_color(graph: Array[Array[Int]], max_color: Int, size: Int): Unit = {
if (max_color <= 0)
{
return;
}
// This are used to store vertex color
var color: Array[Int] = Array.fill[Int](size)(0);
if (fill_color(graph, color, max_color, 1, 0, size))
{
//When given color are suitable
print("\n Graph Color");
var i: Int = 0;
while (i < size)
{
//Display node color
print("\n Node [" + i + "] -> color [" + color(i) + "]");
i += 1;
}
}
else
{
//In case if, given color are not suitable to fill all adjacent vertices.
// (violation of color) Then
print("\n Given colors [" + max_color + "] are not enough\n");
}
}
}
object Main
{
def main(args: Array[String]): Unit = {
var obj: MyGraph = new MyGraph();
//Define node relation in adjacency matrix
var graph: Array[Array[Int]] = Array(Array(0, 1, 0, 1, 0, 1), Array(1, 0, 1, 0, 1, 0), Array(0, 1, 0, 1, 1, 1), Array(1, 0, 1, 0, 1, 0), Array(0, 1, 1, 1, 0, 1), Array(1, 0, 1, 0, 1, 0));
// Get size of adjacency matrix
var size: Int = graph.length;
//Define number of possible color
var max_color: Int = 3;
//Test
obj.graph_color(graph, max_color, size);
}
}
Output
Graph Color
Node [0] -> color [1]
Node [1] -> color [2]
Node [2] -> color [1]
Node [3] -> color [2]
Node [4] -> color [3]
Node [5] -> color [2]
/*
Swift 4 program
Graph coloring
*/
class MyGraph
{
// This function is assigning node color,
// And check adjacent node color are valid or not
func fill_color(_ graph: [[Int]],
_ color: inout[Int],
_ max_color: Int,
_ node_color: Int,
_ node: Int,
_ size: Int) -> Bool
{
if (node_color > max_color)
{
return false;
}
if (node == size)
{
//When color are vaild
return true;
}
if (color[node] == 0)
{
//When need to set color
var status: Bool = true;
//Check neighbors
var i: Int = 0;
while (i < size && status == true)
{
if (graph[node][i] == 1 && color[i] == node_color)
{
// When need to change color
if (self.fill_color(graph, &color, max_color, node_color + 1, node, size))
{
return true;
}
else
{
status = false;
}
}
i += 1;
}
if (status == true)
{
//When color is valid to node
color[node] = node_color;
//Visit to next node
if (self.fill_color(graph, &color, max_color, 1, node + 1, size))
{
return true;
}
//reset node color
color[node] = 0;
}
}
return false;
}
// Handles the request of find given graph node color
func graph_color(_ graph: [[Int]], _ max_color: Int, _ size: Int)
{
if (max_color <= 0)
{
return;
}
// This are used to store vertex color
var color: [Int] = Array(repeating: 0, count: size);
if (self.fill_color(graph, &color, max_color, 1, 0, size))
{
//When given color are suitable
print("\n Graph Color", terminator: "");
var i: Int = 0;
while (i < size)
{
//Display node color
print("\n Node [", i ,"] -> color [", color[i],"]", terminator: "");
i += 1;
}
}
else
{
//In case if, given color are not suitable to fill all adjacent vertices.
// (violation of color) Then
print("\n Given colors [", max_color ,"]are not enough\n", terminator: "");
}
}
}
func main()
{
let obj: MyGraph = MyGraph();
//Define node relation in adjacency matrix
let graph: [[Int]] = [[0, 1, 0, 1, 0, 1],
[1, 0, 1, 0, 1, 0],
[0, 1, 0, 1, 1, 1],
[1, 0, 1, 0, 1, 0],
[0, 1, 1, 1, 0, 1],
[1, 0, 1, 0, 1, 0]];
// Get size of adjacency matrix
let size: Int = graph.count;
//Define number of possible color
let max_color: Int = 3;
//Test
obj.graph_color(graph, max_color, size);
}
main();
Output
Graph Color
Node [ 0 ] -> color [ 1 ]
Node [ 1 ] -> color [ 2 ]
Node [ 2 ] -> color [ 1 ]
Node [ 3 ] -> color [ 2 ]
Node [ 4 ] -> color [ 3 ]
Node [ 5 ] -> color [ 2 ]
Please share your knowledge to improve code and content standard. Also submit your doubts, and test case. We improve by your feedback. We will try to resolve your query as soon as possible.
New Comment