Struct MinimumCodeGenerationParallelAssignments 

pub struct MinimumCodeGenerationParallelAssignments { /* private fields */ }

The Minimum Code Generation for Parallel Assignments problem.

Given a set V of variables and a collection of assignments A_i: “v_i <- op(B_i)” where v_i is the target variable and B_i is the set of variables read, find a permutation of the assignments that minimizes the number of backward dependencies. A backward dependency occurs when assignment pi(i) writes variable v and assignment pi(j) (j > i) reads v.

Example

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

// 4 variables, 4 assignments:
// A_0: a <- op(b, c)   -> (0, [1, 2])
// A_1: b <- op(a)      -> (1, [0])
// A_2: c <- op(d)      -> (2, [3])
// A_3: d <- op(b, c)   -> (3, [1, 2])
let assignments = vec![
    (0, vec![1, 2]),
    (1, vec![0]),
    (2, vec![3]),
    (3, vec![1, 2]),
];
let problem = MinimumCodeGenerationParallelAssignments::new(4, assignments);
let solver = BruteForce::new();
let solution = solver.find_witness(&problem);
assert!(solution.is_some());

Implementations

impl MinimumCodeGenerationParallelAssignments

pub fn new(num_variables: usize, assignments: Vec<(usize, Vec<usize>)>) -> Self

Create a new MinimumCodeGenerationParallelAssignments instance.

Panics

Panics if any target variable or read variable index is >= num_variables.

pub fn num_variables(&self) -> usize

Returns the number of variables.

pub fn num_assignments(&self) -> usize

Returns the number of assignments.

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

Returns the assignments.

Trait Implementations

impl Clone for MinimumCodeGenerationParallelAssignments

fn clone(&self) -> MinimumCodeGenerationParallelAssignments

Returns a duplicate of the value.

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

Performs copy-assignment from source.

impl Debug for MinimumCodeGenerationParallelAssignments

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

Formats the value using the given formatter.

impl<'de> Deserialize<'de> for MinimumCodeGenerationParallelAssignments

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

where __D: Deserializer<'de>,

Deserialize this value from the given Serde deserializer.

impl Problem for MinimumCodeGenerationParallelAssignments

const NAME: &'static str = "MinimumCodeGenerationParallelAssignments"

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

type Value = Min<usize>

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]) -> Min<usize>

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 Serialize for MinimumCodeGenerationParallelAssignments

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 MinimumCodeGenerationParallelAssignments