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 assignments made).
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    #[inline]
85    pub fn depth(&self) -> usize {
86        self.depth
87    }
88
89    #[inline]
90    pub fn score(&self) -> &S::Score {
91        &self.score
92    }
93
94    pub fn set_score(&mut self, score: S::Score) {
95        self.score = score;
96    }
97
98    #[inline]
99    pub fn optimistic_bound(&self) -> Option<&S::Score> {
100        self.optimistic_bound.as_ref()
101    }
102
103    pub fn set_optimistic_bound(&mut self, bound: S::Score) {
104        self.optimistic_bound = Some(bound);
105    }
106
107    #[inline]
108    pub fn descriptor_index(&self) -> Option<usize> {
109        self.descriptor_index
110    }
111
112    #[inline]
113    pub fn variable_index(&self) -> Option<usize> {
114        self.variable_index
115    }
116
117    #[inline]
118    pub fn entity_index(&self) -> Option<usize> {
119        self.entity_index
120    }
121
122    #[inline]
123    pub fn candidate_value_index(&self) -> Option<usize> {
124        self.candidate_value_index
125    }
126
127    #[inline]
128    pub fn parent_index(&self) -> Option<usize> {
129        self.parent_index
130    }
131
132    // Returns whether this node has been expanded.
133    #[inline]
134    pub fn is_expanded(&self) -> bool {
135        self.expanded
136    }
137
138    /// Marks this node as expanded.
139    pub fn mark_expanded(&mut self) {
140        self.expanded = true;
141    }
142
143    pub fn is_leaf(&self, total_entities: usize) -> bool {
144        self.depth >= total_entities
145    }
146
147    pub fn can_prune(&self, best_score: &S::Score) -> bool {
148        match &self.optimistic_bound {
149            Some(bound) => bound <= best_score,
150            None => false,
151        }
152    }
153
154    pub fn assignment_path<'a>(&'a self, all_nodes: &'a [Self]) -> Vec<&'a Self> {
155        let mut path = Vec::with_capacity(self.depth);
156        let mut current = Some(self);
157
158        while let Some(node) = current {
159            if node.parent_index.is_some() {
160                path.push(node);
161            }
162            current = node.parent_index.and_then(|index| all_nodes.get(index));
163        }
164
165        path.reverse();
166        path
167    }
168}
169
170#[cfg(test)]
171#[path = "node_tests.rs"]
172mod tests;
solverforge_solver/phase/exhaustive/node.rs

solverforge_solver/phase/exhaustive/
node.rs
