solverforge_solver/phase/exhaustive/
node.rs

1/* Exhaustive search node representation.
2
3Each node represents a partial solution state in the search tree.
4*/
5
6use solverforge_core::domain::PlanningSolution;
7
8/* A node in the exhaustive search tree.
9
10Each node represents a partial solution state, containing:
11- The depth in the search tree (number of variables assigned)
12- The score at this node
13- An optimistic bound (best possible score from this node)
14- The scalar assignment index tuple to reach this node from its parent
15*/
16#[derive(Clone, Debug)]
17pub struct ExhaustiveSearchNode<S: PlanningSolution> {
18    // Depth in the search tree (0 = root, number of entity positions processed).
19    depth: usize,
20
21    // The score at this node after applying all moves.
22    score: S::Score,
23
24    // Optimistic bound: best possible score achievable from this node.
25    // Used for pruning branches that cannot improve on the best solution.
26    optimistic_bound: Option<S::Score>,
27
28    // Descriptor index of the scalar entity collection being assigned.
29    descriptor_index: Option<usize>,
30
31    // Variable index within the descriptor being assigned.
32    variable_index: Option<usize>,
33
34    // Index of the entity being assigned at this node.
35    entity_index: Option<usize>,
36
37    // Index of the candidate value assigned at this node.
38    candidate_value_index: Option<usize>,
39
40    // Parent node index in the node list (None for root).
41    parent_index: Option<usize>,
42
43    // Whether this node has been expanded.
44    expanded: bool,
45}
46
47impl<S: PlanningSolution> ExhaustiveSearchNode<S> {
48    pub fn root(score: S::Score) -> Self {
49        Self {
50            depth: 0,
51            score,
52            optimistic_bound: None,
53            descriptor_index: None,
54            variable_index: None,
55            entity_index: None,
56            candidate_value_index: None,
57            parent_index: None,
58            expanded: false,
59        }
60    }
61
62    pub fn child(
63        parent_index: usize,
64        depth: usize,
65        score: S::Score,
66        descriptor_index: usize,
67        variable_index: usize,
68        entity_index: usize,
69        candidate_value_index: usize,
70    ) -> Self {
71        Self {
72            depth,
73            score,
74            optimistic_bound: None,
75            descriptor_index: Some(descriptor_index),
76            variable_index: Some(variable_index),
77            entity_index: Some(entity_index),
78            candidate_value_index: Some(candidate_value_index),
79            parent_index: Some(parent_index),
80            expanded: false,
81        }
82    }
83
84    /// Advances past an input-pinned row without adding an assignment to replay.
85    pub(crate) fn pinned_child(parent_index: usize, depth: usize, score: S::Score) -> Self {
86        Self {
87            depth,
88            score,
89            optimistic_bound: None,
90            descriptor_index: None,
91            variable_index: None,
92            entity_index: None,
93            candidate_value_index: None,
94            parent_index: Some(parent_index),
95            expanded: false,
96        }
97    }
98
99    #[inline]
100    pub fn depth(&self) -> usize {
101        self.depth
102    }
103
104    #[inline]
105    pub fn score(&self) -> &S::Score {
106        &self.score
107    }
108
109    pub fn set_score(&mut self, score: S::Score) {
110        self.score = score;
111    }
112
113    #[inline]
114    pub fn optimistic_bound(&self) -> Option<&S::Score> {
115        self.optimistic_bound.as_ref()
116    }
117
118    pub fn set_optimistic_bound(&mut self, bound: S::Score) {
119        self.optimistic_bound = Some(bound);
120    }
121
122    #[inline]
123    pub fn descriptor_index(&self) -> Option<usize> {
124        self.descriptor_index
125    }
126
127    #[inline]
128    pub fn variable_index(&self) -> Option<usize> {
129        self.variable_index
130    }
131
132    #[inline]
133    pub fn entity_index(&self) -> Option<usize> {
134        self.entity_index
135    }
136
137    #[inline]
138    pub fn candidate_value_index(&self) -> Option<usize> {
139        self.candidate_value_index
140    }
141
142    #[inline]
143    pub fn parent_index(&self) -> Option<usize> {
144        self.parent_index
145    }
146
147    // Returns whether this node has been expanded.
148    #[inline]
149    pub fn is_expanded(&self) -> bool {
150        self.expanded
151    }
152
153    /// Marks this node as expanded.
154    pub fn mark_expanded(&mut self) {
155        self.expanded = true;
156    }
157
158    pub fn is_leaf(&self, total_entities: usize) -> bool {
159        self.depth >= total_entities
160    }
161
162    pub fn can_prune(&self, best_score: &S::Score) -> bool {
163        match &self.optimistic_bound {
164            Some(bound) => bound <= best_score,
165            None => false,
166        }
167    }
168
169    pub fn assignment_path<'a>(&'a self, all_nodes: &'a [Self]) -> Vec<&'a Self> {
170        let mut path = Vec::with_capacity(self.depth);
171        let mut current = Some(self);
172
173        while let Some(node) = current {
174            if node.parent_index.is_some() {
175                path.push(node);
176            }
177            current = node.parent_index.and_then(|index| all_nodes.get(index));
178        }
179
180        path.reverse();
181        path
182    }
183}
184
185#[cfg(test)]
186#[path = "node_tests.rs"]
187mod tests;
solverforge_solver/phase/exhaustive/node.rs

solverforge_solver/phase/exhaustive/
node.rs
