Struct MaxCut 

pub struct MaxCut<W = i32> { /* private fields */ }

The Maximum Cut problem.

Given a weighted graph G = (V, E) with edge weights w_e, find a partition of V into sets S and V\S such that the total weight of edges crossing the cut is maximized.

Representation

Each vertex is assigned a binary value:

• 0: vertex is in set S
• 1: vertex is in set V\S

An edge contributes to the cut if its endpoints are in different sets.

Example

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

// Create a triangle with unit weights
let problem = MaxCut::new(3, vec![(0, 1, 1), (1, 2, 1), (0, 2, 1)]);

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

// Maximum cut in triangle is 2 (any partition cuts 2 edges)
for sol in solutions {
    let size = problem.solution_size(&sol);
    assert_eq!(size.size, 2);
}

Implementations

impl<W: Clone + Default> MaxCut<W>

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

Create a new MaxCut problem.

Arguments

• num_vertices - Number of vertices
• edges - List of weighted edges as (u, v, weight) triples

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

where W: From<i32>,

Create a MaxCut problem with unit weights.

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, W)>

Get the edges with weights.

pub fn edge_weight(&self, u: usize, v: usize) -> Option<&W>

Get the weight of an edge.

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

Create a MaxCut problem from edges without weights in tuple form.

pub fn edge_weights(&self) -> Vec<W>

Get edge weights only.

Trait Implementations

impl<W: Clone> Clone for MaxCut<W>

fn clone(&self) -> MaxCut<W>

Returns a duplicate of the value.

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

Performs copy-assignment from source.

impl<W: Debug> Debug for MaxCut<W>

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

Formats the value using the given formatter.

impl<'de, W> Deserialize<'de> for MaxCut<W>

where 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<W> Problem for MaxCut<W>

where W: Clone + Default + PartialOrd + Num + Zero + AddAssign + 'static,

const NAME: &'static str = "MaxCut"

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<W> ReduceTo<MaxCut<W>> for SpinGlass<W>

where W: Clone + Default + PartialOrd + Num + Zero + AddAssign + From<i32> + 'static,

type Result = ReductionSGToMaxCut<W>

The reduction result type.

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

Reduce this problem to the target problem type.

impl<W> ReduceTo<SpinGlass<W>> for MaxCut<W>

where W: Clone + Default + PartialOrd + Num + Zero + AddAssign + From<i32> + 'static,

type Result = ReductionMaxCutToSG<W>

The reduction result type.

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

Reduce this problem to the target problem type.

impl<W> Serialize for MaxCut<W>

where W: Serialize,

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

where __S: Serializer,

Serialize this value into the given Serde serializer.