API Reference

Main Functions

Main public API for parkol: sample_coloring().

parkol.sample.sample_coloring(graph, k, method='hybrid', seed=None, adaptive=False, target_components=None)[source]

Draw an exact uniform sample of a proper k-coloring of a graph.

Parameters:

  • graph (nx.Graph) – The input graph.

  • k (int) – Number of colours. Must be at least the chromatic number of the graph.

  • method (str) –

    Sampling method to use:

    • 'hybrid' (default): PRS decomposition with auto-selected component solver. Defaults to Huber CFTP (simplest, fastest in practice); falls back to BC20 CFTP if Huber fails to coalesce, and to NRS if k <= Delta.

    • 'prs': Pure gamma-PRS (iterative).

    • 'cftp_huber': Huber (2004) bounding-chain CFTP. Requires k > Delta.

    • 'cftp_bc20': Bhandari & Chakraborty (2020) CFTP. Requires k > 3*Delta.

    • 'nrs': Naive rejection sampling.

  • seed (int or None) – Random seed for reproducibility.

  • adaptive (bool) – If True (and method is 'hybrid'), use an adaptive gamma-sequence that decreases gamma to encourage the resampling set to split into multiple components, maximising parallelisation. The number of components may be fewer than target_components since the gamma-soft bad set is a subset of the bad set for proper colouring.

  • target_components (int or None) – Maximum number of desired components for the adaptive strategy. Defaults to the number of available CPU cores.

Returns:

colors (dict) – A proper k-colouring mapping node -> colour (integers in {1, …, k}).

Raises:

  • ValueError – If the method is unknown or k does not satisfy the method’s condition.

  • RuntimeError – If the algorithm does not converge.

Utilities

parkol.utils.verify_coloring(graph, colors)[source]

Verify that a coloring is proper.

Parameters:

  • graph (nx.Graph) – The graph.

  • colors (dict) – Mapping from node to color.

Returns:

bool – True if the coloring is proper (no adjacent vertices share a color).

parkol.utils.has_improper_edge(graph, colors)[source]

Check if any edge has same-colour endpoints (dict-based).

Core Algorithms

Core gamma-PRS algorithm for uniform graph colouring.

Implements the partial rejection sampling method from:
“Uniform Sampling of Graph Colourings via Soft Colouring and Partial

Rejection Sampling”

parkol.prs.compute_n_v_vec(G, colors, u_values, gamma)[source]

Compute n_v(gamma, x) for all vertices using sparse matrix ops.

n_v = number of neighbours w with c_w = c_v and u_w > gamma^{d_w}.

parkol.prs.find_bad_vertices_vec(G, colors, u_values, gamma, mask=None)[source]

Find bad vertices: {v : u_v > gamma^{n_v}}.

Returns boolean array. If mask is given, only vertices in mask are checked.

parkol.prs.find_resampling_set_vec(G, colors, u_values, gamma, mask=None)[source]

Algorithm 1: Find the resampling set R via BFS from bad vertices.

Starting from Bad(x, gamma), expand through non-passive vertices. Include one layer of passive boundary vertices.

parkol.prs.resample_vertices_vec(colors, u_values, k, R_mask, rng)[source]

Resample colours and u-values for vertices where R_mask is True.

parkol.prs.gamma_prs_recursive(G, colors, u_values, gamma_seq, ell, mask, rng, stats, depth=0, max_depth=100000)[source]

Algorithm 4: gamma-PRS(G, x, ell) – recursive implementation.

parkol.prs.gamma_prs_iterative(G, colors, u_values, gamma, mask, rng, stats, max_iter=10000000)[source]

Iterative PRS at a single gamma level.

Repeatedly: find bad vertices -> compute R -> resample R, until Bad(x, gamma) is empty.

parkol.prs.prs_graph_coloring(graph, k, gamma_base=0.9, max_levels=1000, seed=None, recursive=False)[source]

Uniform sampling of a proper k-colouring via gamma-PRS.

Parameters:

  • graph (nx.Graph) – The input graph.

  • k (int) – Number of colours (must be >= chromatic number).

  • gamma_base (float) – Base for the gamma-sequence: gamma_ell = gamma_base^ell.

  • max_levels (int) – Safety limit on the number of levels.

  • seed (int or None) – Random seed for reproducibility.

  • recursive (bool) – If True, use the full recursive Algorithm 4. If False, use iterative PRS at each level (faster, practical).

Returns:

  • colors (dict) – A proper k-colouring mapping node -> colour (1-indexed).

  • stats (dict) – Run statistics.

Hybrid gamma-PRS: PRS for global decomposition into independent components, then an exact sampler on each component.

The idea: PRS at each level identifies the resampling set R and splits it into connected components. Instead of recursive gamma-PRS on each component, an off-the-shelf exact sampler (NRS, CFTP) produces a sample from eta_{gamma_ell} restricted to that component.

parkol.hybrid.prs_hybrid(graph, k, gamma_base=0.9, max_levels=1000, seed=None, component_solver='nrs', adaptive=False, target_components=None)[source]

Hybrid gamma-PRS: PRS decomposition + exact sampler on components.

Parameters:

  • graph (nx.Graph)

  • k (int)

  • gamma_base (float) – Base for the geometric gamma-sequence: gamma_ell = gamma_base^ell. Ignored when adaptive=True.

  • max_levels (int)

  • seed (int or None)

  • component_solver (str) – ‘nrs’ : Naive rejection sampling on each component. ‘cftp_huber’ : Huber (2004) bounding chain CFTP. ‘cftp_bc20’ : Bhandari & Chakraborty (2020) CFTP.

  • adaptive (bool) – If True, use an adaptive gamma-sequence: at each level, decrease gamma by small steps to encourage the resampling set to split into multiple components for parallel processing. The algorithm aims for at most target_components components, but fewer may arise since the gamma-soft bad set is a subset of the bad set for proper colouring.

  • target_components (int or None) – Maximum number of desired components when adaptive=True. Defaults to the number of available CPU cores (os.cpu_count()).

Returns:

  • colors (dict) – Proper k-colouring mapping node -> colour (1-indexed).

  • stats (dict)

Coupling From The Past (CFTP) with bounding chains for graph colouring.

Implements Huber’s (2004) bounding chain method:

  • Underlying chain: Glauber dynamics for proper k-colorings

  • Bounding chain: tracks sets Y(v) of possible colors per vertex

  • Coalescence: all Y(v) are singletons

Condition for polynomial runtime: k >= Delta*(Delta+2). Correct (exact uniform sample) for any k > Delta.

Reference: Huber, “Perfect Sampling Using Bounding Chains”,

Annals of Applied Probability, 2004.

parkol.cftp_huber.cftp_coloring(graph, k, seed=None, max_doubling=25)[source]

CFTP with bounding chains for uniform proper k-colouring.

Parameters:

  • graph (nx.Graph)

  • k (int) – Number of colours. Must be > max degree.

  • seed (int or None)

  • max_doubling (int)

Returns:

  • colors (dict) – A uniformly selected proper k-colouring (node -> colour, 1-indexed).

  • stats (dict)

parkol.cftp_huber.cftp_coloring_on_component(graph, k, component_vertices, boundary_colors, seed=None, max_doubling=20)[source]

CFTP on a subgraph with fixed boundary colours.

Parameters:

  • graph (nx.Graph) – The full graph.

  • k (int)

  • component_vertices (set or list) – Vertices to recolour.

  • boundary_colors (dict) – Fixed colours of vertices adjacent to the component.

  • seed (int or None)

  • max_doubling (int)

Returns:

  • colors (dict) – Proper colouring of the component vertices (node -> colour, 1-indexed).

  • stats (dict)

CFTP with Bhandari & Chakraborty (2020) bounding chain for graph colouring.

Implements Algorithm 1 (PerfectSampler) from:

Bhandari & Chakraborty, “Improved bounds for perfect sampling of k-colorings in graphs”, STOC 2020.

Two-phase structure:

  1. Collapsing phase: reduce all bounding lists to size <= 2 via SPRUCEUP + CONTRACT operations.

  2. Coalescing phase: reduce all lists to size 1 via CONTRACT operations on randomly chosen vertices.

Condition for correctness and polynomial runtime: k > 3 * Delta.

Colors are integers in {0, 1, …, k-1} internally. The public interface returns colors in {1, …, k}.

parkol.cftp_bc20.cftp_bc20(graph, k, seed=None, max_doubling=20)[source]

Perfect sampling of k-colorings via BC20 CFTP.

Parameters:

  • graph (nx.Graph)

  • k (int) – Number of colors. Must satisfy k > 3 * Delta.

  • seed (int or None)

  • max_doubling (int)

Returns:

  • colors (dict) – A uniformly random proper k-coloring (node -> colour, 1-indexed).

  • stats (dict)

parkol.cftp_bc20.cftp_bc20_on_component(graph, k, component_vertices, boundary_colors, seed=None, max_doubling=20)[source]

BC20 CFTP on a subgraph with fixed boundary colors.

Parameters:

  • graph (nx.Graph)

  • k (int) – Must satisfy k > 3 * Delta.

  • component_vertices (set or list)

  • boundary_colors (dict) – Fixed colors in {1, …, k}.

  • seed (int or None)

  • max_doubling (int)

Returns:

  • colors (dict) – Proper coloring of the component vertices (node -> colour, 1-indexed).

  • stats (dict)