Struct SetSplitting 

pub struct SetSplitting { /* private fields */ }

The Set Splitting problem.

Given a finite universe $U = {0, \ldots, n-1}$ and a collection $\mathcal{C}$ of subsets of $U$, decide whether there exists a 2-coloring (partition into $S_1$ and $S_2$) of $U$ such that every subset in $\mathcal{C}$ is non-monochromatic, i.e., contains at least one element from each part.

Example

use problemreductions::models::set::SetSplitting;
use problemreductions::{Problem, Solver, BruteForce};

// Universe {0,1,2,3,4,5}, subsets that all must be split
let problem = SetSplitting::new(6, vec![
    vec![0, 1, 2],
    vec![2, 3, 4],
    vec![0, 4, 5],
    vec![1, 3, 5],
]);

let solver = BruteForce::new();
let witness = solver.find_witness(&problem);
assert!(witness.is_some());

Implementations

impl SetSplitting

pub fn new(universe_size: usize, subsets: Vec<Vec<usize>>) -> Self

Create a new Set Splitting problem.

Panics

Panics if any subset is empty, has fewer than 2 elements, or contains an element outside the universe.

pub fn try_new( universe_size: usize, subsets: Vec<Vec<usize>>, ) -> Result<Self, String>

Create a new Set Splitting problem, returning an error instead of panicking.

pub fn universe_size(&self) -> usize

Get the size of the universe.

pub fn num_subsets(&self) -> usize

Get the number of subsets.

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

Get the subsets.

pub fn normalized_universe_size(&self) -> usize

Universe size after decomposing all subsets to size 2 or 3.

pub fn normalized_num_size2_subsets(&self) -> usize

Number of size-2 subsets after decomposition.

pub fn normalized_num_size3_subsets(&self) -> usize

Number of size-3 subsets after decomposition.

pub fn is_valid_solution(&self, config: &[usize]) -> bool

Check if a coloring (config) splits all subsets.

Trait Implementations

impl Clone for SetSplitting

fn clone(&self) -> SetSplitting

Returns a duplicate of the value.

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

Performs copy-assignment from source.

impl Debug for SetSplitting

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

Formats the value using the given formatter.

impl<'de> Deserialize<'de> for SetSplitting

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

where __D: Deserializer<'de>,

Deserialize this value from the given Serde deserializer.

impl Problem for SetSplitting

const NAME: &'static str = "SetSplitting"

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<Betweenness> for SetSplitting

type Result = ReductionSetSplittingToBetweenness

The reduction result type.

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

Reduce this problem to the target problem type.

impl ReduceTo<ILP> for SetSplitting

type Result = ReductionSetSplittingToILP

The reduction result type.

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

Reduce this problem to the target problem type.

impl ReduceTo<SetSplitting> for NAESatisfiability

type Result = ReductionNAESATToSetSplitting

The reduction result type.

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

Reduce this problem to the target problem type.

impl Serialize for SetSplitting

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 SetSplitting