Struct KColoring 

pub struct KColoring<K: KValue, G> { /* private fields */ }

The Graph K-Coloring problem.

Given a graph G = (V, E) and K colors, find an assignment of colors to vertices such that no two adjacent vertices have the same color.

Type Parameters

• K - KValue type representing the number of colors (e.g., K3 for 3-coloring)
• G - Graph type (e.g., SimpleGraph, KingsSubgraph)

Example

use problemreductions::models::graph::KColoring;
use problemreductions::topology::SimpleGraph;
use problemreductions::variant::K3;
use problemreductions::{Problem, Solver, BruteForce};

// Triangle graph needs at least 3 colors
let graph = SimpleGraph::new(3, vec![(0, 1), (1, 2), (0, 2)]);
let problem = KColoring::<K3, _>::new(graph);

let solver = BruteForce::new();
let solutions = solver.find_all_satisfying(&problem);

// Verify all solutions are valid colorings
for sol in &solutions {
    assert!(problem.evaluate(sol));
}

Implementations

impl<K: KValue, G: Graph> KColoring<K, G>

pub fn new(graph: G) -> Self

Create a new K-Coloring problem from a graph.

Panics

Panics if K is KN (use KColoring::<KN, G>::with_k instead).

pub fn graph(&self) -> &G

Get a reference to the underlying graph.

pub fn num_colors(&self) -> usize

Get the number of colors.

pub fn is_valid_solution(&self, config: &[usize]) -> bool

Check if a configuration is a valid coloring.

impl<G: Graph> KColoring<KN, G>

pub fn with_k(graph: G, num_colors: usize) -> Self

Create a K-Coloring problem with an explicit number of colors.

Only available for KN (runtime K). For compile-time K types like K3, use new which derives K from the type parameter.

impl<K: KValue, G: Graph> KColoring<K, G>

pub fn num_vertices(&self) -> usize

Get the number of vertices in the underlying graph.

pub fn num_edges(&self) -> usize

Get the number of edges in the underlying graph.

Trait Implementations

impl<K: Clone + KValue, G: Clone> Clone for KColoring<K, G>

fn clone(&self) -> KColoring<K, G>

Returns a duplicate of the value.

fn clone_from(&mut self, source: &Self)

Performs copy-assignment from source.

impl<K: Debug + KValue, G: Debug> Debug for KColoring<K, G>

fn fmt(&self, f: &mut Formatter<'_>) -> Result

Formats the value using the given formatter.

impl<'de, K: KValue, G> Deserialize<'de> for KColoring<K, G>

where G: Deserialize<'de>,

fn deserialize<__D>(__deserializer: __D) -> Result<Self, __D::Error>

where __D: Deserializer<'de>,

Deserialize this value from the given Serde deserializer.

impl<K: KValue, G> Problem for KColoring<K, G>

where G: Graph + VariantParam,

const NAME: &'static str = "KColoring"

Base name of this problem type (e.g., “MaximumIndependentSet”).

type Metric = bool

The evaluation metric type.

fn variant() -> Vec<(&'static str, &'static str)>

Returns variant attributes derived from type parameters.

fn dims(&self) -> Vec<usize>

Configuration space dimensions. Each entry is the cardinality of that variable.

fn evaluate(&self, config: &[usize]) -> bool

Evaluate the problem on a configuration.

fn num_variables(&self) -> usize

Number of variables (derived from dims).

impl ReduceTo<ILP> for KColoring<K1, SimpleGraph>

type Result = ReductionKColoringToILP<K1, SimpleGraph>

The reduction result type.

fn reduce_to(&self) -> Self::Result

Reduce this problem to the target problem type.

impl ReduceTo<ILP> for KColoring<K2, SimpleGraph>

type Result = ReductionKColoringToILP<K2, SimpleGraph>

The reduction result type.

fn reduce_to(&self) -> Self::Result

Reduce this problem to the target problem type.

impl ReduceTo<ILP> for KColoring<K3, SimpleGraph>

type Result = ReductionKColoringToILP<K3, SimpleGraph>

The reduction result type.

fn reduce_to(&self) -> Self::Result

Reduce this problem to the target problem type.

impl ReduceTo<ILP> for KColoring<K4, SimpleGraph>

type Result = ReductionKColoringToILP<K4, SimpleGraph>

The reduction result type.

fn reduce_to(&self) -> Self::Result

Reduce this problem to the target problem type.

impl ReduceTo<ILP> for KColoring<KN, SimpleGraph>

type Result = ReductionKColoringToILP<KN, SimpleGraph>

The reduction result type.

fn reduce_to(&self) -> Self::Result

Reduce this problem to the target problem type.

impl ReduceTo<KColoring<K3, SimpleGraph>> for Satisfiability

type Result = ReductionSATToColoring

The reduction result type.

fn reduce_to(&self) -> Self::Result

Reduce this problem to the target problem type.

impl ReduceTo<KColoring<KN, SimpleGraph>> for KColoring<K3, SimpleGraph>

type Result = ReductionAutoCast<KColoring<K3, SimpleGraph>, KColoring<KN, SimpleGraph>>

The reduction result type.

fn reduce_to(&self) -> Self::Result

Reduce this problem to the target problem type.

impl ReduceTo<QUBO> for KColoring<K2, SimpleGraph>

type Result = ReductionKColoringToQUBO<K2>

The reduction result type.

fn reduce_to(&self) -> Self::Result

Reduce this problem to the target problem type.

impl ReduceTo<QUBO> for KColoring<K3, SimpleGraph>

type Result = ReductionKColoringToQUBO<K3>

The reduction result type.

fn reduce_to(&self) -> Self::Result

Reduce this problem to the target problem type.

impl ReduceTo<QUBO> for KColoring<KN, SimpleGraph>

type Result = ReductionKColoringToQUBO<KN>

The reduction result type.

fn reduce_to(&self) -> Self::Result

Reduce this problem to the target problem type.

impl<K: KValue, G> Serialize for KColoring<K, G>

where G: Serialize,

fn serialize<__S>(&self, __serializer: __S) -> Result<__S::Ok, __S::Error>

where __S: Serializer,

Serialize this value into the given Serde serializer.

impl DeclaredVariant for KColoring<K2, SimpleGraph>

impl DeclaredVariant for KColoring<K3, SimpleGraph>

impl DeclaredVariant for KColoring<K4, SimpleGraph>

impl DeclaredVariant for KColoring<K5, SimpleGraph>

impl DeclaredVariant for KColoring<KN, SimpleGraph>

impl<K: KValue, G: Graph + VariantParam> SatisfactionProblem for KColoring<K, G>