Skip to content

Instantly share code, notes, and snippets.

@arrieta
Created November 8, 2021 14:27
Show Gist options
  • Save arrieta/4fdf7e2d8e444e640ffe9bb15ebc67cb to your computer and use it in GitHub Desktop.
Save arrieta/4fdf7e2d8e444e640ffe9bb15ebc67cb to your computer and use it in GitHub Desktop.
Graph Coloring Algorithms
#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));
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment