Design

This guide covers the library internals for contributors.

Module Overview

Problem Model

Every problem implements Problem. Optimization problems additionally implement OptimizationProblem; satisfaction problems implement SatisfactionProblem.

trait Problem: Clone {
    const NAME: &'static str;              // e.g., "MaximumIndependentSet"
    type Metric: Clone;                    // SolutionSize<W> or bool
    fn dims(&self) -> Vec<usize>;          // config space per variable
    fn evaluate(&self, config: &[usize]) -> Self::Metric;
    fn variant() -> Vec<(&'static str, &'static str)>; // e.g., [("graph", "SimpleGraph"), ("weight", "i32")]
    fn num_variables(&self) -> usize;      // default: dims().len()
    fn problem_size_names() -> &'static [&'static str]; // e.g., ["num_vertices", "num_edges"]
    fn problem_size_values(&self) -> Vec<usize>;       // e.g., [10, 15] for a specific instance
}

trait OptimizationProblem: Problem<Metric = SolutionSize<Self::Value>> {
    type Value: PartialOrd + Clone;        // e.g., i32, f64
    fn direction(&self) -> Direction;      // Maximize or Minimize
}

trait SatisfactionProblem: Problem<Metric = bool> {}  // marker trait

• Problem — the base trait. Every problem declares a NAME (e.g., "MaximumIndependentSet"). The solver explores the configuration space defined by dims() and scores each configuration with evaluate(). For example, a 4-vertex MIS has dims() = [2, 2, 2, 2] (each vertex is selected or not); evaluate(&[1, 0, 1, 0]) returns Valid(2) if vertices 0 and 2 form an independent set, or Invalid if they share an edge. problem_size_names() and problem_size_values() expose the instance's structural dimensions (e.g., num_vertices, num_edges) as a ProblemSize — used by the reduction graph to evaluate overhead polynomials along a path.
• OptimizationProblem — extends Problem with a comparable Value type and a direction() (Maximize or Minimize).
• SatisfactionProblem — constrains Metric = bool: true if all constraints are satisfied, false otherwise.

Variant System

A single problem name like MaximumIndependentSet can have multiple variants — carrying weights on vertices, or defined on a restricted topology (e.g., king's subgraph). Variants form a subtype hierarchy: independent sets on king's subgraphs are a subset of independent sets on unit-disk graphs. The reduction from a more specific variant to a less specific one is a variant cast — an identity mapping where indices are preserved.

Variant types fall into three categories:

• Graph type — HyperGraph (root), SimpleGraph, PlanarGraph, BipartiteGraph, UnitDiskGraph, KingsSubgraph, TriangularSubgraph.
• Weight type — One (unweighted), i32, f64.
• K value — e.g., K3 for 3-SAT, KN for arbitrary K.

pub trait VariantParam: 'static {
    const CATEGORY: &'static str;     // e.g., "graph", "weight", "k"
    const VALUE: &'static str;        // e.g., "SimpleGraph", "i32"
    const PARENT_VALUE: Option<&'static str>;  // None for root types
}

pub trait CastToParent: VariantParam {
    type Parent: VariantParam;
    fn cast_to_parent(&self) -> Self::Parent;
}

// Root type (no parent):
impl_variant_param!(HyperGraph, "graph");

// Type with parent (cast closure required):
impl_variant_param!(SimpleGraph, "graph", parent: HyperGraph,
    cast: |g| {
        let edges: Vec<Vec<usize>> = g.edges().into_iter().map(|(u, v)| vec![u, v]).collect();
        HyperGraph::new(g.num_vertices(), edges)
    });

// K root (arbitrary K):
impl_variant_param!(KN, "k", k: None);

// Specific K with parent:
impl_variant_param!(K3, "k", parent: KN, cast: |_| KN, k: Some(3));

impl_variant_reduction!(
    MaximumIndependentSet,
    <KingsSubgraph, i32> => <UnitDiskGraph, i32>,
    fields: [num_vertices, num_edges],
    |src| MaximumIndependentSet::new(
        src.graph().cast_to_parent(), src.weights().to_vec())
);

// MaximumIndependentSet<G: VariantParam, W: VariantParam>
fn variant() -> Vec<(&'static str, &'static str)> {
    crate::variant_params![G, W]
    // e.g., MaximumIndependentSet<UnitDiskGraph, One>
    //     -> vec![("graph", "UnitDiskGraph"), ("weight", "One")]
}

Reduction Rules

A reduction requires two pieces: a result struct and a ReduceTo<T> impl.

The result struct holds the target problem and the logic to map solutions back:

#[derive(Debug, Clone)]
pub struct ReductionISToVC<W> {
    target: MinimumVertexCover<SimpleGraph, W>,
}

impl<W: WeightElement + VariantParam> ReductionResult for ReductionISToVC<W> {
    type Source = MaximumIndependentSet<SimpleGraph, W>;
    type Target = MinimumVertexCover<SimpleGraph, W>;

    fn target_problem(&self) -> &Self::Target { &self.target }
    fn extract_solution(&self, target_sol: &[usize]) -> Vec<usize> {
        target_sol.iter().map(|&x| 1 - x).collect()  // complement
    }
}

The #[reduction] attribute on the ReduceTo<T> impl registers the reduction in the global registry (via inventory):

