Status: Developing
⚠️
The Minimum Graph Coloring is a well-known NP-Hard combinatorial optimization problem that consists on assigning the least number of different colors to the vertices of a graph such that every two adjacent vertices are colored with distinct colors.
This project aims to find the chromatic number of an undirected graph.
Three heuristic algorithms were implemented, one based on Simulated Annealing metaheuristic, along with two exact algorithms.
The DIMACS graphs are used as instance files. Available here and here.
You should have Java JDK 11 installed on your computer.
You should open the command line and and then open the directory on which you extracted the project.
Being on NP-Hard directory, you should execute the following code on the command line:
- cd src
- cd Classes
- javac *.java
Access the directory src through the command line and then type java Classes.Application and execute it.
As soon as you run the program, you'll be asked to type the name of aa instance file to compute its chromatic number.
You should write the file name along with ".txt" at the end.
Example: david.txt
You'll also be asked whether you'd like or not to run the Brute Force and Backtracking exact algorithms.
For those you'd like to run, it is enough to type "yes".
Before running the heuristic based on Simulated Annealing, you'll be asked to set the initial temperature (T_0), the iterations per temperature (L) and the cooling rate (alpha).
Features to be added and corrected in the future:
- Change the random neigr method of Simulated Annealing as it has not improved the solution quality.
MIT licensed.