Struct MatroidIntersectionSolver 

pub struct MatroidIntersectionSolver {
    pub ground_set_size: usize,
    pub block_assignment_1: Vec<usize>,
    pub rank_bounds_1: Vec<usize>,
    pub block_assignment_2: Vec<usize>,
    pub rank_bounds_2: Vec<usize>,
}

Solves the matroid intersection problem for two partition matroids.

A partition matroid is defined by a partition of the ground set E into blocks B_1, …, B_k, with rank bounds r_1, …, r_k.

Fields

ground_set_size: usize

Ground set size |E|.

block_assignment_1: Vec<usize>

Block assignments: block[i] = block index for element i.

rank_bounds_1: Vec<usize>

Rank bounds for matroid 1 (indexed by block).

block_assignment_2: Vec<usize>

Block assignments for matroid 2.

rank_bounds_2: Vec<usize>

Rank bounds for matroid 2.

Implementations

impl MatroidIntersectionSolver

pub fn new( n: usize, block_assignment_1: Vec<usize>, rank_bounds_1: Vec<usize>, block_assignment_2: Vec<usize>, rank_bounds_2: Vec<usize>, ) -> Self

Create a new solver for two partition matroids on ground set {0..n-1}.

pub fn is_independent_1(&self, mask: u64) -> bool

Check if a set (represented as a bitmask) is independent in matroid 1.

pub fn is_independent_2(&self, mask: u64) -> bool

Check if a set is independent in matroid 2.

pub fn solve_brute_force(&self) -> (usize, u64)

Find the maximum common independent set by brute force (for small |E|).

Returns (max_size, mask) where mask encodes the optimal set.

Trait Implementations

impl Clone for MatroidIntersectionSolver

fn clone(&self) -> MatroidIntersectionSolver

Returns a duplicate of the value.

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

Performs copy-assignment from source.

impl Debug for MatroidIntersectionSolver

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

Formats the value using the given formatter.