Skip to main content

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 ]
Last updated on by Kalkicode




Comment

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