Skip to content

Instantly share code, notes, and snippets.

@opsec-ee

opsec-ee/grphcolr.c

Created January 24, 2026 23:59
Show Gist options

  • Select an option

    Learn more about clone URLs
  • Save opsec-ee/661b126139746972afe931a6ef35442a to your computer and use it in GitHub Desktop.

Select an option

Learn more about clone URLs
Save opsec-ee/661b126139746972afe931a6ef35442a to your computer and use it in GitHub Desktop.
Download ZIP
Graph Coloring in C
Raw
grphcolr.c
/* Author: H. Overman 2026 */
/* n/a "toy" */
#include <stdbool.h>
#include <stdint.h>
#include <string.h>
#include <stdio.h>
#include <time.h>
#define MAX_VERTICES 64
#define MAX_COLORS 32
typedef struct {
int n;
int k;
uint64_t adj[MAX_VERTICES];
uint32_t domain[MAX_VERTICES];
int color[MAX_VERTICES];
uint32_t saved[MAX_VERTICES][MAX_VERTICES];
uint8_t changed[MAX_VERTICES][MAX_VERTICES];
int nchanged[MAX_VERTICES];
} ColoringCtx;
static inline int select_mrv(const ColoringCtx *ctx)
{
int best = -1;
int best_count = MAX_COLORS + 1;
for (int v = 0; v < ctx->n; v++) {
if (ctx->color[v] != -1)
continue;
int cnt = __builtin_popcount(ctx->domain[v]);
if (cnt == 0)
return -1;
if (cnt < best_count) {
best_count = cnt;
best = v;
if (cnt == 1)
break;
}
}
return best;
}
static bool solve(ColoringCtx *ctx, int depth, int remaining)
{
if (remaining == 0)
return true;
int v = select_mrv(ctx);
if (v < 0)
return false;
uint32_t avail = ctx->domain[v];
const uint64_t nbrs = ctx->adj[v];
while (avail) {
int c = __builtin_ctz(avail);
avail &= avail - 1;
uint32_t cmask = 1u << c;
ctx->color[v] = c;
uint64_t scan = nbrs;
int nc = 0;
bool wipeout = false;
while (scan && !wipeout) {
int u = __builtin_ctzll(scan);
scan &= scan - 1;
if (ctx->color[u] == -1 && (ctx->domain[u] & cmask)) {
ctx->saved[depth][nc] = ctx->domain[u];
ctx->changed[depth][nc] = (uint8_t)u;
nc++;
ctx->domain[u] ^= cmask;
wipeout = (ctx->domain[u] == 0);
}
}
ctx->nchanged[depth] = nc;
if (!wipeout && solve(ctx, depth + 1, remaining - 1))
return true;
for (int i = 0; i < nc; i++)
ctx->domain[ctx->changed[depth][i]] = ctx->saved[depth][i];
ctx->color[v] = -1;
}
return false;
}
bool graph_color_verify(int n, uint64_t conflicts[], int k, int out_color[])
{
if (n <= 0 || n > MAX_VERTICES || k <= 0 || k > MAX_COLORS)
return false;
static ColoringCtx ctx;
ctx.n = n;
ctx.k = k;
uint32_t full = (k == 32) ? ~0u : (1u << k) - 1;
for (int i = 0; i < n; i++) {
ctx.adj[i] = conflicts[i] & ~(1ULL << i);
ctx.domain[i] = full;
ctx.color[i] = -1;
}
if (!solve(&ctx, 0, n))
return false;
for (int i = 0; i < n; i++)
out_color[i] = ctx.color[i];
return true;
}
/* ─────────────────────────────────────────────────────────────────────────── */
/* TESTS */
/* ─────────────────────────────────────────────────────────────────────────── */
static double get_time_ms(void)
{
struct timespec ts;
timespec_get(&ts, TIME_UTC);
return ts.tv_sec * 1000.0 + ts.tv_nsec / 1e6;
}
static bool verify_coloring(int n, uint64_t conflicts[], int colors[])
{
for (int i = 0; i < n; i++) {
if (colors[i] < 0)
return false;
uint64_t nbrs = conflicts[i] & ~(1ULL << i);
while (nbrs) {
int j = __builtin_ctzll(nbrs);
nbrs &= nbrs - 1;
if (colors[i] == colors[j])
return false;
}
}
return true;
}
static bool run_test(const char *name, int n, uint64_t conflicts[],
int k, bool expect)
{
int colors[MAX_VERTICES];
double t0 = get_time_ms();
bool found = graph_color_verify(n, conflicts, k, colors);
double t1 = get_time_ms();
bool pass = (found == expect);
if (found && !verify_coloring(n, conflicts, colors))
pass = false;
printf("[%s] %s: %s (%.3f ms)\n",
pass ? "PASS" : "FAIL", name,
found ? "VERIFIED" : "REJECTED", t1 - t0);
if (found && n <= 10) {
printf(" Coloring:");
for (int i = 0; i < n; i++)
printf(" v%d=%d", i, colors[i]);
printf("\n");
}
return pass;
}
int main(void)
{
printf("Graph Coloring Tests\n");
printf("════════════════════\n\n");
int passed = 0, total = 0;
/* Test 1: Triangle (K3) - needs 3 colors */
{
uint64_t g[3] = {
(1ULL<<1)|(1ULL<<2),
(1ULL<<0)|(1ULL<<2),
(1ULL<<0)|(1ULL<<1)
};
total++; if (run_test("K3, k=3", 3, g, 3, true)) passed++;
total++; if (run_test("K3, k=2", 3, g, 2, false)) passed++;
}
/* Test 2: Square (C4) - bipartite, needs 2 */
{
uint64_t g[4] = {
(1ULL<<1)|(1ULL<<3),
(1ULL<<0)|(1ULL<<2),
(1ULL<<1)|(1ULL<<3),
(1ULL<<0)|(1ULL<<2)
};
total++; if (run_test("C4, k=2", 4, g, 2, true)) passed++;
}
/* Test 3: Pentagon (C5) - odd cycle, needs 3 */
{
uint64_t g[5] = {
(1ULL<<1)|(1ULL<<4),
(1ULL<<0)|(1ULL<<2),
(1ULL<<1)|(1ULL<<3),
(1ULL<<2)|(1ULL<<4),
(1ULL<<3)|(1ULL<<0)
};
total++; if (run_test("C5, k=3", 5, g, 3, true)) passed++;
total++; if (run_test("C5, k=2", 5, g, 2, false)) passed++;
}
/* Test 4: Complete K5 - needs 5 */
{
uint64_t g[5];
for (int i = 0; i < 5; i++)
g[i] = 0b11111 & ~(1ULL << i);
total++; if (run_test("K5, k=5", 5, g, 5, true)) passed++;
total++; if (run_test("K5, k=4", 5, g, 4, false)) passed++;
}
/* Test 5: Petersen graph - chromatic number 3 */
{
uint64_t g[10] = {
(1ULL<<1)|(1ULL<<4)|(1ULL<<5),
(1ULL<<0)|(1ULL<<2)|(1ULL<<6),
(1ULL<<1)|(1ULL<<3)|(1ULL<<7),
(1ULL<<2)|(1ULL<<4)|(1ULL<<8),
(1ULL<<3)|(1ULL<<0)|(1ULL<<9),
(1ULL<<0)|(1ULL<<7)|(1ULL<<8),
(1ULL<<1)|(1ULL<<8)|(1ULL<<9),
(1ULL<<2)|(1ULL<<9)|(1ULL<<5),
(1ULL<<3)|(1ULL<<5)|(1ULL<<6),
(1ULL<<4)|(1ULL<<6)|(1ULL<<7)
};
total++; if (run_test("Petersen, k=3", 10, g, 3, true)) passed++;
}
/* Test 6: Bipartite K_{3,3} - needs 2 */
{
uint64_t g[6] = {
(1ULL<<3)|(1ULL<<4)|(1ULL<<5),
(1ULL<<3)|(1ULL<<4)|(1ULL<<5),
(1ULL<<3)|(1ULL<<4)|(1ULL<<5),
(1ULL<<0)|(1ULL<<1)|(1ULL<<2),
(1ULL<<0)|(1ULL<<1)|(1ULL<<2),
(1ULL<<0)|(1ULL<<1)|(1ULL<<2)
};
total++; if (run_test("K3,3, k=2", 6, g, 2, true)) passed++;
}
/* Test 7: Wheel W6 (hub + C5) - needs 4 */
{
uint64_t g[6] = {
(1ULL<<1)|(1ULL<<2)|(1ULL<<3)|(1ULL<<4)|(1ULL<<5), /* hub */
(1ULL<<0)|(1ULL<<2)|(1ULL<<5), /* v1-v2, v1-v5 */
(1ULL<<0)|(1ULL<<1)|(1ULL<<3), /* v2-v1, v2-v3 */
(1ULL<<0)|(1ULL<<2)|(1ULL<<4), /* v3-v2, v3-v4 */
(1ULL<<0)|(1ULL<<3)|(1ULL<<5), /* v4-v3, v4-v5 */
(1ULL<<0)|(1ULL<<4)|(1ULL<<1) /* v5-v4, v5-v1 */
};
total++; if (run_test("W6, k=4", 6, g, 4, true)) passed++;
total++; if (run_test("W6, k=3", 6, g, 3, false)) passed++;
}
/* Test 8: Dense 40-vertex random graph */
{
uint64_t g[40] = {0};
uint64_t seed = 12345;
for (int i = 0; i < 40; i++) {
for (int j = i + 1; j < 40; j++) {
seed = seed * 6364136223846793005ULL + 1;
if ((seed >> 60) < 10) {
g[i] |= (1ULL << j);
g[j] |= (1ULL << i);
}
}
}
total++; if (run_test("Dense40, k=20", 40, g, 20, true)) passed++;
}
/* Test 9: Sparse 50-vertex random graph */
{
uint64_t g[50] = {0};
uint64_t seed = 99999;
for (int i = 0; i < 50; i++) {
for (int j = i + 1; j < 50; j++) {
seed = seed * 6364136223846793005ULL + 1;
if ((seed >> 60) < 3) {
g[i] |= (1ULL << j);
g[j] |= (1ULL << i);
}
}
}
total++; if (run_test("Sparse50, k=5", 50, g, 5, true)) passed++;
}
/* Test 10: Self-loops (should be ignored) */
{
uint64_t g[3] = {
(1ULL<<0)|(1ULL<<1)|(1ULL<<2),
(1ULL<<0)|(1ULL<<1)|(1ULL<<2),
(1ULL<<0)|(1ULL<<1)|(1ULL<<2)
};
total++; if (run_test("K3+self, k=3", 3, g, 3, true)) passed++;
}
/* Test 11: Empty graph - 1 color suffices */
{
uint64_t g[5] = {0, 0, 0, 0, 0};
total++; if (run_test("Empty5, k=1", 5, g, 1, true)) passed++;
}
/* Test 12: Single vertex */
{
uint64_t g[1] = {0};
total++; if (run_test("Single, k=1", 1, g, 1, true)) passed++;
}
/* Test 13: Complete K8 - needs 8 */
{
uint64_t g[8];
for (int i = 0; i < 8; i++)
g[i] = 0xFF & ~(1ULL << i);
total++; if (run_test("K8, k=8", 8, g, 8, true)) passed++;
total++; if (run_test("K8, k=7", 8, g, 7, false)) passed++;
}
printf("\n════════════════════\n");
printf("Results: %d/%d passed\n", passed, total);
/* Benchmark */
{
uint64_t g[40] = {0};
uint64_t seed = 77777;
for (int i = 0; i < 40; i++) {
for (int j = i + 1; j < 40; j++) {
seed = seed * 6364136223846793005ULL + 1;
if ((seed >> 60) < 8) {
g[i] |= (1ULL << j);
g[j] |= (1ULL << i);
}
}
}
int colors[MAX_VERTICES];
int iters = 10000;
double t0 = get_time_ms();
for (int i = 0; i < iters; i++)
graph_color_verify(40, g, 15, colors);
double t1 = get_time_ms();
printf("\n[BENCH] %d iterations: %.2f ms total, %.2f µs/call\n",
iters, t1 - t0, (t1 - t0) * 1000.0 / iters);
}
return (passed == total) ? 0 : 1;
}
/**
* [user@localhost tools]$ gcc -std=c23 -O3 -march=native -flto -DNDEBUG grphcolr.c -o grphcolr
* [user@localhost tools]$ ./grphcolr
* Graph Coloring Tests
* ════════════════════
*
* [PASS] K3, k=3: VERIFIED (0.028 ms)
* Coloring: v0=0 v1=1 v2=2
* [PASS] K3, k=2: REJECTED (0.001 ms)
* [PASS] C4, k=2: VERIFIED (0.001 ms)
* Coloring: v0=0 v1=1 v2=0 v3=1
* [PASS] C5, k=3: VERIFIED (0.001 ms)
* Coloring: v0=0 v1=1 v2=0 v3=1 v4=2
* [PASS] C5, k=2: REJECTED (0.001 ms)
* [PASS] K5, k=5: VERIFIED (0.001 ms)
* Coloring: v0=0 v1=1 v2=2 v3=3 v4=4
* [PASS] K5, k=4: REJECTED (0.005 ms)
* [PASS] Petersen, k=3: VERIFIED (0.004 ms)
* Coloring: v0=0 v1=1 v2=0 v3=1 v4=2 v5=1 v6=0 v7=2 v8=2 v9=1
* [PASS] K3,3, k=2: VERIFIED (0.002 ms)
* Coloring: v0=0 v1=0 v2=0 v3=1 v4=1 v5=1
* [PASS] W6, k=4: VERIFIED (0.002 ms)
* Coloring: v0=0 v1=1 v2=2 v3=1 v4=2 v5=3
* [PASS] W6, k=3: REJECTED (0.003 ms)
* [PASS] Dense40, k=20: VERIFIED (0.081 ms)
* [PASS] Sparse50, k=5: VERIFIED (0.039 ms)
* [PASS] K3+self, k=3: VERIFIED (0.001 ms)
* Coloring: v0=0 v1=1 v2=2
* [PASS] Empty5, k=1: VERIFIED (0.001 ms)
* Coloring: v0=0 v1=0 v2=0 v3=0 v4=0
* [PASS] Single, k=1: VERIFIED (0.000 ms)
* Coloring: v0=0
* [PASS] K8, k=8: VERIFIED (0.003 ms)
* Coloring: v0=0 v1=1 v2=2 v3=3 v4=4 v5=5 v6=6 v7=7
* [PASS] K8, k=7: REJECTED (1.003 ms)
*
* ════════════════════
* Results: 18/18 passed
*
* [BENCH] 10000 iterations: 23.94 ms total, 2.39 µs/call
*
*/
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment