solverforge_solver/phase/exhaustive/
node.rs

1//! Exhaustive search node representation.
2//!
3//! Each node represents a partial solution state in the search tree.
4
5use std::marker::PhantomData;
6
7use crate::heuristic::Move;
8use solverforge_core::domain::PlanningSolution;
9
10/// A node in the exhaustive search tree.
11///
12/// Each node represents a partial solution state, containing:
13/// - The depth in the search tree (number of variables assigned)
14/// - The score at this node
15/// - An optimistic bound (best possible score from this node)
16/// - The move sequence to reach this node from the root
17#[derive(Debug, Clone)]
18pub struct ExhaustiveSearchNode<S: PlanningSolution> {
19    /// Depth in the search tree (0 = root, number of assignments made).
20    depth: usize,
21
22    /// The score at this node after applying all moves.
23    score: S::Score,
24
25    /// Optimistic bound: best possible score achievable from this node.
26    /// Used for pruning branches that cannot improve on the best solution.
27    optimistic_bound: Option<S::Score>,
28
29    /// Index of the entity being assigned at this node.
30    entity_index: Option<usize>,
31
32    /// Index of the value assigned at this node.
33    value_index: Option<usize>,
34
35    /// Parent node index in the node list (None for root).
36    parent_index: Option<usize>,
37
38    /// Whether this node has been expanded.
39    expanded: bool,
40}
41
42impl<S: PlanningSolution> ExhaustiveSearchNode<S> {
43    /// Creates a new root node.
44    pub fn root(score: S::Score) -> Self {
45        Self {
46            depth: 0,
47            score,
48            optimistic_bound: None,
49            entity_index: None,
50            value_index: None,
51            parent_index: None,
52            expanded: false,
53        }
54    }
55
56    /// Creates a child node.
57    pub fn child(
58        parent_index: usize,
59        depth: usize,
60        score: S::Score,
61        entity_index: usize,
62        value_index: usize,
63    ) -> Self {
64        Self {
65            depth,
66            score,
67            optimistic_bound: None,
68            entity_index: Some(entity_index),
69            value_index: Some(value_index),
70            parent_index: Some(parent_index),
71            expanded: false,
72        }
73    }
74
75    /// Returns the depth of this node.
76    #[inline]
77    pub fn depth(&self) -> usize {
78        self.depth
79    }
80
81    /// Returns the score at this node.
82    #[inline]
83    pub fn score(&self) -> &S::Score {
84        &self.score
85    }
86
87    /// Sets the score at this node.
88    pub fn set_score(&mut self, score: S::Score) {
89        self.score = score;
90    }
91
92    /// Returns the optimistic bound for this node.
93    #[inline]
94    pub fn optimistic_bound(&self) -> Option<&S::Score> {
95        self.optimistic_bound.as_ref()
96    }
97
98    /// Sets the optimistic bound for this node.
99    pub fn set_optimistic_bound(&mut self, bound: S::Score) {
100        self.optimistic_bound = Some(bound);
101    }
102
103    /// Returns the entity index being assigned at this node.
104    #[inline]
105    pub fn entity_index(&self) -> Option<usize> {
106        self.entity_index
107    }
108
109    /// Returns the value index assigned at this node.
110    #[inline]
111    pub fn value_index(&self) -> Option<usize> {
112        self.value_index
113    }
114
115    /// Returns the parent node index.
116    #[inline]
117    pub fn parent_index(&self) -> Option<usize> {
118        self.parent_index
119    }
120
121    /// Returns whether this node has been expanded.
122    #[inline]
123    pub fn is_expanded(&self) -> bool {
124        self.expanded
125    }
126
127    /// Marks this node as expanded.
128    pub fn mark_expanded(&mut self) {
129        self.expanded = true;
130    }
131
132    /// Returns whether this node is a leaf (all entities assigned).
133    pub fn is_leaf(&self, total_entities: usize) -> bool {
134        self.depth >= total_entities
135    }
136
137    /// Checks if this node can be pruned based on the best score.
138    ///
139    /// A node can be pruned if its optimistic bound is worse than or equal
140    /// to the best score found so far.
141    pub fn can_prune(&self, best_score: &S::Score) -> bool {
142        match &self.optimistic_bound {
143            Some(bound) => bound <= best_score,
144            None => false,
145        }
146    }
147}
148
149/// Tracks the move sequence to reconstruct a solution path.
150///
151/// # Type Parameters
152/// * `S` - The planning solution type
153/// * `M` - The move type
154#[derive(Debug, Clone)]
155pub struct MoveSequence<S, M>
156where
157    S: PlanningSolution,
158    M: Move<S>,
159{
160    /// The sequence of moves from root to current node.
161    moves: Vec<M>,
162    _phantom: PhantomData<S>,
163}
164
165impl<S, M> MoveSequence<S, M>
166where
167    S: PlanningSolution,
168    M: Move<S>,
169{
170    /// Creates an empty move sequence.
171    pub fn new() -> Self {
172        Self {
173            moves: Vec::new(),
174            _phantom: PhantomData,
175        }
176    }
177
178    /// Creates a sequence with initial capacity.
179    pub fn with_capacity(capacity: usize) -> Self {
180        Self {
181            moves: Vec::with_capacity(capacity),
182            _phantom: PhantomData,
183        }
184    }
185
186    /// Adds a move to the sequence.
187    pub fn push(&mut self, m: M) {
188        self.moves.push(m);
189    }
190
191    /// Removes and returns the last move.
192    pub fn pop(&mut self) -> Option<M> {
193        self.moves.pop()
194    }
195
196    /// Returns the number of moves in the sequence.
197    pub fn len(&self) -> usize {
198        self.moves.len()
199    }
200
201    /// Returns whether the sequence is empty.
202    pub fn is_empty(&self) -> bool {
203        self.moves.is_empty()
204    }
205
206    /// Returns an iterator over the moves.
207    pub fn iter(&self) -> impl Iterator<Item = &M> {
208        self.moves.iter()
209    }
210
211    /// Clears all moves from the sequence.
212    pub fn clear(&mut self) {
213        self.moves.clear();
214    }
215}
216
217impl<S, M> Default for MoveSequence<S, M>
218where
219    S: PlanningSolution,
220    M: Move<S>,
221{
222    fn default() -> Self {
223        Self::new()
224    }
225}
226
227#[cfg(test)]
228mod tests {
229    use super::*;
230    use crate::heuristic::r#move::ChangeMove;
231    use solverforge_core::score::SimpleScore;
232
233    #[derive(Clone, Debug)]
234    struct TestSolution {
235        values: Vec<Option<i32>>,
236        score: Option<SimpleScore>,
237    }
238
239    impl PlanningSolution for TestSolution {
240        type Score = SimpleScore;
241
242        fn score(&self) -> Option<Self::Score> {
243            self.score
244        }
245
246        fn set_score(&mut self, score: Option<Self::Score>) {
247            self.score = score;
248        }
249    }
250
251    // Typed getter - zero erasure
252    fn get_value(s: &TestSolution, idx: usize) -> Option<i32> {
253        s.values.get(idx).copied().flatten()
254    }
255
256    // Typed setter - zero erasure
257    fn set_value(s: &mut TestSolution, idx: usize, v: Option<i32>) {
258        if let Some(val) = s.values.get_mut(idx) {
259            *val = v;
260        }
261    }
262
263    #[test]
264    fn test_root_node() {
265        let node: ExhaustiveSearchNode<TestSolution> =
266            ExhaustiveSearchNode::root(SimpleScore::of(0));
267
268        assert_eq!(node.depth(), 0);
269        assert_eq!(node.score(), &SimpleScore::of(0));
270        assert!(node.parent_index().is_none());
271        assert!(node.entity_index().is_none());
272        assert!(!node.is_expanded());
273    }
274
275    #[test]
276    fn test_child_node() {
277        let node: ExhaustiveSearchNode<TestSolution> =
278            ExhaustiveSearchNode::child(0, 1, SimpleScore::of(-1), 0, 2);
279
280        assert_eq!(node.depth(), 1);
281        assert_eq!(node.score(), &SimpleScore::of(-1));
282        assert_eq!(node.parent_index(), Some(0));
283        assert_eq!(node.entity_index(), Some(0));
284        assert_eq!(node.value_index(), Some(2));
285    }
286
287    #[test]
288    fn test_is_leaf() {
289        let node: ExhaustiveSearchNode<TestSolution> =
290            ExhaustiveSearchNode::child(0, 4, SimpleScore::of(0), 3, 1);
291
292        assert!(node.is_leaf(4));
293        assert!(!node.is_leaf(5));
294    }
295
296    #[test]
297    fn test_optimistic_bound_pruning() {
298        let mut node: ExhaustiveSearchNode<TestSolution> =
299            ExhaustiveSearchNode::root(SimpleScore::of(-5));
300
301        // No bound set - cannot prune
302        assert!(!node.can_prune(&SimpleScore::of(0)));
303
304        // Set bound worse than best - can prune
305        node.set_optimistic_bound(SimpleScore::of(-2));
306        assert!(node.can_prune(&SimpleScore::of(0)));
307
308        // Set bound better than best - cannot prune
309        node.set_optimistic_bound(SimpleScore::of(5));
310        assert!(!node.can_prune(&SimpleScore::of(0)));
311    }
312
313    type TestMove = ChangeMove<TestSolution, i32>;
314
315    #[test]
316    fn test_move_sequence() {
317        let mut seq: MoveSequence<TestSolution, TestMove> = MoveSequence::new();
318
319        assert!(seq.is_empty());
320        assert_eq!(seq.len(), 0);
321
322        seq.push(ChangeMove::new(
323            0,
324            Some(42),
325            get_value,
326            set_value,
327            "test",
328            0,
329        ));
330        assert_eq!(seq.len(), 1);
331
332        let m = seq.pop();
333        assert!(m.is_some());
334        assert!(seq.is_empty());
335    }
336}
solverforge_solver/phase/exhaustive/node.rs

solverforge_solver/phase/exhaustive/
node.rs
