Graph coloring

graph-coloring.js

/*
https://www.interviewcake.com/question/javascript/graph-coloring

Given an undirected graph with maximum degree D, find a graph coloring using at most D+1 colors.

Our solution runs in O(N+M)O(N+M) time but takes O(D)O(D) space. Can we get down to O(1)O(1) space?
*/
function GraphNode(label) {
  this.label = label;
  this.neighbors = new Set();
  this.color = null;
}

function getRandomColor(colorsCount, exclusionsVector = 0) {
    const exclusions = exclusionsVector.toNumber(2).split('');

    for (let i=colorsCount-1; i--; i >= 0) {
        if (exclusions[i] === '0') {
            return colorsCount - 1 - i;
        }
    }

    return undefined;
}

function colorGraph(graph, allColors) {
  
  // Determine D
  const d = Math.max(...graph.map(node => node.neighbors.size));
  
  graph.forEach(node => {
    if (!node.color) {
      node.color = getRandomColor(d+1);
    }
    const neighborExcludedColors = 1 << node.color;
    node.neighbors.forEach(neighbor => {
      if (!neighbor.color || neighbor.color === node.color) {
        neighbor.color = getRandomColor(colors, neighborExcludedColors);
      }
      if (neighbor.color) {
        neighborExcludedColors |= 1 << neighbor.color;
      }
      else {
        throw new Error('impossible to color graph');
      }
    });
  });

  graph.forEach(node => node.color = allColors[node.color]);
}

const CSS_COLOR_NAMES = ["AliceBlue","AntiqueWhite","Aqua","Aquamarine","Azure","Beige","Bisque","Black","BlanchedAlmond","Blue","BlueViolet","Brown","BurlyWood","CadetBlue","Chartreuse","Chocolate","Coral","CornflowerBlue","Cornsilk","Crimson","Cyan","DarkBlue","DarkCyan","DarkGoldenRod","DarkGray","DarkGrey","DarkGreen","DarkKhaki","DarkMagenta","DarkOliveGreen","Darkorange","DarkOrchid","DarkRed","DarkSalmon","DarkSeaGreen","DarkSlateBlue","DarkSlateGray","DarkSlateGrey","DarkTurquoise","DarkViolet","DeepPink","DeepSkyBlue","DimGray","DimGrey","DodgerBlue","FireBrick","FloralWhite","ForestGreen","Fuchsia","Gainsboro","GhostWhite","Gold","GoldenRod","Gray","Grey","Green","GreenYellow","HoneyDew","HotPink","IndianRed","Indigo","Ivory","Khaki","Lavender","LavenderBlush","LawnGreen","LemonChiffon","LightBlue","LightCoral","LightCyan","LightGoldenRodYellow","LightGray","LightGrey","LightGreen","LightPink","LightSalmon","LightSeaGreen","LightSkyBlue","LightSlateGray","LightSlateGrey","LightSteelBlue","LightYellow","Lime","LimeGreen","Linen","Magenta","Maroon","MediumAquaMarine","MediumBlue","MediumOrchid","MediumPurple","MediumSeaGreen","MediumSlateBlue","MediumSpringGreen","MediumTurquoise","MediumVioletRed","MidnightBlue","MintCream","MistyRose","Moccasin","NavajoWhite","Navy","OldLace","Olive","OliveDrab","Orange","OrangeRed","Orchid","PaleGoldenRod","PaleGreen","PaleTurquoise","PaleVioletRed","PapayaWhip","PeachPuff","Peru","Pink","Plum","PowderBlue","Purple","Red","RosyBrown","RoyalBlue","SaddleBrown","Salmon","SandyBrown","SeaGreen","SeaShell","Sienna","Silver","SkyBlue","SlateBlue","SlateGray","SlateGrey","Snow","SpringGreen","SteelBlue","Tan","Teal","Thistle","Tomato","Turquoise","Violet","Wheat","White","WhiteSmoke","Yellow","YellowGreen"];

(function firstTest() {
  var a = new GraphNode("a");
  var b = new GraphNode("b");
  var c = new GraphNode("c");
  
  a.neighbors.add(b);
  b.neighbors.add(a);
  c.neighbors.add(b);
  b.neighbors.add(c);
  
  var graph = [a, b, c];
  
  colorGraph(graph, CSS_COLOR_NAMES);
  
  console.log(graph);
})();


