javanp-completesimulated-annealinggraph-coloring

Graph Coloring with using Simulated Annealing


I am trying to come up with the algorithm for a Graph Coloring problem using Simulated Annealing. There is the general algorithm online, but when i look at it, I couldn't understand how can apply this algorithm on this problem. Each node in graph must had diffrent color from it's neibours.

How can I use the Simulated annealing algorithm for this.
What is the "temperature", "schedule" in this problem?

Please help me understand this. Thanks


Solution

  • A proper coloring of a graph is an assignment of colors to the vertices of the graph so that no two adjacent vertices have the same color.
    To solve this problem assume you have a graph G with N nodes then you need these methods:

    Finally write a recursive method as simulatedAnnealing(graph, temp) which contains a main loop to change color for each node then check isColoringValid() if it would ok calculate loss function() and getProbability(). Because in higher temperature you can accept worth answer but in lower temperature, only better answer is accepted and at the end of method reduce the temperature and call simulatedAnnealing(graph, temp).

    You can find complete solution in my github.