rpid 0.3.1

Rust Programmable Interface for Domain-Independent Dynamic Programming (RPID)
Documentation 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151

//! Search nodes for state space search.

mod cost_node;
mod dual_bound_node;
mod id_tree;
mod state_registry;

pub use crate::dp::DpMut;
pub use cost_node::CostNode;
pub use dual_bound_node::DualBoundNode;
pub use id_tree::IdTree;
pub use state_registry::{InsertionResult, StateRegistry};

/// Trait for search nodes.
pub trait SearchNode: Sized {
    /// Type of the DP data.
    type DpData: DpMut<State = Self::State, CostType = Self::CostType>;
    /// Type of the state.
    type State;
    /// Type of the cost.
    type CostType;
    /// Type of the transition label.
    type Label;

    /// Returns the state of the node.
    fn get_state(&self, dp: &Self::DpData) -> &Self::State;

    /// Returns the state of the node.
    fn get_state_mut(&mut self, dp: &Self::DpData) -> &mut Self::State;

    /// Returns the cost of the node.
    fn get_cost(&self, dp: &Self::DpData) -> Self::CostType;

    /// Returns the dual bound of the path cost extending the node.
    fn get_bound(&self, dp: &Self::DpData) -> Option<Self::CostType>;

    /// Returns whether the node is closed.
    fn is_closed(&self) -> bool;

    /// Closes the node.
    fn close(&self);

    /// Returns the transitions to reach the node.
    fn get_transitions(&self, dp: &Self::DpData) -> Vec<Self::Label>;

    /// Checks if the node is a solution and returns the cost and transitions if it is.
    fn check_solution(&self, dp: &mut Self::DpData) -> Option<(Self::CostType, Vec<Self::Label>)> {
        let state = self.get_state(dp);
        let cost = self.get_cost(dp);

        if let Some(solution_cost) = dp
            .get_base_cost(state)
            .map(|base_cost| dp.combine_cost_weights(cost, base_cost))
        {
            let transitions = self.get_transitions(dp);

            Some((solution_cost, transitions))
        } else {
            None
        }
    }

    /// Returns whether the nodes are ordered by dual bound values.
    fn ordered_by_bound() -> bool {
        false
    }
}

#[cfg(test)]
mod tests {
    use super::*;
    use crate::dp::Dp;

    struct MockDp;

    impl Dp for MockDp {
        type State = i32;
        type CostType = i32;
        type Label = usize;

        fn get_target(&self) -> Self::State {
            2
        }

        fn get_successors(
            &self,
            _: &Self::State,
        ) -> impl IntoIterator<Item = (Self::State, Self::CostType, Self::Label)> {
            vec![]
        }

        fn get_base_cost(&self, state: &Self::State) -> Option<Self::CostType> {
            if *state == 0 { Some(0) } else { None }
        }

        fn combine_cost_weights(&self, a: Self::CostType, b: Self::CostType) -> Self::CostType {
            a + b
        }
    }

    struct MockNode(i32);

    impl SearchNode for MockNode {
        type DpData = MockDp;
        type State = i32;
        type CostType = i32;
        type Label = usize;

        fn get_state(&self, _: &Self::DpData) -> &Self::State {
            &self.0
        }

        fn get_state_mut(&mut self, _: &Self::DpData) -> &mut Self::State {
            &mut self.0
        }

        fn get_cost(&self, _: &Self::DpData) -> Self::CostType {
            2
        }

        fn get_bound(&self, _: &Self::DpData) -> Option<Self::CostType> {
            Some(0)
        }

        fn is_closed(&self) -> bool {
            false
        }

        fn close(&self) {}

        fn get_transitions(&self, _: &Self::DpData) -> Vec<Self::Label> {
            vec![0, 1]
        }
    }

    #[test]
    fn test_check_solution() {
        let mut dp = MockDp;
        let node = MockNode(0);

        assert_eq!(node.check_solution(&mut dp), Some((2, vec![0, 1])));
    }

    #[test]
    fn test_check_solution_none() {
        let mut dp = MockDp;
        let node = MockNode(1);

        assert_eq!(node.check_solution(&mut dp), None);
    }
}