explicit_graph/
explicit-graph.rs

1//! This is a trivial example that does not solve any optimizatino problem,
2//! just walks an explicitly given graph using `branch_and_bound`.
3
4use bb::SubproblemResolution;
5use branch_and_bound as bb;
6
7#[derive(Clone, Debug)]
8struct GraphNode {
9    bound: i32,
10    next: Vec<GraphNode>,
11}
12
13impl bb::Subproblem for GraphNode {
14    type Score = i32;
15
16    fn branch_or_evaluate(&mut self) -> branch_and_bound::SubproblemResolution<GraphNode, i32> {
17        if self.bound < 5 {
18            eprintln!("I should not be visited in Best-First-Search");
19        } else {
20            eprintln!("Node with bound {0} visited", self.bound)
21        }
22        if self.next.is_empty() {
23            SubproblemResolution::Solved(self.bound)
24        } else {
25            SubproblemResolution::Branched(Box::new(self.next.clone().into_iter()))
26        }
27    }
28
29    fn bound(&self) -> i32 {
30        self.bound
31    }
32}
33
34fn graph() -> GraphNode {
35    let leaf0 = GraphNode {
36        bound: 0,
37        next: vec![],
38    };
39    let leaf1 = GraphNode {
40        bound: 1,
41        next: vec![],
42    };
43    let leaf2 = GraphNode {
44        bound: 2,
45        next: vec![],
46    };
47    let leaf3 = GraphNode {
48        bound: 3,
49        next: vec![],
50    };
51    let leaf4 = GraphNode {
52        bound: 4,
53        next: vec![],
54    };
55    let leaf5 = GraphNode {
56        bound: 5,
57        next: vec![],
58    };
59
60    let parent23 = GraphNode {
61        bound: 4,
62        next: vec![leaf2, leaf3],
63    };
64    let parent1p23 = GraphNode {
65        bound: 5,
66        next: vec![leaf1, parent23],
67    };
68
69    let parent45 = GraphNode {
70        bound: 6,
71        next: vec![leaf4, leaf5],
72    };
73    let parent0p45 = GraphNode {
74        bound: 7,
75        next: vec![leaf0, parent45],
76    };
77
78    let root = GraphNode {
79        bound: 8,
80        next: vec![parent0p45, parent1p23],
81    };
82
83    root
84}
85
86fn main() {
87    println!("Trying depth-first search");
88    println!(
89        "Max node: {:#?}",
90        bb::solve(graph(), bb::TraverseMethod::DepthFirst)
91    );
92
93    println!("Trying breadth-first search");
94    println!(
95        "Max node: {:#?}",
96        bb::solve(graph(), bb::TraverseMethod::BreadthFirst)
97    );
98
99    println!("Now trying best-first search");
100    println!(
101        "Max node: {:#?}",
102        bb::solve(graph(), bb::TraverseMethod::BestFirst)
103    );
104
105    println!("Trying custom-order (should be same as best-first!)");
106    println!(
107        "Max node: {:#?}",
108        bb::solve(
109            graph(),
110            bb::TraverseMethod::Custom {
111                cmp: Box::new(|n1, n2| n1.bound.cmp(&n2.bound)),
112                cmp_superceeds_bound: true
113            }
114        )
115    );
116
117    println!("Trying custom-order, worst-first search");
118    println!(
119        "Max node: {:#?}",
120        bb::solve(
121            graph(),
122            bb::TraverseMethod::Custom {
123                cmp: Box::new(|n1, n2| n2.bound.cmp(&n1.bound)),
124                cmp_superceeds_bound: false
125            }
126        )
127    );
128}
explicit_graph/explicit-graph.rs

explicit_graph/
explicit-graph.rs
