csp_solver/
adjacency.rs

1//! Pre-built constraint dependency graph with flat arena storage.
2
3use crate::constraint::{ConstraintEnum, VarId};
4use crate::domain::Domain;
5
6#[derive(Debug, Clone)]
7struct ArenaIndex {
8    entries: Vec<(u32, u32)>,
9}
10
11impl ArenaIndex {
12    fn new(count: usize) -> Self {
13        Self { entries: vec![(0, 0); count] }
14    }
15
16    fn get<'a>(&self, idx: usize, pool: &'a [u32]) -> &'a [u32] {
17        let (offset, len) = self.entries[idx];
18        &pool[offset as usize..(offset + len) as usize]
19    }
20}
21
22#[derive(Debug, Clone)]
23pub struct Adjacency {
24    pool: Vec<u32>,
25    var_constraints: ArenaIndex,
26    constraint_neighbors: ArenaIndex,
27    var_neighbors: ArenaIndex,
28}
29
30impl Adjacency {
31    pub fn build<D: Domain>(num_vars: usize, constraints: &[ConstraintEnum<D>]) -> Self
32    where
33        D::Value: PartialEq,
34    {
35        let num_constraints = constraints.len();
36
37        let mut vc_lists: Vec<Vec<u32>> = vec![Vec::new(); num_vars];
38        for (ci, c) in constraints.iter().enumerate() {
39            for &v in c.scope() {
40                vc_lists[v as usize].push(ci as u32);
41            }
42        }
43
44        let mut cn_lists: Vec<Vec<u32>> = vec![Vec::new(); num_constraints];
45        for vc in &vc_lists {
46            for &ci in vc {
47                for &cj in vc {
48                    if ci != cj { cn_lists[ci as usize].push(cj); }
49                }
50            }
51        }
52        for neighbors in &mut cn_lists { neighbors.sort_unstable(); neighbors.dedup(); }
53
54        let mut vn_lists: Vec<Vec<u32>> = vec![Vec::new(); num_vars];
55        for c in constraints {
56            let scope = c.scope();
57            for &vi in scope {
58                for &vj in scope {
59                    if vi != vj { vn_lists[vi as usize].push(vj); }
60                }
61            }
62        }
63        for neighbors in &mut vn_lists { neighbors.sort_unstable(); neighbors.dedup(); }
64
65        let total_len: usize = vc_lists.iter().map(|v| v.len()).sum::<usize>()
66            + cn_lists.iter().map(|v| v.len()).sum::<usize>()
67            + vn_lists.iter().map(|v| v.len()).sum::<usize>();
68        let mut pool = Vec::with_capacity(total_len);
69
70        let mut var_constraints = ArenaIndex::new(num_vars);
71        for (i, list) in vc_lists.iter().enumerate() {
72            let offset = pool.len() as u32;
73            pool.extend_from_slice(list);
74            var_constraints.entries[i] = (offset, list.len() as u32);
75        }
76
77        let mut constraint_neighbors = ArenaIndex::new(num_constraints);
78        for (i, list) in cn_lists.iter().enumerate() {
79            let offset = pool.len() as u32;
80            pool.extend_from_slice(list);
81            constraint_neighbors.entries[i] = (offset, list.len() as u32);
82        }
83
84        let mut var_neighbors = ArenaIndex::new(num_vars);
85        for (i, list) in vn_lists.iter().enumerate() {
86            let offset = pool.len() as u32;
87            pool.extend_from_slice(list);
88            var_neighbors.entries[i] = (offset, list.len() as u32);
89        }
90
91        Self { pool, var_constraints, constraint_neighbors, var_neighbors }
92    }
93
94    pub fn constraints_for(&self, var: VarId) -> &[u32] {
95        self.var_constraints.get(var as usize, &self.pool)
96    }
97
98    pub fn neighbors_of_constraint(&self, ci: usize) -> &[u32] {
99        self.constraint_neighbors.get(ci, &self.pool)
100    }
101
102    pub fn neighbors_of_var(&self, var: VarId) -> &[u32] {
103        self.var_neighbors.get(var as usize, &self.pool)
104    }
105}
csp_solver/adjacency.rs

csp_solver/
adjacency.rs
