Struct IntegerExpressionMembership 

pub struct IntegerExpressionMembership { /* private fields */ }

The Integer Expression Membership problem.

Given an integer expression e over union (∪) and Minkowski sum (+) operations on singleton positive integers, and a target integer K, decide whether K ∈ eval(e).

Configuration

Each Union node has a binary variable (0 = left, 1 = right). A configuration assigns a branch choice to every Union node in DFS order. The expression then collapses to a chain of Sum and Atom nodes, evaluating to a single integer.

Example

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

// e = (1 ∪ 4) + (3 ∪ 6) + (2 ∪ 5), target K = 12
let expr = IntExpr::Sum(
    Box::new(IntExpr::Sum(
        Box::new(IntExpr::Union(
            Box::new(IntExpr::Atom(1)),
            Box::new(IntExpr::Atom(4)),
        )),
        Box::new(IntExpr::Union(
            Box::new(IntExpr::Atom(3)),
            Box::new(IntExpr::Atom(6)),
        )),
    )),
    Box::new(IntExpr::Union(
        Box::new(IntExpr::Atom(2)),
        Box::new(IntExpr::Atom(5)),
    )),
);
let problem = IntegerExpressionMembership::new(expr, 12);
let solver = BruteForce::new();
let solution = solver.find_witness(&problem);
assert!(solution.is_some());

Implementations

impl IntegerExpressionMembership

pub fn new(expression: IntExpr, target: u64) -> Self

Create a new IntegerExpressionMembership instance.

Arguments

• expression - The integer expression tree
• target - The target integer K

pub fn expression(&self) -> &IntExpr

Returns a reference to the expression tree.

pub fn target(&self) -> u64

Returns the target integer K.

pub fn expression_size(&self) -> usize

Returns the total number of nodes in the expression tree.

pub fn num_union_nodes(&self) -> usize

Returns the number of Union nodes in the expression tree.

pub fn num_atoms(&self) -> usize

Returns the number of Atom nodes in the expression tree.

pub fn expression_depth(&self) -> usize

Returns the depth of the expression tree.

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

Evaluate the expression for a given config and return the resulting integer.

Returns Some(value) if the config is valid, None otherwise.

Trait Implementations

impl Clone for IntegerExpressionMembership

fn clone(&self) -> IntegerExpressionMembership

Returns a duplicate of the value.

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

Performs copy-assignment from source.

impl Debug for IntegerExpressionMembership

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

Formats the value using the given formatter.

impl<'de> Deserialize<'de> for IntegerExpressionMembership

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

where __D: Deserializer<'de>,

Deserialize this value from the given Serde deserializer.

impl Problem for IntegerExpressionMembership

const NAME: &'static str = "IntegerExpressionMembership"

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

type Value = Or

The evaluation value type.

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 variant() -> Vec<(&'static str, &'static str)>

Returns variant attributes derived from type parameters.

fn num_variables(&self) -> usize

Number of variables (derived from dims).

fn problem_type() -> ProblemType

Look up this problem’s catalog entry.

impl ReduceTo<IntegerExpressionMembership> for SubsetSum

type Result = ReductionSubsetSumToIntegerExpressionMembership

The reduction result type.

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

Reduce this problem to the target problem type.

impl Serialize for IntegerExpressionMembership

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 IntegerExpressionMembership