tree_traversal

A Rust library for finding the optimal leaf node in a tree structure. This crate implements several tree traversal algorithms to find the best (the lowest cost) leaf node in a tree.

Algorithms

• Breadth First Search
• Depth First Search
• Beam Search
• Branch and Bound Search
• Greedy Search

Using this crate

cargo add tree_traversal

Example

use tree_traversal::bbs::bbs;

type Node = Vec<bool>;

fn main() {
    let weights = [4, 2, 6, 3, 4];
    let profits = [100, 20, 2, 5, 10];
    let capacity = 8 as u32;
    let total_items = weights.len();

    let successor_fn = |n: &Node| {
        if n.len() == total_items {
            return vec![];
        }

        let total_weight: u32 = n
            .iter()
            .copied()
            .enumerate()
            .map(|(i, b)| {
                if b {
                    return weights[i];
                } else {
                    return 0;
                }
            })
            .sum();

        let mut childrean = vec![];

        let next_idx = n.len();
        if capacity >= total_weight + weights[next_idx] {
            let mut c1 = n.clone();
            c1.push(true);
            childrean.push(c1);
        }

        let mut c2 = n.clone();
        c2.push(false);
        childrean.push(c2);

        childrean
    };

    let total_profit = |n: &Node| {
        let s: u32 = n
            .iter()
            .copied()
            .enumerate()
            .map(|(i, b)| {
                if b {
                    return profits[i];
                } else {
                    return 0;
                }
            })
            .sum();
        s
    };

    // tree traversal assumes a minimization problem
    // if you want to solve maximization problem, subtract your actual score from the MAX value
    let lower_bound_fn = |n: &Node| {
        let current_profit = total_profit(n);
        let max_remained_profit: u32 = profits[n.len()..].into_iter().sum();
        Some(u32::MAX - (current_profit + max_remained_profit))
    };

    let cost_fn = |n: &Node| Some(u32::MAX - total_profit(n));

    let leaf_check_fn = |n: &Node| n.len() == total_items;

    let (cost, best_node) =
        bbs(vec![], successor_fn, lower_bound_fn, cost_fn, leaf_check_fn).unwrap();
    let cost = u32::MAX - cost;

    dbg!((best_node, cost));
}

Note

The API is derived from the great pathfinding crate.