dtrees_rs/algorithms/optimal/rules/
common.rs

1//! The rules that define the DL8.5 problem, plus the time limit. None of them
2//! is relaxable except, optionally, the time limit.
3
4use crate::algorithms::optimal::rules::core::Reason;
5use crate::algorithms::optimal::rules::{Rule, RuleContext, RuleResult, RuleState};
6use crate::caching::EXACT;
7use crate::globals::float_is_null;
8use std::time::Instant;
9
10/// Turns nodes at the maximum depth into leaves.
11#[derive(Debug)]
12pub struct MaxDepthRule {
13    max_depth: usize,
14    priority: u8,
15}
16
17impl MaxDepthRule {
18    /// A rule for trees of at most `max_depth` levels.
19    pub fn new(max_depth: usize) -> Self {
20        Self {
21            max_depth,
22            priority: 98,
23        }
24    }
25}
26
27impl Rule for MaxDepthRule {
28    fn evaluate(&self, context: &RuleContext) -> RuleResult {
29        if context.depth >= self.max_depth {
30            RuleResult::stop_with_bound(EXACT, Reason::MaxDepthReached)
31                .optimal()
32                .leaf()
33        } else {
34            RuleResult::continue_search()
35        }
36    }
37
38    fn priority(&self) -> u8 {
39        self.priority
40    }
41
42    fn description(&self) -> String {
43        format!("Max depth {}", self.max_depth)
44    }
45
46    fn state(&self) -> RuleState {
47        RuleState::Active
48    }
49
50    fn is_relaxable(&self) -> bool {
51        false
52    }
53
54    fn as_any(&self) -> &dyn std::any::Any {
55        self
56    }
57
58    fn as_any_mut(&mut self) -> &mut dyn std::any::Any {
59        self
60    }
61}
62
63/// Turns nodes with fewer than `min_support` instances into leaves.
64#[derive(Debug)]
65pub struct MinSupportRule {
66    min_support: usize,
67    priority: u8,
68}
69
70impl MinSupportRule {
71    /// A rule requiring `min_support` instances to split a node.
72    pub fn new(min_support: usize) -> Self {
73        Self {
74            min_support,
75            priority: 97,
76        }
77    }
78}
79
80impl Rule for MinSupportRule {
81    fn evaluate(&self, context: &RuleContext) -> RuleResult {
82        if context.support < self.min_support {
83            RuleResult::stop_with_bound(EXACT, Reason::NotEnoughSupport)
84                .optimal()
85                .leaf()
86        } else {
87            RuleResult::continue_search()
88        }
89    }
90
91    fn priority(&self) -> u8 {
92        self.priority
93    }
94
95    fn description(&self) -> String {
96        format!("Min support {}", self.min_support)
97    }
98
99    fn state(&self) -> RuleState {
100        RuleState::Active
101    }
102
103    fn is_relaxable(&self) -> bool {
104        false
105    }
106
107    fn as_any(&self) -> &dyn std::any::Any {
108        self
109    }
110
111    fn as_any_mut(&mut self) -> &mut dyn std::any::Any {
112        self
113    }
114}
115
116/// Stops the search once the time limit is reached.
117///
118/// It also serves as the search's clock. When made relaxable, reaching the
119/// limit ends the current pass and the clock restarts for the next one.
120#[derive(Debug)]
121pub struct TimeLimitRule {
122    time_limit: f64,
123    priority: u8,
124    start_time: Instant,
125    current_state: RuleState,
126    relaxable: bool,
127}
128
129impl Default for TimeLimitRule {
130    fn default() -> Self {
131        Self::new(f64::INFINITY)
132    }
133}
134
135impl TimeLimitRule {
136    /// A rule that stops the search after `time_limit` seconds.
137    pub fn new(time_limit: f64) -> Self {
138        Self {
139            time_limit,
140            priority: 100,
141            start_time: Instant::now(),
142            current_state: RuleState::Disabled,
143            relaxable: false,
144        }
145    }
146    /// Makes the limit apply per pass rather than to the whole search.
147    pub fn relaxable(mut self) -> Self {
148        self.relaxable = true;
149        self
150    }
151
152    /// Seconds since the rule was activated or reset.
153    pub fn elapsed_seconds(&self) -> f64 {
154        self.start_time.elapsed().as_secs_f64()
155    }
156
157    /// Seconds left before the limit, never negative.
158    pub fn remaining_seconds(&self) -> f64 {
159        (self.time_limit - self.elapsed_seconds()).max(0.0)
160    }
161
162    /// Whether the limit is reached.
163    pub fn exhausted(&self) -> bool {
164        self.elapsed_seconds() >= self.time_limit
165    }
166}
167
168impl Rule for TimeLimitRule {
169    fn evaluate(&self, _context: &RuleContext) -> RuleResult {
170        if !self.is_active() {
171            return RuleResult::continue_search();
172        }
173
174        if self.exhausted() {
175            let reason = match self.is_relaxable() {
176                true => Reason::RuleReason,
177                false => Reason::TimeLimitReached,
178            };
179            RuleResult::stop_with_bound(f64::INFINITY, reason)
180        } else {
181            RuleResult::continue_search()
182        }
183    }
184
185    fn priority(&self) -> u8 {
186        self.priority
187    }
188
189    fn description(&self) -> String {
190        "Time limit rule".to_string()
191    }
192
193    fn state(&self) -> RuleState {
194        self.current_state
195    }
196
197    fn activate(&mut self) {
198        self.current_state = RuleState::Active;
199        self.reset();
200    }
201
202    fn deactivate(&mut self) {
203        self.current_state = RuleState::Disabled;
204    }
205
206    fn reset(&mut self) {
207        self.start_time = Instant::now()
208    }
209
210    fn is_relaxable(&self) -> bool {
211        self.relaxable
212    }
213
214    fn relax(&mut self) {
215        if self.is_relaxable() {
216            self.reset()
217        }
218    }
219
220    fn as_any(&self) -> &dyn std::any::Any {
221        self
222    }
223
224    fn as_any_mut(&mut self) -> &mut dyn std::any::Any {
225        self
226    }
227}
228
229/// Stops at nodes whose lower bound reaches the upper bound, or whose upper
230/// bound is zero: no subtree there can improve the parent.
231#[derive(Debug)]
232pub struct LowerBoundRule {
233    priority: u8,
234    current_state: RuleState,
235}
236
237impl Default for LowerBoundRule {
238    fn default() -> Self {
239        Self::new()
240    }
241}
242
243impl LowerBoundRule {
244    /// A new, inactive rule.
245    pub fn new() -> Self {
246        Self {
247            priority: 100,
248            current_state: RuleState::Disabled,
249        }
250    }
251}
252
253impl Rule for LowerBoundRule {
254    fn evaluate(&self, context: &RuleContext) -> RuleResult {
255        if !self.is_active() {
256            return RuleResult::continue_search();
257        }
258
259        if context.upper_bound <= context.node_lower_bound || float_is_null(context.upper_bound) {
260            RuleResult::stop_search(Reason::LowerBoundConstrained)
261        } else {
262            RuleResult::continue_search()
263        }
264    }
265
266    fn priority(&self) -> u8 {
267        self.priority
268    }
269
270    fn description(&self) -> String {
271        "Lower bound rule".to_string()
272    }
273
274    fn state(&self) -> RuleState {
275        self.current_state
276    }
277
278    fn activate(&mut self) {
279        self.current_state = RuleState::Active;
280    }
281
282    fn deactivate(&mut self) {
283        self.current_state = RuleState::Disabled;
284    }
285
286    fn is_relaxable(&self) -> bool {
287        false
288    }
289
290    fn as_any(&self) -> &dyn std::any::Any {
291        self
292    }
293
294    fn as_any_mut(&mut self) -> &mut dyn std::any::Any {
295        self
296    }
297}
298
299/// Stops at nodes already solved in an earlier visit: a complete search found
300/// their error at or below its bound, so it is their optimum. Always active.
301#[derive(Debug)]
302pub struct UsableNodeRule {
303    priority: u8,
304}
305
306impl Default for UsableNodeRule {
307    fn default() -> Self {
308        Self::new()
309    }
310}
311
312impl UsableNodeRule {
313    /// A new rule.
314    pub fn new() -> Self {
315        Self { priority: 101 }
316    }
317}
318
319impl Rule for UsableNodeRule {
320    fn evaluate(&self, context: &RuleContext) -> RuleResult {
321        if !self.is_active() {
322            return RuleResult::continue_search();
323        }
324
325        if context.node_upper_bound.is_finite() && context.error <= context.node_upper_bound {
326            RuleResult::stop_search(Reason::Done)
327        } else {
328            RuleResult::continue_search()
329        }
330    }
331
332    fn priority(&self) -> u8 {
333        self.priority
334    }
335
336    fn description(&self) -> String {
337        "Usable node rule".to_string()
338    }
339
340    fn state(&self) -> RuleState {
341        RuleState::Active
342    }
343
344    fn is_relaxable(&self) -> bool {
345        false
346    }
347
348    fn as_any(&self) -> &dyn std::any::Any {
349        self
350    }
351
352    fn as_any_mut(&mut self) -> &mut dyn std::any::Any {
353        self
354    }
355}
356
357/// Turns nodes with zero error as a leaf into leaves.
358#[derive(Debug)]
359pub struct PureNodeRule {
360    priority: u8,
361}
362
363impl Default for PureNodeRule {
364    fn default() -> Self {
365        Self::new()
366    }
367}
368
369impl PureNodeRule {
370    /// A new rule.
371    pub fn new() -> Self {
372        Self { priority: 99 }
373    }
374}
375
376impl Rule for PureNodeRule {
377    fn evaluate(&self, context: &RuleContext) -> RuleResult {
378        if float_is_null(context.leaf_error) {
379            RuleResult::stop_with_bound(EXACT, Reason::PureNode)
380                .optimal()
381                .leaf()
382        } else {
383            RuleResult::continue_search()
384        }
385    }
386
387    fn priority(&self) -> u8 {
388        self.priority
389    }
390
391    fn description(&self) -> String {
392        "Pure node rule".to_string()
393    }
394
395    fn state(&self) -> RuleState {
396        RuleState::Active
397    }
398
399    fn is_relaxable(&self) -> bool {
400        false
401    }
402
403    fn as_any(&self) -> &dyn std::any::Any {
404        self
405    }
406
407    fn as_any_mut(&mut self) -> &mut dyn std::any::Any {
408        self
409    }
410}
411
412/// Applies the similarity lower bound of DL8.5: stops when the bound reaches
413/// the upper bound, makes the node a leaf when the leaf meets the bound, and
414/// stops when the best tree found meets it.
415#[derive(Debug)]
416pub struct SimilarityLowerBoundRule {
417    priority: u8,
418    current_state: RuleState,
419}
420
421impl Default for SimilarityLowerBoundRule {
422    fn default() -> Self {
423        Self::new()
424    }
425}
426
427impl SimilarityLowerBoundRule {
428    /// A new, inactive rule.
429    pub fn new() -> Self {
430        Self {
431            priority: 100,
432            current_state: RuleState::Disabled,
433        }
434    }
435}
436
437impl Rule for SimilarityLowerBoundRule {
438    fn evaluate(&self, context: &RuleContext) -> RuleResult {
439        if !self.is_active() {
440            return RuleResult::continue_search();
441        }
442        if context.node_lower_bound >= context.upper_bound {
443            return RuleResult::stop_search(Reason::LowerBoundConstrained);
444        }
445        if context.leaf_error <= context.node_lower_bound {
446            return RuleResult::stop_with_bound(EXACT, Reason::PureNode)
447                .optimal()
448                .leaf();
449        }
450        if context.error <= context.node_lower_bound {
451            return RuleResult::stop_search(Reason::Done);
452        }
453        RuleResult::continue_search()
454    }
455
456    fn priority(&self) -> u8 {
457        self.priority
458    }
459
460    fn description(&self) -> String {
461        "Similarity Lower Bound Rule".to_string()
462    }
463
464    fn state(&self) -> RuleState {
465        self.current_state
466    }
467
468    fn is_active(&self) -> bool {
469        self.current_state == RuleState::Active
470    }
471
472    fn activate(&mut self) {
473        self.current_state = RuleState::Active
474    }
475
476    fn deactivate(&mut self) {
477        self.current_state = RuleState::Disabled
478    }
479
480    fn is_relaxable(&self) -> bool {
481        false
482    }
483
484    fn as_any(&self) -> &dyn std::any::Any {
485        self
486    }
487
488    fn as_any_mut(&mut self) -> &mut dyn std::any::Any {
489        self
490    }
491}
dtrees_rs/algorithms/optimal/rules/common.rs

dtrees_rs/algorithms/optimal/rules/
common.rs
