Struct MinimumWeightAndOrGraph 

pub struct MinimumWeightAndOrGraph { /* private fields */ }

The Minimum Weight AND/OR Graph problem.

Given a directed acyclic graph G = (V, A) where each non-leaf vertex is either an AND gate or an OR gate, a source vertex s, and arc weights w: A -> Z, find a solution subgraph of minimum total arc weight.

A solution subgraph is a subset of arcs S such that:

• The source vertex is “solved”
• For each solved AND-gate vertex v: all outgoing arcs from v are in S
• For each solved OR-gate vertex v: at least one outgoing arc from v is in S
• For each arc (u,v) in S: the target vertex v is also solved (recursively)
• Leaf vertices are trivially solved (no outgoing arcs needed)

The configuration space is binary over arcs: each arc is either selected (1) or not (0).

Example

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

// 7 vertices: AND at 0, OR at 1 and 2, leaves 3-6
let problem = MinimumWeightAndOrGraph::new(
    7,
    vec![(0,1), (0,2), (1,3), (1,4), (2,5), (2,6)],
    0,
    vec![Some(true), Some(false), Some(false), None, None, None, None],
    vec![1, 2, 3, 1, 4, 2],
);
let solver = BruteForce::new();
use problemreductions::solvers::Solver as _;
let optimal = solver.solve(&problem);
assert_eq!(optimal, problemreductions::types::Min(Some(6)));

Implementations

impl MinimumWeightAndOrGraph

pub fn new( num_vertices: usize, arcs: Vec<(usize, usize)>, source: usize, gate_types: Vec<Option<bool>>, arc_weights: Vec<i32>, ) -> Self

Create a new Minimum Weight AND/OR Graph instance.

Panics

Panics if any arc index is out of bounds, if the source is out of bounds, if gate_types length does not match num_vertices, if arc_weights length does not match the number of arcs, or if the source is a leaf.

pub fn num_vertices(&self) -> usize

Get the number of vertices.

pub fn num_arcs(&self) -> usize

Get the number of arcs.

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

Get the arcs.

pub fn source(&self) -> usize

Get the source vertex.

pub fn gate_types(&self) -> &[Option<bool>]

Get the gate types.

pub fn arc_weights(&self) -> &[i32]

Get the arc weights.

Trait Implementations

impl Clone for MinimumWeightAndOrGraph

fn clone(&self) -> MinimumWeightAndOrGraph

Returns a duplicate of the value.

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

Performs copy-assignment from source.

impl Debug for MinimumWeightAndOrGraph

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

Formats the value using the given formatter.

impl<'de> Deserialize<'de> for MinimumWeightAndOrGraph

fn deserialize<D>(deserializer: D) -> Result<Self, D::Error>

where D: Deserializer<'de>,

Deserialize this value from the given Serde deserializer.

impl Problem for MinimumWeightAndOrGraph

const NAME: &'static str = "MinimumWeightAndOrGraph"

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

type Value = Min<i32>

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<i32>

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<MinimumWeightAndOrGraph> for MinimumVertexCover<SimpleGraph, i32>

type Result = ReductionVCToAndOrGraph

The reduction result type.

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

Reduce this problem to the target problem type.

impl Serialize for MinimumWeightAndOrGraph

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 MinimumWeightAndOrGraph