problemreductions/models/graph/
spin_glass.rs

1//! Spin Glass (Ising model) problem implementation.
2//!
3//! The Spin Glass problem minimizes the Ising Hamiltonian energy.
4
5use crate::registry::{FieldInfo, ProblemSchemaEntry};
6use crate::topology::{Graph, SimpleGraph};
7use crate::traits::{OptimizationProblem, Problem};
8use crate::types::{Direction, SolutionSize, WeightElement};
9use serde::{Deserialize, Serialize};
10
11inventory::submit! {
12    ProblemSchemaEntry {
13        name: "SpinGlass",
14        module_path: module_path!(),
15        description: "Minimize Ising Hamiltonian on a graph",
16        fields: &[
17            FieldInfo { name: "graph", type_name: "G", description: "The interaction graph" },
18            FieldInfo { name: "couplings", type_name: "Vec<W>", description: "Pairwise couplings J_ij" },
19            FieldInfo { name: "fields", type_name: "Vec<W>", description: "On-site fields h_i" },
20        ],
21    }
22}
23
24/// The Spin Glass (Ising model) problem.
25///
26/// Given n spin variables s_i in {-1, +1}, interaction coefficients J_ij,
27/// and on-site fields h_i, minimize the Hamiltonian:
28///
29/// H(s) = sum_{i<j} J_ij * s_i * s_j + sum_i h_i * s_i
30///
31/// # Representation
32///
33/// Variables are binary (0 or 1), mapped to spins via: s = 2*x - 1
34/// - x = 0 -> s = -1
35/// - x = 1 -> s = +1
36///
37/// # Type Parameters
38///
39/// * `G` - The graph type (e.g., `SimpleGraph`, `KingsSubgraph`, `UnitDiskGraph`)
40/// * `W` - The weight type for couplings (e.g., `i32`, `f64`)
41///
42/// # Example
43///
44/// ```
45/// use problemreductions::models::graph::SpinGlass;
46/// use problemreductions::topology::SimpleGraph;
47/// use problemreductions::{Problem, Solver, BruteForce};
48///
49/// // Two spins with antiferromagnetic coupling J_01 = 1
50/// let problem = SpinGlass::<SimpleGraph, f64>::new(2, vec![((0, 1), 1.0)], vec![0.0, 0.0]);
51///
52/// let solver = BruteForce::new();
53/// let solutions = solver.find_all_best(&problem);
54///
55/// // Ground state has opposite spins
56/// for sol in &solutions {
57///     assert!(sol[0] != sol[1]); // Antiferromagnetic: opposite spins
58/// }
59/// ```
60#[derive(Debug, Clone, Serialize, Deserialize)]
61pub struct SpinGlass<G, W> {
62    /// The underlying graph structure.
63    graph: G,
64    /// Coupling terms J_ij, one per edge in graph.edges() order.
65    couplings: Vec<W>,
66    /// On-site fields h_i.
67    fields: Vec<W>,
68}
69
70impl<W: Clone + Default> SpinGlass<SimpleGraph, W> {
71    /// Create a new Spin Glass problem.
72    ///
73    /// # Arguments
74    /// * `num_spins` - Number of spin variables
75    /// * `interactions` - Coupling terms J_ij as ((i, j), value)
76    /// * `fields` - On-site fields h_i
77    pub fn new(num_spins: usize, interactions: Vec<((usize, usize), W)>, fields: Vec<W>) -> Self {
78        assert_eq!(fields.len(), num_spins);
79        let edges: Vec<_> = interactions.iter().map(|((i, j), _)| (*i, *j)).collect();
80        let couplings: Vec<_> = interactions.iter().map(|(_, w)| w.clone()).collect();
81        let graph = SimpleGraph::new(num_spins, edges);
82        Self {
83            graph,
84            couplings,
85            fields,
86        }
87    }
88
89    /// Create a Spin Glass with no on-site fields.
90    pub fn without_fields(num_spins: usize, interactions: Vec<((usize, usize), W)>) -> Self
91    where
92        W: num_traits::Zero,
93    {
94        let fields = vec![W::zero(); num_spins];
95        Self::new(num_spins, interactions, fields)
96    }
97}
98
99impl<G: Graph, W: Clone + Default> SpinGlass<G, W> {
100    /// Create a SpinGlass problem from a graph with specified couplings.
101    ///
102    /// # Arguments
103    /// * `graph` - The underlying graph
104    /// * `couplings` - Coupling terms (must match graph.num_edges())
105    /// * `fields` - On-site fields h_i
106    pub fn from_graph(graph: G, couplings: Vec<W>, fields: Vec<W>) -> Self {
107        assert_eq!(
108            couplings.len(),
109            graph.num_edges(),
110            "couplings length must match num_edges"
111        );
112        assert_eq!(
113            fields.len(),
114            graph.num_vertices(),
115            "fields length must match num_vertices"
116        );
117        Self {
118            graph,
119            couplings,
120            fields,
121        }
122    }
123
124    /// Create a SpinGlass problem from a graph with no on-site fields.
125    pub fn from_graph_without_fields(graph: G, couplings: Vec<W>) -> Self
126    where
127        W: num_traits::Zero,
128    {
129        let fields = vec![W::zero(); graph.num_vertices()];
130        Self::from_graph(graph, couplings, fields)
131    }
132
133    /// Get a reference to the underlying graph.
134    pub fn graph(&self) -> &G {
135        &self.graph
136    }
137
138    /// Get the number of spins.
139    pub fn num_spins(&self) -> usize {
140        self.graph.num_vertices()
141    }
142
143    /// Get the number of interactions (edges in the interaction graph).
144    pub fn num_interactions(&self) -> usize {
145        self.graph.num_edges()
146    }
147
148    /// Get the interactions as ((i, j), weight) pairs.
149    ///
150    /// Reconstructs from graph.edges() and couplings.
151    pub fn interactions(&self) -> Vec<((usize, usize), W)> {
152        self.graph
153            .edges()
154            .into_iter()
155            .zip(self.couplings.iter())
156            .map(|((i, j), w)| ((i, j), w.clone()))
157            .collect()
158    }
159
160    /// Get the couplings (J_ij values).
161    pub fn couplings(&self) -> &[W] {
162        &self.couplings
163    }
164
165    /// Get the on-site fields.
166    pub fn fields(&self) -> &[W] {
167        &self.fields
168    }
169
170    /// Convert binary config (0,1) to spin config (-1,+1).
171    pub fn config_to_spins(config: &[usize]) -> Vec<i32> {
172        config.iter().map(|&x| 2 * x as i32 - 1).collect()
173    }
174}
175
176impl<G, W> SpinGlass<G, W>
177where
178    G: Graph,
179    W: Clone + num_traits::Zero + std::ops::AddAssign + std::ops::Mul<Output = W> + From<i32>,
180{
181    /// Compute the Hamiltonian energy for a spin configuration.
182    pub fn compute_energy(&self, spins: &[i32]) -> W {
183        let mut energy = W::zero();
184
185        // Interaction terms: sum J_ij * s_i * s_j
186        for ((i, j), j_val) in self.graph.edges().iter().zip(self.couplings.iter()) {
187            let s_i = spins.get(*i).copied().unwrap_or(1);
188            let s_j = spins.get(*j).copied().unwrap_or(1);
189            let product: i32 = s_i * s_j;
190            energy += j_val.clone() * W::from(product);
191        }
192
193        // On-site terms: sum h_i * s_i
194        for (i, h_val) in self.fields.iter().enumerate() {
195            let s_i = spins.get(i).copied().unwrap_or(1);
196            energy += h_val.clone() * W::from(s_i);
197        }
198
199        energy
200    }
201}
202
203impl<G, W> Problem for SpinGlass<G, W>
204where
205    G: Graph + crate::variant::VariantParam,
206    W: WeightElement
207        + crate::variant::VariantParam
208        + PartialOrd
209        + num_traits::Num
210        + num_traits::Zero
211        + num_traits::Bounded
212        + std::ops::AddAssign
213        + std::ops::Mul<Output = W>
214        + From<i32>,
215{
216    const NAME: &'static str = "SpinGlass";
217    type Metric = SolutionSize<W::Sum>;
218
219    fn dims(&self) -> Vec<usize> {
220        vec![2; self.graph.num_vertices()]
221    }
222
223    fn evaluate(&self, config: &[usize]) -> SolutionSize<W::Sum> {
224        let spins = Self::config_to_spins(config);
225        SolutionSize::Valid(self.compute_energy(&spins).to_sum())
226    }
227
228    fn variant() -> Vec<(&'static str, &'static str)> {
229        crate::variant_params![G, W]
230    }
231}
232
233impl<G, W> OptimizationProblem for SpinGlass<G, W>
234where
235    G: Graph + crate::variant::VariantParam,
236    W: WeightElement
237        + crate::variant::VariantParam
238        + PartialOrd
239        + num_traits::Num
240        + num_traits::Zero
241        + num_traits::Bounded
242        + std::ops::AddAssign
243        + std::ops::Mul<Output = W>
244        + From<i32>,
245{
246    type Value = W::Sum;
247
248    fn direction(&self) -> Direction {
249        Direction::Minimize
250    }
251}
252
253crate::declare_variants! {
254    SpinGlass<SimpleGraph, i32> => "2^num_spins",
255    SpinGlass<SimpleGraph, f64> => "2^num_spins",
256}
257
258#[cfg(test)]
259#[path = "../../unit_tests/models/graph/spin_glass.rs"]
260mod tests;
problemreductions/models/graph/spin_glass.rs

problemreductions/models/graph/
spin_glass.rs
