Chromatic number - Graph coloring

graphcoloring.js

class GraphNode {
  constructor(label) {
    this.label = label;
    this.neighbors = new Set();
    this.color = null;
  }
}

/**
 * Function to apply legal coloring to graph
 * @param {GraphNode} graph 
 * @param {Array} colors 
 * @returns {Number} chromatic number of the graph
 */
function colorGraph(graph, colors) {
  // array of set of nodes that can not have the color that corresponds to that index
  let colorRules = [];
  
  // loop through nodes
  for (const node of graph) {
    // throw error if it has a loop
    if (node.neighbors.has(node)) throw new Error('Graph is a loop thus invalid for legal coloring; loop at node ' + node.label);
    
    // check if it is legal to apply first color
    let colorIndex = 0;
    while (colorRules[colorIndex] && colorRules[colorIndex].has(node)) {
      // if it isn't move to the next color
      colorIndex++;
    }

    // use the first legal color found
    node.color = colors[colorIndex];

    // if that color hasn't been selected before, add new rule for it
    if (!colorRules[colorIndex]) colorRules[colorIndex] = node.neighbors;

    // add current node neighbors to the set of nodes that can not use that color
    else node.neighbors.forEach(n => colorRules[colorIndex].add(n));
  }

  return colorRules.length;
}