Struct MaximalIS 

pub struct MaximalIS { /* private fields */ }

The Maximal Independent Set problem.

Given a graph G = (V, E), find an independent set S that is maximal, meaning no vertex can be added to S while keeping it independent.

This is different from Maximum Independent Set - maximal means locally optimal (cannot extend), while maximum means globally optimal (largest).

Example

use problemreductions::models::graph::MaximalIS;
use problemreductions::{Problem, Solver, BruteForce};

// Path graph 0-1-2
let problem = MaximalIS::new(3, vec![(0, 1), (1, 2)]);

let solver = BruteForce::new();
let solutions = solver.find_best(&problem);

// Maximal independent sets: {0, 2} or {1}
for sol in &solutions {
    assert!(problem.solution_size(sol).is_valid);
}

Implementations

impl MaximalIS

pub fn new(num_vertices: usize, edges: Vec<(usize, usize)>) -> Self

Create a new Maximal Independent Set problem.

pub fn num_vertices(&self) -> usize

Get the number of vertices.

pub fn num_edges(&self) -> usize

Get the number of edges.

Trait Implementations

impl Clone for MaximalIS

fn clone(&self) -> MaximalIS

Returns a duplicate of the value.

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

Performs copy-assignment from source.

impl ConstraintSatisfactionProblem for MaximalIS

fn constraints(&self) -> Vec<LocalConstraint>

Returns the hard constraints that must be satisfied.

fn objectives(&self) -> Vec<LocalSolutionSize<Self::Size>>

Returns the local objectives that contribute to solution size.

fn weights(&self) -> Vec<Self::Size>

Returns the weights for the problem (e.g., vertex weights).

fn set_weights(&mut self, _weights: Vec<Self::Size>)

Set new weights for the problem.

fn is_weighted(&self) -> bool

Returns whether the problem has non-uniform weights.

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

Check if all constraints are satisfied by a configuration.

fn compute_objective(&self, config: &[usize]) -> Self::Size

Compute the total objective value from all local objectives.

impl Debug for MaximalIS

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

Formats the value using the given formatter.

impl<'de> Deserialize<'de> for MaximalIS

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

where __D: Deserializer<'de>,

Deserialize this value from the given Serde deserializer.

impl Problem for MaximalIS

const NAME: &'static str = "MaximalIS"

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

type GraphType = SimpleGraph

The graph type this problem operates on.

type Weight = i32

The weight type for this problem.

type Size = i32

The type used for objective/size values.

fn num_variables(&self) -> usize

Returns the number of variables in the problem.

fn num_flavors(&self) -> usize

Returns the number of possible values (flavors) for each variable. For binary problems, this is 2.

fn problem_size(&self) -> ProblemSize

Returns metadata about the problem size.

fn energy_mode(&self) -> EnergyMode

Returns whether larger or smaller objective values are better.

fn solution_size(&self, config: &[usize]) -> SolutionSize<Self::Size>

Evaluate the solution size for a given configuration.

fn variables(&self) -> Range<usize>

Returns the range of variable indices.

fn flavors(&self) -> Vec<usize>

Returns the possible flavors as a vector.

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

Check if a configuration is valid for this problem.

fn solution_size_multiple( &self, configs: &[Vec<usize>], ) -> Vec<SolutionSize<Self::Size>>

Evaluate multiple configurations at once (batch evaluation).

impl Serialize for MaximalIS

fn serialize<__S>(&self, __serializer: __S) -> Result<__S::Ok, __S::Error>

where __S: Serializer,

Serialize this value into the given Serde serializer.