Graph Coloring Problem

Problem description

Given an undirected graph and a number of colors, determines if the graph can be colored with at most m colors. No two adjacent vertices of the graph can be colored with the same color.

Input

Adjacency matrix:
0 1 1 1
1 0 1 1
1 1 0 1
1 1 1 0

Output for number of colors = 4:

Solution exists and here are the assigned colours:
Vertex(number:0, color:1)
Vertex(number:1, color:2)
Vertex(number:2, color:3)
Vertex(number:3, color:4)
Congratulations!

Output for number of colors = 3:

It is not possible to colour given graph in this number of colours.

Algorithm using backtracking:

1. Read matrix from file and convert it to the ditionary of vertices.
2. Pass to the recursive function number of colors and number of vertex (number of vertex = 0 at the beginning), then check every vertex which colour it is safe to give by the is_safe function.
3. Return results with the colors assigned to every Vertex if possible. If graph cannot be coloured in given number of colors, return the message.

Relization:

read_file function - Reads matrix from file and converts it into graph.

class Graph:

Methods:

init - Initializes class.
is_safe - Checks if it is ok to set the given colour to the given vertex.
graph_color_recursive - Recursive function to colorize the graph by backtracking.
graph_color_final - Shows result of the colonizing.

class Vertex:

Methods:

init - Initializes class.
hash - Supports hashing.
str - Returns information about vertex in string.