Struct MaximumIndependentSet 

pub struct MaximumIndependentSet<G, W> { /* private fields */ }

The Independent Set problem.

Given a graph G = (V, E) and weights w_v for each vertex, find a subset S ⊆ V such that:

• No two vertices in S are adjacent (independent set constraint)
• The total weight Σ_{v ∈ S} w_v is maximized

Type Parameters

• G - The graph type (e.g., SimpleGraph, KingsSubgraph, UnitDiskGraph)
• W - The weight type (e.g., i32, f64, One)

Example

use problemreductions::models::graph::MaximumIndependentSet;
use problemreductions::topology::SimpleGraph;
use problemreductions::{Problem, Solver, BruteForce};

// Create a triangle graph (3 vertices, 3 edges)
let graph = SimpleGraph::new(3, vec![(0, 1), (1, 2), (0, 2)]);
let problem = MaximumIndependentSet::new(graph, vec![1; 3]);

// Solve with brute force
let solver = BruteForce::new();
let solutions = solver.find_all_best(&problem);

// Maximum independent set in a triangle has size 1
assert!(solutions.iter().all(|s| s.iter().sum::<usize>() == 1));

Implementations

impl<G: Graph, W: Clone + Default> MaximumIndependentSet<G, W>

pub fn new(graph: G, weights: Vec<W>) -> Self

Create an Independent Set problem from a graph with given weights.

pub fn graph(&self) -> &G

Get a reference to the underlying graph.

pub fn weights(&self) -> &[W]

Get a reference to the weights.

pub fn is_weighted(&self) -> bool

where W: WeightElement,

Check if the problem uses a non-unit weight type.

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

Check if a configuration is a valid independent set.

impl<G: Graph, W: WeightElement> MaximumIndependentSet<G, W>

pub fn num_vertices(&self) -> usize

Get the number of vertices in the underlying graph.

pub fn num_edges(&self) -> usize

Get the number of edges in the underlying graph.

Trait Implementations

impl<G: Clone, W: Clone> Clone for MaximumIndependentSet<G, W>

fn clone(&self) -> MaximumIndependentSet<G, W>

Returns a duplicate of the value.

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

Performs copy-assignment from source.

impl<G: Debug, W: Debug> Debug for MaximumIndependentSet<G, W>

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

Formats the value using the given formatter.

impl<'de, G, W> Deserialize<'de> for MaximumIndependentSet<G, W>

where G: Deserialize<'de>, W: Deserialize<'de>,

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

where __D: Deserializer<'de>,

Deserialize this value from the given Serde deserializer.

impl<G, W> OptimizationProblem for MaximumIndependentSet<G, W>

where G: Graph + VariantParam, W: WeightElement + VariantParam,

type Value = <W as WeightElement>::Sum

The inner objective value type (e.g., i32, f64).

fn direction(&self) -> Direction

Whether to maximize or minimize the metric.

impl<G, W> Problem for MaximumIndependentSet<G, W>

where G: Graph + VariantParam, W: WeightElement + VariantParam,

const NAME: &'static str = "MaximumIndependentSet"

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

type Metric = SolutionSize<<W as WeightElement>::Sum>

The evaluation metric 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]) -> SolutionSize<W::Sum>

Evaluate the problem on a configuration.

fn num_variables(&self) -> usize

Number of variables (derived from dims).

impl ReduceTo<MaximumClique<SimpleGraph, i32>> for MaximumIndependentSet<SimpleGraph, i32>

type Result = ReductionISToClique<i32>

The reduction result type.

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

Reduce this problem to the target problem type.

impl ReduceTo<MaximumIndependentSet<KingsSubgraph, One>> for MaximumIndependentSet<SimpleGraph, One>

type Result = ReductionISSimpleOneToGridOne

The reduction result type.

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

Reduce this problem to the target problem type.

impl ReduceTo<MaximumIndependentSet<KingsSubgraph, i32>> for MaximumIndependentSet<KingsSubgraph, One>

type Result = ReductionAutoCast<MaximumIndependentSet<KingsSubgraph, One>, MaximumIndependentSet<KingsSubgraph, i32>>

The reduction result type.

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

Reduce this problem to the target problem type.

impl ReduceTo<MaximumIndependentSet<SimpleGraph, One>> for MaximumIndependentSet<UnitDiskGraph, One>

type Result = ReductionAutoCast<MaximumIndependentSet<UnitDiskGraph, One>, MaximumIndependentSet<SimpleGraph, One>>

The reduction result type.

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

Reduce this problem to the target problem type.

impl ReduceTo<MaximumIndependentSet<SimpleGraph, One>> for MaximumSetPacking<One>

