m-Coloring Problem
Introduction
m-Coloring is a problem which is basically in order to determine/show that if we manage to color a graph with at most m colors such that no two adjacent vertices of the given graph are colored with the same color.
There are three common ways to solve that kind of problem. These,
1. Naive Appoach
Can be thought as a brute-force way. It is based on the idea that “on worst case scenario it will take m^n tries with m colors and n vertices given”. Thus the time complexity is O(m^n) and space complexity is O(n).
2. Backtracking
The main purpose of this algorithm is to reach the goal with learning from repetition and it’s own mistakes. As the name suggests, the algorithm takes a step back to find a solution. At first the algorithm starts with a possible move and then keeps going with another. If it does not satisfy, algorithm goes back and tries another one, until it either finds a solution or appears that there is no solution. Thus the time complexity is O(m^n) and space complexity is O(n). The upperbound time complexity (worst-case scenario) is same with brute-force navive approach since there is a total combination of vertex colors is same as m^n. On the other hand, the average complexity is lower relatively.
3. BFS:
The appoarch with BFS is based on the idea that coloring each node from 1 to n travelling with BFS. The algorithm checks all edges of the given node and if the color of the neighbors are same, corrects it and goes on. Time complexity is linear and the space complexity is O(V) since it stores the visited nodes.
Dependencies
In order to run the functions, you need to install the following modules into your virtual environment
▪ pandas (current latest version: 1.1.4)
▪ plotly (current latest version: 4.13.0)
Constraint Satisfaction Problems (CSPs)
Task: Color each region
Variables: X = {Argentina, Bolivia, Brazil, Chile, Colombia, Ecuador, Falkland Islands, Guyana, Paraguay, Peru, Suriname, Uruguay, Venezuela}
Domains: Di = {blue, red, green, yellow}
Constraints: adjacent regions must have different color
Data
Solution
Solution can be handled with 3 functions basically. At first we declare a list to use later just to reach countries when iterating.
k_list = list(adj)color_w_backtracking(k: integer)
Aim
The function is in order to create the result dictionary by checking neighbors’ colors for each counrty.
Extra
This part of the code can also be handled with another “for loop”. However, for the sake of simplicity, it is handled with iterating manually with the constant “k” by calling the function with parameter = 0.
check_safe(curr_country: String, curr_color: String)
Aim
The fuction is in order to check if a color is allowed (still available) to assign to a country.
plot_choropleth(colormap: dictionary)
Aim
The function is in order to visualize the map by result dictionary.
Logic
To understand the algorithm better, print(information_about_that_step) is used at important breakpoints.
Result
Full Code
https://github.com/asrinoztin/m-coloring
