graph-coloring

graph-coloring.js

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

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];
const colors = ['red', 'green'];

function colorGraph(graph, colors) {
  const queue = [graph[0]];
  let index = 0;
  let currentGraph;

  while (queue.length) {
    currentGraph = queue.pop();
    if (!currentGraph.color) {
      currentGraph.color = colors[index];
      index++;
      if (index === colors.length) index = 0;
    }
    
    currentGraph.neighbors.forEach(neighbor => {
      if (neighbor.label === currentGraph.label) throw new Error('loop graphs are invalid');
      if (!neighbor.color) {
        queue.push(neighbor);
      }
    });
  }
  return graph;
}