Graph Coloring Algorithms

node-coloring-greedy.cpp

#include <algorithm>
#include <iostream>
#include <map>
#include <numeric>
#include <set>
#include <vector>

using Graph    = std::vector<std::set<int>>;
using Coloring = std::vector<int>;

auto sorting(const Graph& g) {
  std::vector<int> nodes(g.size());
  std::iota(nodes.begin(), nodes.end(), 0);

  auto pred = [&g](auto i, auto j) { return g[i].size() > g[j].size(); };
  std::sort(nodes.begin(), nodes.end(), pred);

  return nodes;
}

auto minimum_color(int v, const Graph& g, const Coloring& c) {
  std::set<int> forbidden_colors;
  for (auto n : g[v]) {
    if (auto f = c[n]; f >= 0) {
      forbidden_colors.insert(f);
    }
  }
  auto color = 0;
  while (forbidden_colors.contains(color)) {
    ++color;
  }
  return color;
}

auto color(const Graph& g) {
  Coloring c(g.size(), -1);
  for (auto node : sorting(g)) {
    c[node] = minimum_color(node, g, c);
  }
  return c;
}

std::map<int, std::string> CMAP{
    {0, "#FF2244"},
    {1, "#AABBCC"},
    {2, "#459123"},
    {4, "#3F9B1A"},
};

auto dot(const Graph& g, const Coloring& c) {
  std::cout << "graph {\n";
  for (auto k = 0u; k < c.size(); ++k) {
    std::cout << "node [color=\"" << CMAP.at(c[k]) << "\"]; "
              << "N" << k << ";\n";
  }
  for (auto k = 0u; k < g.size(); ++k) {
    for (auto b : g[k]) {
      std::cout << "N" << k << " -- N" << b << ";\n";
    }
  }
  std::cout << "overlap=false;\n"
            << "label=\"Proper Coloring of Peterson Graph\";\n"
            << "}\n";
}

int main() {
  std::vector<std::pair<int, int>> pairs = {
      {0, 1}, {1, 2}, {2, 3}, {3, 4}, {4, 0}, {0, 5}, {1, 6}, {2, 7},
      {3, 8}, {4, 9}, {5, 7}, {7, 9}, {9, 6}, {6, 8}, {8, 5},
  };

  Graph g(10u);
  for (auto [a, b] : pairs) {
    g[a].insert(b);
    g[b].insert(a);
  }

  dot(g, color(g));
}