Graph Utilities

Block Gibbs needs the free blocks to be independent sets — no two nodes in one block may share a factor — so building a sampler for a new graph starts with a graph coloring. rlf_coloring implements Recursive Largest First, which produces the color classes that become the free blocks.

The high-level model front doors (IsingEBM via ising_sample, and the continuous programs) call this for you; reach for it directly when you are assembling a custom PGM and need the sampling order yourself.

hamon.graph_utils.rlf_coloring(n_nodes: int, edges: collections.abc.Iterable[tuple[int, int]]) -> list[int]

Color an integer-indexed graph with Recursive Largest First (RLF).

Nodes are 0 .. n_nodes - 1; edges are (u, v) index pairs (direction and duplicates ignored, self-loops dropped) — any iterable of pairs or an (m, 2) integer array. Returns colors where colors[i] is the color class of node i.

RLF builds each color class as a maximal independent set, repeatedly adding the vertex with the most neighbors already excluded from the class (ties broken toward fewest remaining-candidate neighbors, then smallest index). It minimizes the number of colors more aggressively than first-fit/greedy heuristics on dense graphs and matches them on sparse/bipartite ones — and in hamon the color count is the number of sequential block-Gibbs groups, which sets the NRPT round-loop XLA compile cost. Deterministic (index tie-breaking) so colorings are reproducible.

Carries no worst-case bound and can exceed degeneracy + 1, though rarely enough on real interaction graphs that a smallest-last fallback was measured and did not earn its keep.

The selection rule is evaluated with incrementally maintained neighbor counters over a CSR adjacency and a vectorized argmax, so the cost is O(|V|² elementwise + |V|·χ + |E|·χ) in NumPy rather than O(|V|·|E|) in Python-set operations. The coloring produced is identical to the reference set-based implementation for any input.