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

csp_solver/
adjacency.rs
