Struct MinimumCutIntoBoundedSets 

pub struct MinimumCutIntoBoundedSets<G, W: WeightElement> { /* private fields */ }

Minimum Cut Into Bounded Sets (Garey & Johnson ND17).

Given a weighted graph G = (V, E), source vertex s, sink vertex t, and size bound B, find a partition of V into disjoint sets V1 and V2 such that:

• s is in V1, t is in V2
• |V1| <= B, |V2| <= B
• The total weight of edges crossing the partition is minimized

Type Parameters

• G - The graph type (e.g., SimpleGraph)
• W - The weight type for edges (e.g., i32)

Example

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

// Simple 4-vertex path graph with unit weights, s=0, t=3
let graph = SimpleGraph::new(4, vec![(0, 1), (1, 2), (2, 3)]);
let problem = MinimumCutIntoBoundedSets::new(graph, vec![1, 1, 1], 0, 3, 3);

// Partition {0,1} vs {2,3}: cut edge (1,2) with weight 1
let val = problem.evaluate(&[0, 0, 1, 1]);
assert_eq!(val, problemreductions::types::Min(Some(1)));

Implementations

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

pub fn new( graph: G, edge_weights: Vec<W>, source: usize, sink: usize, size_bound: usize, ) -> Self

Create a new MinimumCutIntoBoundedSets problem.

Arguments

• graph - The undirected graph
• edge_weights - Weights for each edge (must match graph.num_edges())
• source - Source vertex s (must be in V1)
• sink - Sink vertex t (must be in V2)
• size_bound - Maximum size B for each partition set

Panics

Panics if edge_weights length doesn’t match num_edges, if source == sink, or if source/sink are out of bounds.

pub fn graph(&self) -> &G

Get a reference to the underlying graph.

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

Get the edge weights.

pub fn source(&self) -> usize

Get the source vertex.

pub fn sink(&self) -> usize

Get the sink vertex.

pub fn size_bound(&self) -> usize

Get the size bound B.

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 + WeightElement> Clone for MinimumCutIntoBoundedSets<G, W>

fn clone(&self) -> MinimumCutIntoBoundedSets<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 + WeightElement> Debug for MinimumCutIntoBoundedSets<G, W>

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

Formats the value using the given formatter.

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

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

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

where __D: Deserializer<'de>,

Deserialize this value from the given Serde deserializer.

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

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

const NAME: &'static str = "MinimumCutIntoBoundedSets"

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

type Value = Min<<W as WeightElement>::Sum>

The evaluation value 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]) -> Min<W::Sum>

Evaluate the problem on a configuration.

fn num_variables(&self) -> usize

Number of variables (derived from dims).

fn problem_type() -> ProblemType

Look up this problem’s catalog entry.

impl ReduceTo<ILP> for MinimumCutIntoBoundedSets<SimpleGraph, i32>

type Result = ReductionMinCutBSToILP

The reduction result type.

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

Reduce this problem to the target problem type.

impl ReduceTo<MinimumCutIntoBoundedSets<SimpleGraph, i32>> for MaxCut<SimpleGraph, i32>

type Result = ReductionMaxCutToMinCutBounded

The reduction result type.

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

Reduce this problem to the target problem type.

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

where G: Serialize, W: Serialize + WeightElement,

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 MinimumCutIntoBoundedSets<SimpleGraph, i32>