🔴 GraphColoringProblem-Optimization

Project Description:

The goal of this project is to implement and compare different optimization algorithms for solving the graph coloring problem. The problem consists of coloring the nodes of a graph such that no two adjacent nodes have the same color, while using the minimum number of colors possible.

🔸 The implemented algorithms include:

Greedy algorithm: A simple approach that assigns the first available color to each node, starting from the node with the most neighbors.

Tabu search: A metaheuristic algorithm that uses a tabu list to prevent the algorithm from getting stuck in local optima.

Simulated annealing: A probabilistic metaheuristic algorithm that simulates the process of annealing in materials science to escape local optima.

Genetic algorithm: A population-based algorithm that imitates the process of natural selection to find the optimal solution.

🔸 The project consists of the following steps:

1. Implement the graph coloring problem as a function that takes the adjacency matrix and adjacency list of a graph as input and returns the coloring of the nodes as a dictionary.
2. Implement the different optimization algorithms as functions that take the graph coloring problem as input and return the optimal coloring of the nodes.
3. Compare the results of the different algorithms by running them on a set of test graphs and measuring the number of colors used, the execution time, and the quality of the solutions.

The project will be implemented in Python and will make use of popular libraries such as numpy, pandas, matplotlib for data manipulation and visualization.

🔺 Requirements

Python 3.x

Numpy

Matplotlib (for visualizing the results)

🔺 Input

The input for the program will be an adjacency matrix and adjacency list of a graph.

🔺 Output

The output will be a dictionary containing the nodes as keys and their assigned colors as values.

🔺 Conclusion

The project will be useful for researchers and practitioners working in the field of graph theory and combinatorial optimization. It will provide a comprehensive comparison of different optimization algorithms for solving the graph coloring problem and can serve as a starting point for further research in this area.

🔺 Contributing

1. Fork it!
2. Create your feature branch: git checkout -b my-new-feature
3. Commit your changes: git commit -am 'Add some feature'
4. Push to the branch: git push origin my-new-feature
5. Submit a pull request :D

📮 For more information contact me: [email protected]