Struct GraphProblem 

pub struct GraphProblem<C: GraphConstraint, G: Graph = SimpleGraph, W = i32> { /* private fields */ }

A generic graph problem parameterized by constraint type, graph type, and weight type.

This struct provides a standard implementation for binary graph problems where:

• Each vertex can be either selected (1) or not selected (0)
• Edges impose constraints on which pairs of vertices can be simultaneously selected
• The objective is to maximize or minimize the total weight of selected vertices

Type Parameters

• C: The constraint type implementing GraphConstraint
• G: The graph type implementing Graph (default: SimpleGraph)
• W: The weight type (default: i32)

Example

use problemreductions::topology::{SimpleGraph, UnitDiskGraph};

// Define Independent Set as a type alias (defaults to SimpleGraph)
pub type IndependentSet<G = SimpleGraph, W = i32> = GraphProblem<IndependentSetConstraint, G, W>;

// Create an instance with SimpleGraph (default)
let problem = IndependentSet::new(4, vec![(0, 1), (1, 2), (2, 3)]);

// Create an instance with UnitDiskGraph for quantum hardware
let udg = UnitDiskGraph::new(vec![(0.0, 0.0), (1.0, 0.0), (2.0, 0.0)], 1.5);
let problem_udg = IndependentSet::<UnitDiskGraph>::from_graph(udg);

Implementations

impl<C: GraphConstraint, W: Clone + Default> GraphProblem<C, SimpleGraph, W>

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

where W: From<i32>,

Create a new graph problem with unit weights using SimpleGraph.

Arguments

• num_vertices - Number of vertices in the graph
• edges - List of edges as (u, v) pairs

pub fn with_weights( num_vertices: usize, edges: Vec<(usize, usize)>, weights: Vec<W>, ) -> Self

Create a new graph problem with custom weights using SimpleGraph.

Arguments

• num_vertices - Number of vertices in the graph
• edges - List of edges as (u, v) pairs
• weights - Weight for each vertex

Panics

Panics if weights.len() != num_vertices.

impl<C: GraphConstraint, G: Graph, W: Clone + Default> GraphProblem<C, G, W>

pub fn from_graph(graph: G) -> Self

where W: From<i32>,

Create a graph problem from an existing graph with unit weights.

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

Create a graph problem from an existing graph with custom weights.

Panics

Panics if weights.len() != graph.num_vertices().

pub fn graph(&self) -> &G

Get a reference to the underlying graph.

pub fn num_vertices(&self) -> usize

Get the number of vertices.

pub fn num_edges(&self) -> usize

Get the number of edges.

pub fn edges(&self) -> Vec<(usize, usize)>

Get the edges as a list of (u, v) pairs.

pub fn has_edge(&self, u: usize, v: usize) -> bool

Check if two vertices are adjacent.

Trait Implementations

impl<C: Clone + GraphConstraint, G: Clone + Graph, W: Clone> Clone for GraphProblem<C, G, W>

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

Returns a duplicate of the value.

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

Performs copy-assignment from source.

impl<C, G, W> ConstraintSatisfactionProblem for GraphProblem<C, G, W>

where C: GraphConstraint, G: Graph, W: Clone + Default + PartialOrd + Num + Zero + AddAssign + 'static,

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<C: Debug + GraphConstraint, G: Debug + Graph, W: Debug> Debug for GraphProblem<C, G, W>

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

Formats the value using the given formatter.

impl<'de, C: GraphConstraint, G, W> Deserialize<'de> for GraphProblem<C, G, W>

where G: Deserialize<'de> + Graph, 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<C, G, W> Problem for GraphProblem<C, G, W>

where C: GraphConstraint, G: Graph, W: Clone + Default + PartialOrd + Num + Zero + AddAssign + 'static,

const NAME: &'static str = C::NAME

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

type GraphType = SimpleGraph

The graph type this problem operates on.

type Weight = W

The weight type for this problem.

type Size = W

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<C, G, W> ProblemMetadata for GraphProblem<C, G, W>

where C: GraphConstraint, G: Graph, W: Clone + Default,

fn problem_info() -> ProblemInfo

Returns the problem info for this problem type.

fn category() -> ProblemCategory

Returns the problem category.

impl<C: GraphConstraint, G, W> Serialize for GraphProblem<C, G, W>

where G: Serialize + Graph, W: Serialize,

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

where __S: Serializer,

Serialize this value into the given Serde serializer.