Struct RegisterSufficiency 

pub struct RegisterSufficiency { /* private fields */ }

The Register Sufficiency problem.

Given a directed acyclic graph G = (V, A) where arcs represent data dependencies, and a positive integer K, determine whether there is an evaluation ordering of all vertices such that at most K registers are needed at any point during the computation.

Representation

An arc (v, u) means vertex v depends on vertex u (i.e., u must be in a register when v is evaluated). Each variable represents a vertex, with domain {0, ..., n-1} giving its evaluation position (the config must be a valid permutation).

Example

use problemreductions::models::misc::RegisterSufficiency;
use problemreductions::{Problem, Solver, BruteForce};

// 4 vertices: v2 depends on v0, v3 depends on v0 and v1
let problem = RegisterSufficiency::new(
    4,
    vec![(2, 0), (3, 0), (3, 1)],
    2,
);
let solver = BruteForce::new();
let solution = solver.find_witness(&problem);
assert!(solution.is_some());

Implementations

impl RegisterSufficiency

pub fn new(num_vertices: usize, arcs: Vec<(usize, usize)>, bound: usize) -> Self

Create a new Register Sufficiency instance.

Panics

Panics if any arc index is out of bounds (>= num_vertices), or if any arc is a self-loop.

pub fn num_vertices(&self) -> usize

Get the number of vertices.

pub fn num_arcs(&self) -> usize

Get the number of arcs.

pub fn num_sinks(&self) -> usize

Count vertices with no dependents.

pub fn bound(&self) -> usize

Get the register bound K.

pub fn arcs(&self) -> &[(usize, usize)]

Get the arcs.

pub fn simulate_registers(&self, config: &[usize]) -> Option<usize>

Simulate register usage for a given evaluation ordering and return the maximum number of registers used, or None if the ordering is invalid (not a permutation or violates dependencies).

pub fn solve_exact(&self) -> Option<Vec<usize>>

Exact branch-and-bound solver: finds a topological ordering using at most self.bound registers, or returns None if no such ordering exists. Uses heuristic candidate ordering (prefer vertices that free the most registers) so that YES instances typically resolve on the first greedy path without backtracking. For NO instances the full search tree must be explored, so prefer the ILP solver path for infeasibility proofs.

NOTE: a greedy topological sort is not exact — it can miss valid orderings. This method is exact because it backtracks when the greedy choice fails. Do not replace it with a pure greedy solver.

Trait Implementations

impl Clone for RegisterSufficiency

fn clone(&self) -> RegisterSufficiency

Returns a duplicate of the value.

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

Performs copy-assignment from source.

impl Debug for RegisterSufficiency

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

Formats the value using the given formatter.

impl<'de> Deserialize<'de> for RegisterSufficiency

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

where __D: Deserializer<'de>,

Deserialize this value from the given Serde deserializer.

impl Problem for RegisterSufficiency

const NAME: &'static str = "RegisterSufficiency"

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

type Value = Or

The evaluation value 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]) -> Or

Evaluate the problem on a configuration.

fn num_variables(&self) -> usize

Number of variables (derived from dims).

fn problem_type() -> ProblemType

Look up this problem’s catalog entry.

impl ReduceTo<ILP<i32>> for RegisterSufficiency

type Result = ReductionRegisterSufficiencyToILP

The reduction result type.

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

Reduce this problem to the target problem type.

impl ReduceTo<RegisterSufficiency> for KSatisfiability<K3>

type Result = Reduction3SATToRegisterSufficiency

The reduction result type.

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

Reduce this problem to the target problem type.

impl Serialize for RegisterSufficiency

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 RegisterSufficiency