Struct ConjunctiveBooleanQuery 

pub struct ConjunctiveBooleanQuery { /* private fields */ }

The Conjunctive Boolean Query problem.

Given a finite domain D = {0, ..., domain_size-1}, a collection of relations R, and a conjunctive Boolean query Q = (exists y_1, ..., y_l)(A_1 /\ ... /\ A_r), determine whether Q is true over R and D.

Representation

The configuration is a vector of length num_variables, where each entry is a value in {0, ..., domain_size-1} representing an assignment to the existentially quantified variables.

Example

use problemreductions::models::misc::{ConjunctiveBooleanQuery, CbqRelation, QueryArg};
use problemreductions::{Problem, Solver, BruteForce};

let relations = vec![
    CbqRelation { arity: 2, tuples: vec![vec![0, 3], vec![1, 3]] },
];
let conjuncts = vec![
    (0, vec![QueryArg::Variable(0), QueryArg::Constant(3)]),
];
let problem = ConjunctiveBooleanQuery::new(6, relations, 1, conjuncts);
let solver = BruteForce::new();
let solution = solver.find_witness(&problem);
assert!(solution.is_some());

Implementations

impl ConjunctiveBooleanQuery

pub fn new( domain_size: usize, relations: Vec<Relation>, num_variables: usize, conjuncts: Vec<(usize, Vec<QueryArg>)>, ) -> Self

Create a new ConjunctiveBooleanQuery instance.

Panics

Panics if:

• Any relation’s tuples have incorrect arity
• Any tuple entry is >= domain_size
• Any conjunct references a non-existent relation
• Any Variable(i) has i >= num_variables
• Any Constant(c) has c >= domain_size
• Any conjunct’s argument count does not match the referenced relation’s arity

pub fn domain_size(&self) -> usize

Returns the size of the finite domain.

pub fn num_relations(&self) -> usize

Returns the number of relations.

pub fn num_variables(&self) -> usize

Returns the number of existentially quantified variables.

pub fn num_conjuncts(&self) -> usize

Returns the number of conjuncts in the query.

pub fn relations(&self) -> &[Relation]

Returns the relations.

pub fn conjuncts(&self) -> &[(usize, Vec<QueryArg>)]

Returns the conjuncts.

Trait Implementations

impl Clone for ConjunctiveBooleanQuery

fn clone(&self) -> ConjunctiveBooleanQuery

Returns a duplicate of the value.

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

Performs copy-assignment from source.

impl Debug for ConjunctiveBooleanQuery

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

Formats the value using the given formatter.

impl<'de> Deserialize<'de> for ConjunctiveBooleanQuery

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

where __D: Deserializer<'de>,

Deserialize this value from the given Serde deserializer.

impl PartialEq for ConjunctiveBooleanQuery

fn eq(&self, other: &ConjunctiveBooleanQuery) -> bool

Tests for self and other values to be equal, and is used by ==.

fn ne(&self, other: &Rhs) -> bool

Tests for !=. The default implementation is almost always sufficient, and should not be overridden without very good reason.

impl Problem for ConjunctiveBooleanQuery

const NAME: &'static str = "ConjunctiveBooleanQuery"

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<ConjunctiveBooleanQuery> for KClique<SimpleGraph>

type Result = ReductionKCliqueToCBQ

The reduction result type.

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

Reduce this problem to the target problem type.

impl Serialize for ConjunctiveBooleanQuery

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 ConjunctiveBooleanQuery

impl StructuralPartialEq for ConjunctiveBooleanQuery