branch_and_bound/
candidate.rs

1use crate::{Subproblem, SubproblemResolution};
2
3/// `OrderedCandidate` encapsulates a `Node` (which has to be `Subproblem`)
4/// and defines an order on it.
5pub trait OrderedCandidate: Ord + Subproblem {
6    type Node: Subproblem;
7
8    /// Create an `OrderedCandidate`.
9    /// This method should be used for the root node.
10    fn new(root: Self::Node) -> Self;
11    /// Peeks at the encapsulated node
12    fn node(&self) -> &Self::Node;
13    /// Consumes the candidate and returns the node
14    fn into_node(self) -> Self::Node;
15}
16
17/// `BoundOrderedCandidate` implements `{Partial,}Eq` and `{Partial,}Ord`
18/// based on the value of `node.bound()`.
19///
20/// Note: two `BoundOrderedCandidate`s wrapping different nodes with the boundary
21/// will compare equal!
22pub(crate) struct BoundOrderedCandidate<Node: Subproblem<Score = Score>, Score: Ord> {
23    node: Node,
24    bound: Score,
25}
26
27/// `DepthOrderedCandidate` implements `{Partial,}Eq` and `{Partial,}Ord`
28/// based on the depth in the tree (higher in the tree is less; root is the lowest).
29///
30/// Note: two `DepthOrderedCandidate`s wrapping different nodes on the same level
31/// of the tree will compare equal!
32pub(crate) struct DepthOrderedCandidate<Node: Subproblem<Score = Score>, Score: Ord> {
33    node: Node,
34    depth: u64,
35}
36
37impl<Score: Ord, Node: Subproblem<Score = Score>> PartialEq for BoundOrderedCandidate<Node, Score> {
38    fn eq(&self, other: &Self) -> bool {
39        self.bound == other.bound
40    }
41}
42
43impl<Score: Ord, Node: Subproblem<Score = Score>> Eq for BoundOrderedCandidate<Node, Score> {}
44
45impl<Score: Ord, Node: Subproblem<Score = Score>> PartialOrd
46    for BoundOrderedCandidate<Node, Score>
47{
48    fn partial_cmp(&self, other: &Self) -> Option<std::cmp::Ordering> {
49        Some(self.cmp(other))
50    }
51}
52
53impl<Score: Ord, Node: Subproblem<Score = Score>> Ord for BoundOrderedCandidate<Node, Score> {
54    fn cmp(&self, other: &Self) -> std::cmp::Ordering {
55        self.bound.cmp(&other.bound)
56    }
57}
58
59impl<Score, Node> Subproblem for BoundOrderedCandidate<Node, Score>
60where
61    Score: Ord,
62    Node: Subproblem<Score = Score> + 'static,
63{
64    type Score = Score;
65
66    fn branch_or_evaluate(&self) -> crate::SubproblemResolution<Self, Self::Score> {
67        use SubproblemResolution::{Branched, Solved};
68
69        match self.node.branch_or_evaluate() {
70            Solved(score) => Solved(score),
71            // Just wrap all `Node`s into `Self`. Won't compile without clojure (why??)
72            Branched(subproblems) => Branched(Box::new(subproblems.map(|node| Self::new(node)))),
73        }
74    }
75
76    fn bound(&self) -> Self::Score {
77        self.node.bound()
78    }
79}
80
81impl<Score, Node> OrderedCandidate for BoundOrderedCandidate<Node, Score>
82where
83    Score: Ord,
84    Node: Subproblem<Score = Score> + 'static,
85{
86    type Node = Node;
87
88    fn new(root: Self::Node) -> Self {
89        Self {
90            bound: root.bound(),
91            node: root,
92        }
93    }
94
95    fn node(&self) -> &Self::Node {
96        &self.node
97    }
98
99    fn into_node(self) -> Self::Node {
100        self.node
101    }
102}
103
104impl<Score: Ord, Node: Subproblem<Score = Score>> PartialEq for DepthOrderedCandidate<Node, Score> {
105    fn eq(&self, other: &Self) -> bool {
106        self.depth == other.depth
107    }
108}
109
110impl<Score: Ord, Node: Subproblem<Score = Score>> Eq for DepthOrderedCandidate<Node, Score> {}
111
112impl<Score: Ord, Node: Subproblem<Score = Score>> PartialOrd
113    for DepthOrderedCandidate<Node, Score>
114{
115    fn partial_cmp(&self, other: &Self) -> Option<std::cmp::Ordering> {
116        Some(self.cmp(other))
117    }
118}
119
120impl<Score: Ord, Node: Subproblem<Score = Score>> Ord for DepthOrderedCandidate<Node, Score> {
121    fn cmp(&self, other: &Self) -> std::cmp::Ordering {
122        self.depth.cmp(&other.depth)
123    }
124}
125
126impl<Score, Node> Subproblem for DepthOrderedCandidate<Node, Score>
127where
128    Score: Ord,
129    Node: Subproblem<Score = Score> + 'static,
130{
131    type Score = Score;
132
133    fn branch_or_evaluate(&self) -> SubproblemResolution<Self, Self::Score> {
134        use SubproblemResolution::{Branched, Solved};
135
136        let depth: u64 = self.depth;
137        match self.node.branch_or_evaluate() {
138            Solved(score) => Solved(score),
139            Branched(subproblems) => Branched(Box::new(subproblems.map(move |subnode| Self {
140                node: subnode,
141                depth: depth + 1,
142            }))),
143        }
144    }
145
146    fn bound(&self) -> Self::Score {
147        self.node.bound()
148    }
149}
150
151impl<Score, Node> OrderedCandidate for DepthOrderedCandidate<Node, Score>
152where
153    Score: Ord,
154    Node: Subproblem<Score = Score> + 'static,
155{
156    type Node = Node;
157
158    fn new(root: Self::Node) -> Self {
159        Self {
160            node: root,
161            depth: 0,
162        }
163    }
164
165    fn node(&self) -> &Self::Node {
166        &self.node
167    }
168
169    fn into_node(self) -> Self::Node {
170        self.node
171    }
172}
branch_and_bound/candidate.rs

branch_and_bound/
candidate.rs