type Result = ReductionSPToIS<One>

The reduction result type.

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

Reduce this problem to the target problem type.

impl ReduceTo<MaximumIndependentSet<SimpleGraph, One>> for Satisfiability

type Result = ReductionSATToIS

The reduction result type.

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

Reduce this problem to the target problem type.

impl ReduceTo<MaximumIndependentSet<SimpleGraph, i32>> for MaximumIndependentSet<SimpleGraph, One>

type Result = ReductionAutoCast<MaximumIndependentSet<SimpleGraph, One>, MaximumIndependentSet<SimpleGraph, i32>>

The reduction result type.

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

Reduce this problem to the target problem type.

impl ReduceTo<MaximumIndependentSet<SimpleGraph, i32>> for MaximumIndependentSet<UnitDiskGraph, i32>

type Result = ReductionAutoCast<MaximumIndependentSet<UnitDiskGraph, i32>, MaximumIndependentSet<SimpleGraph, i32>>

The reduction result type.

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

Reduce this problem to the target problem type.

impl ReduceTo<MaximumIndependentSet<SimpleGraph, i32>> for MaximumSetPacking<i32>

type Result = ReductionSPToIS<i32>

The reduction result type.

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

Reduce this problem to the target problem type.

impl ReduceTo<MaximumIndependentSet<SimpleGraph, i32>> for MinimumVertexCover<SimpleGraph, i32>

type Result = ReductionVCToIS<i32>

The reduction result type.

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

Reduce this problem to the target problem type.

impl ReduceTo<MaximumIndependentSet<TriangularSubgraph, i32>> for MaximumIndependentSet<SimpleGraph, One>

type Result = ReductionISSimpleToTriangular

The reduction result type.

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

Reduce this problem to the target problem type.

impl ReduceTo<MaximumIndependentSet<UnitDiskGraph, One>> for MaximumIndependentSet<KingsSubgraph, One>

type Result = ReductionAutoCast<MaximumIndependentSet<KingsSubgraph, One>, MaximumIndependentSet<UnitDiskGraph, One>>

The reduction result type.

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

Reduce this problem to the target problem type.

impl ReduceTo<MaximumIndependentSet<UnitDiskGraph, i32>> for MaximumIndependentSet<KingsSubgraph, i32>

type Result = ReductionAutoCast<MaximumIndependentSet<KingsSubgraph, i32>, MaximumIndependentSet<UnitDiskGraph, i32>>

The reduction result type.

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

Reduce this problem to the target problem type.

impl ReduceTo<MaximumIndependentSet<UnitDiskGraph, i32>> for MaximumIndependentSet<TriangularSubgraph, i32>

type Result = ReductionAutoCast<MaximumIndependentSet<TriangularSubgraph, i32>, MaximumIndependentSet<UnitDiskGraph, i32>>

The reduction result type.

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

Reduce this problem to the target problem type.

impl ReduceTo<MaximumIndependentSet<UnitDiskGraph, i32>> for MaximumIndependentSet<UnitDiskGraph, One>

type Result = ReductionAutoCast<MaximumIndependentSet<UnitDiskGraph, One>, MaximumIndependentSet<UnitDiskGraph, i32>>

The reduction result type.

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

Reduce this problem to the target problem type.

impl ReduceTo<MaximumSetPacking<One>> for MaximumIndependentSet<SimpleGraph, One>

type Result = ReductionISToSP<One>

The reduction result type.

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

Reduce this problem to the target problem type.

impl ReduceTo<MaximumSetPacking> for MaximumIndependentSet<SimpleGraph, i32>

type Result = ReductionISToSP<i32>

The reduction result type.

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

Reduce this problem to the target problem type.

impl ReduceTo<MinimumVertexCover<SimpleGraph, i32>> for MaximumIndependentSet<SimpleGraph, i32>

type Result = ReductionISToVC<i32>

The reduction result type.

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

Reduce this problem to the target problem type.

impl<G, W> Serialize for MaximumIndependentSet<G, W>

where G: Serialize, W: Serialize,

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 MaximumIndependentSet<KingsSubgraph, One>

impl DeclaredVariant for MaximumIndependentSet<KingsSubgraph, i32>

impl DeclaredVariant for MaximumIndependentSet<SimpleGraph, One>

impl DeclaredVariant for MaximumIndependentSet<SimpleGraph, i32>

impl DeclaredVariant for MaximumIndependentSet<TriangularSubgraph, i32>

impl DeclaredVariant for MaximumIndependentSet<UnitDiskGraph, One>

impl DeclaredVariant for MaximumIndependentSet<UnitDiskGraph, i32>