chromatic_number.hpp¶
Exact minimum vertex coloring for an undirected graph with at most 64 vertices using DSATUR branch-and-bound.
Verified by chromatic_number.
精确计算一般图的最小顶点着色数；适合点数较小的不可相邻同色分组。
Implementation¶
#ifndef NOYA_CHROMATIC_NUMBER_HPP
#define NOYA_CHROMATIC_NUMBER_HPP 1
/// @complexity Time: O(n 2^n).
/// Space: O(2^n).
#include <bit>
#include <cassert>
#include <cstdint>
#include <utility>
#include <vector>
namespace noya {
struct graph_coloring_result {
int color_count = 0;
std::vector<int> color;
};
/// @brief Exact minimum vertex coloring for an undirected graph with at most
/// 64 vertices using DSATUR branch-and-bound.
inline graph_coloring_result
minimum_graph_coloring(int n, const std::vector<std::pair<int, int>> &edges) {
assert(0 <= n && n <= 64);
std::vector<std::uint64_t> adjacency(n);
for (auto [first, second] : edges) {
assert(0 <= first && first < n);
assert(0 <= second && second < n);
if (first == second) {
continue;
}
adjacency[first] |= std::uint64_t(1) << second;
adjacency[second] |= std::uint64_t(1) << first;
}
graph_coloring_result best;
best.color_count = n;
best.color.resize(n);
for (int vertex = 0; vertex < n; vertex++) {
best.color[vertex] = vertex;
}
if (n == 0) {
return best;
}
std::vector<int> color(n, -1);
auto search = [&](auto &self, int colored, int used_colors) -> void {
if (used_colors >= best.color_count) {
return;
}
if (colored == n) {
best.color_count = used_colors;
best.color = color;
return;
}
int chosen = -1;
int chosen_saturation = -1;
int chosen_degree = -1;
std::uint64_t chosen_forbidden = 0;
for (int vertex = 0; vertex < n; vertex++) {
if (color[vertex] != -1) {
continue;
}
std::uint64_t forbidden = 0;
std::uint64_t neighbors = adjacency[vertex];
while (neighbors != 0) {
int next = std::countr_zero(neighbors);
neighbors &= neighbors - 1;
if (color[next] != -1) {
forbidden |= std::uint64_t(1) << color[next];
}
}
int saturation = std::popcount(forbidden);
int degree = std::popcount(adjacency[vertex]);
if (saturation > chosen_saturation ||
(saturation == chosen_saturation && degree > chosen_degree)) {
chosen = vertex;
chosen_saturation = saturation;
chosen_degree = degree;
chosen_forbidden = forbidden;
}
}
for (int value = 0; value < used_colors; value++) {
if (!(chosen_forbidden >> value & 1)) {
color[chosen] = value;
self(self, colored + 1, used_colors);
color[chosen] = -1;
}
}
if (used_colors + 1 < best.color_count) {
color[chosen] = used_colors;
self(self, colored + 1, used_colors + 1);
color[chosen] = -1;
}
};
search(search, 0, 0);
return best;
}
} // namespace noya
#endif // NOYA_CHROMATIC_NUMBER_HPP
#include <bit>
#include <cassert>
#include <cstdint>
#include <utility>
#include <vector>
/// @complexity Time: O(n 2^n).
/// Space: O(2^n).
namespace noya {
struct graph_coloring_result {
int color_count = 0;
std::vector<int> color;
};
/// @brief Exact minimum vertex coloring for an undirected graph with at most
/// 64 vertices using DSATUR branch-and-bound.
inline graph_coloring_result
minimum_graph_coloring(int n, const std::vector<std::pair<int, int>> &edges) {
assert(0 <= n && n <= 64);
std::vector<std::uint64_t> adjacency(n);
for (auto [first, second] : edges) {
assert(0 <= first && first < n);
assert(0 <= second && second < n);
if (first == second) {
continue;
}
adjacency[first] |= std::uint64_t(1) << second;
adjacency[second] |= std::uint64_t(1) << first;
}
graph_coloring_result best;
best.color_count = n;
best.color.resize(n);
for (int vertex = 0; vertex < n; vertex++) {
best.color[vertex] = vertex;
}
if (n == 0) {
return best;
}
std::vector<int> color(n, -1);
auto search = [&](auto &self, int colored, int used_colors) -> void {
if (used_colors >= best.color_count) {
return;
}
if (colored == n) {
best.color_count = used_colors;
best.color = color;
return;
}
int chosen = -1;
int chosen_saturation = -1;
int chosen_degree = -1;
std::uint64_t chosen_forbidden = 0;
for (int vertex = 0; vertex < n; vertex++) {
if (color[vertex] != -1) {
continue;
}
std::uint64_t forbidden = 0;
std::uint64_t neighbors = adjacency[vertex];
while (neighbors != 0) {
int next = std::countr_zero(neighbors);
neighbors &= neighbors - 1;
if (color[next] != -1) {
forbidden |= std::uint64_t(1) << color[next];
}
}
int saturation = std::popcount(forbidden);
int degree = std::popcount(adjacency[vertex]);
if (saturation > chosen_saturation ||
(saturation == chosen_saturation && degree > chosen_degree)) {
chosen = vertex;
chosen_saturation = saturation;
chosen_degree = degree;
chosen_forbidden = forbidden;
}
}
for (int value = 0; value < used_colors; value++) {
if (!(chosen_forbidden >> value & 1)) {
color[chosen] = value;
self(self, colored + 1, used_colors);
color[chosen] = -1;
}
}
if (used_colors + 1 < best.color_count) {
color[chosen] = used_colors;
self(self, colored + 1, used_colors + 1);
color[chosen] = -1;
}
};
search(search, 0, 0);
return best;
}
} // namespace noya