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

problemreductions/models/graph/
spin_glass.rs