(function lineGraphTest() {
    const nodeA = new GraphNode("A"); 
    const nodeB = new GraphNode("B"); 
    const nodeC = new GraphNode("C"); 
    const nodeD = new GraphNode("D");
    nodeA.neighbors.add(nodeB);
    nodeB.neighbors.add(nodeA);
    nodeB.neighbors.add(nodeC);
    nodeC.neighbors.add(nodeB);
    nodeC.neighbors.add(nodeD);
    nodeD.neighbors.add(nodeC);
    const graph = [nodeA, nodeB, nodeC, nodeD];
    colorGraph(graph, CSS_COLOR_NAMES);  
    console.log(graph);      
})();


    
(function separateGraphTest() {
        const nodeA = new GraphNode("A"); 
        const nodeB = new GraphNode("B"); 
        const nodeC = new GraphNode("C"); 
        const nodeD = new GraphNode("D");
        nodeA.neighbors.add(nodeB);
        nodeB.neighbors.add(nodeA);
        nodeC.neighbors.add(nodeD);
        nodeD.neighbors.add(nodeC);
        const graph = [nodeA, nodeB, nodeC, nodeD];
        colorGraph(graph, CSS_COLOR_NAMES);
        console.log(graph);
})();



(function triangleGraphTest() {
        const nodeA = new GraphNode("A"); 
        const nodeB = new GraphNode("B"); 
        const nodeC = new GraphNode("C"); 
        nodeA.neighbors.add(nodeB);
        nodeA.neighbors.add(nodeC);
        nodeB.neighbors.add(nodeA);
        nodeB.neighbors.add(nodeC);
        nodeC.neighbors.add(nodeA);
        nodeC.neighbors.add(nodeB);
        const graph = [nodeA, nodeB, nodeC];
        colorGraph(graph, CSS_COLOR_NAMES);
        console.log(graph);
})();

(function envelopeGraphTest() {
        const nodeA = new GraphNode("A"); 
        const nodeB = new GraphNode("B"); 
        const nodeC = new GraphNode("C"); 
        const nodeD = new GraphNode("D");
        const nodeE = new GraphNode("E");
        nodeA.neighbors.add(nodeB);
        nodeA.neighbors.add(nodeC);
        nodeB.neighbors.add(nodeA);
        nodeB.neighbors.add(nodeC);
        nodeB.neighbors.add(nodeD);
        nodeB.neighbors.add(nodeE);
        nodeC.neighbors.add(nodeA);
        nodeC.neighbors.add(nodeB);
        nodeC.neighbors.add(nodeD);
        nodeC.neighbors.add(nodeE);
        nodeD.neighbors.add(nodeB);
        nodeD.neighbors.add(nodeC);
        nodeD.neighbors.add(nodeE);
        nodeE.neighbors.add(nodeB);
        nodeE.neighbors.add(nodeC);
        nodeE.neighbors.add(nodeD);
        const graph = [nodeA, nodeB, nodeC, nodeD, nodeE];
        colorGraph(graph, CSS_COLOR_NAMES);
        console.log(graph);
})();



(function loopGraphTest() {
        const nodeA = new GraphNode("A"); 
        nodeA.neighbors.add(nodeA);
        const graph = [nodeA];
        colorGraph(graph, CSS_COLOR_NAMES);
        console.log(graph);
})();
    
   

@themindfuldev can you still remember some of the code details?

In the meantime the line 15, const exclusions = exclusionsVector.toNumber(2).split(''); seems to be const exclusions = exclusionsVector.toNumber(2).split(''); with current Javascript versions, right?

But what about line 38, neighbor.color = getRandomColor(colors, neighborExcludedColors);, where is the variable colors coming from...?

Hi @brmarkus,

For line 15, I am unable to see any differences between both versions that you described.

For line 38, I think I ran this inside their online runtime environment that provided colors as a global variable.

Yes, you are right, two times the same. I needed to change const exclusions = exclusionsVector.toNumber(2).split(''); to const exclusions = exclusionsVector.toString(2).split(''); due to a "compile error"

Is it usual that variables were pre-set, provided...? I think the two method parameters in function colorGraph(graph, allColors) are provided from their automated test set and defines the playground, besides your tests?

Anyway, I was happy to find your version, thank you very much for the inspirations.