#[reduction(
    overhead = {
        ReductionOverhead::new(vec![
            ("num_vertices", poly!(num_vertices)),
            ("num_edges", poly!(num_edges)),
        ])
    }
)]
impl ReduceTo<MinimumVertexCover<SimpleGraph, i32>>
    for MaximumIndependentSet<SimpleGraph, i32>
{
    type Result = ReductionISToVC<i32>;
    fn reduce_to(&self) -> Self::Result { /* ... */ }
}

inventory::submit! {
    ReductionEntry {
        source_name: "MaximumIndependentSet",
        target_name: "MinimumVertexCover",
        source_variant_fn: || <MaximumIndependentSet<SimpleGraph, i32> as Problem>::variant(),
        target_variant_fn: || <MinimumVertexCover<SimpleGraph, i32> as Problem>::variant(),
        overhead_fn: || ReductionOverhead::new(vec![
            ("num_vertices", poly!(num_vertices)),
            ("num_edges", poly!(num_edges)),
        ]),
        module_path: module_path!(),
        reduce_fn: |src: &dyn Any| -> Box<dyn DynReductionResult> {
            let src = src.downcast_ref::<MaximumIndependentSet<SimpleGraph, i32>>().unwrap();
            Box::new(ReduceTo::<MinimumVertexCover<SimpleGraph, i32>>::reduce_to(src))
        },
    }
}

Reduction Graph

ReductionGraph::new() iterates all registered ReductionEntry items (via inventory) and builds a variant-level directed graph:

• Nodes are unique (problem_name, variant) pairs — e.g., ("MaximumIndependentSet", {graph: "KingsSubgraph", weight: "i32"}).
• Edges come exclusively from #[reduction] registrations — both cross-problem reductions and variant casts. There are no auto-generated edges.

Exported files:

• reduction_graph.json — all problem variants and reduction edges
• problem_schemas.json — field definitions for each problem type

Regenerate with cargo run --example export_graph and cargo run --example export_schemas.

Path finding

All path-finding operates on exact variant nodes. Use ReductionGraph::variant_to_map(&T::variant()) to convert a Problem::variant() into the required BTreeMap<String, String>.

Use find_cheapest_path with MinimizeSteps for fewest-hops search.

The PathCostFn trait (used by find_cheapest_path) computes edge cost from overhead and current problem size:

CustomCost wraps a closure that receives the edge's ReductionOverhead (polynomial mapping from input to output size fields) and the current ProblemSize (accumulated field values at that point in the path), and returns an f64 edge cost. Dijkstra minimizes the total cost along the path.

Example: Finding a path from MIS{KingsSubgraph, i32} to VC{SimpleGraph, i32}:

MIS{KingsSubgraph,i32} -> MIS{UnitDiskGraph,i32} -> MIS{SimpleGraph,i32} -> VC{SimpleGraph,i32}
     variant cast              variant cast                reduction

Executable paths

Convert a ReductionPath into a typed ExecutablePath<S, T> via make_executable(), then call reduce():

// find_cheapest_path returns a ReductionPath (list of variant node IDs)
let rpath = graph.find_cheapest_path("Factoring", &src_var,
    "SpinGlass", &dst_var, &ProblemSize::new(vec![]), &MinimizeSteps).unwrap();

// make_executable converts it into a typed, callable chain
let path = graph.make_executable::<Factoring, SpinGlass<SimpleGraph, f64>>(&rpath).unwrap();

// reduce() applies each step, returning a ChainedReduction
let reduction = path.reduce(&factoring_instance);
let target: &SpinGlass<SimpleGraph, f64> = reduction.target_problem();
let solution: Vec<usize> = reduction.extract_solution(&target_solution);

ExecutablePath holds a type-erased ReduceFn per edge. reduce() applies them sequentially, producing a ChainedReduction that stores each intermediate result. extract_solution maps the final solution back through the chain in reverse order.

For full type control, you can also chain ReduceTo::reduce_to() calls manually at each step.

poly!(num_vertices)              // p(x) = num_vertices
poly!(num_vertices ^ 2)          // p(x) = num_vertices²
poly!(3 * num_edges)             // p(x) = 3 × num_edges
poly!(num_vertices * num_edges)  // p(x) = num_vertices × num_edges

ReductionOverhead::new(vec![
    ("num_vars", poly!(num_vertices) + poly!(num_edges)),
    ("num_clauses", poly!(3 * num_edges)),
])

Input:  ProblemSize { num_vertices: 10, num_edges: 15 }
Output: ProblemSize { num_vars: 25, num_clauses: 45 }

Solvers

Solvers implement the Solver trait:

pub trait Solver {
    fn find_best<P: OptimizationProblem>(&self, problem: &P) -> Option<Vec<usize>>;
    fn find_satisfying<P: Problem<Metric = bool>>(&self, problem: &P) -> Option<Vec<usize>>;
}

JSON Serialization

All problem types support JSON serialization via serde:

use problemreductions::io::{to_json, from_json};

let json: String = to_json(&problem)?;
let restored: MaximumIndependentSet<SimpleGraph, i32> = from_json(&json)?;

Contributing

See Call for Contributions for the recommended issue-based workflow (no coding required).