DEV Community

Write better code: Day 8 - Graph Coloring

Arjun Rajkumar on December 12, 2018

This post originally appeared on Arjun Rajkumar's blog. Arjun is a web developer based in Bangalore, India. -- Day 8: Question 1 Give...
Read full post
Collapse
 
arjunrajkumar profile image
Arjun Rajkumar •

Logic:

  • Each node in the graph has maximum D neighbours.
  • Given than there are maximum D+1 colours, we can assume that for each node there is atleast one color that is not used.
  • So, go thru each node and get the colors of all its neighbours.
  • Check to see which color is not included in this neighbouring color group, and assign the color to it. 
def colour_graoh(colors, graph)
  graph.nodes.each do |node|

    all_neighbouring_colors = []

    node.neighbours.each do |neighbour|
      all_neighbouring_colors << neighbour.color if !all_neighbouring_colors.include?(neighbour.color)
    end

    colors.each do |color|
      node.color = color if !all_neighbouring_colors.include?(color)
      break
    end
end