Graph: controlling traversal

The graph — Treeish<N>, or the more general Edgy<N, E> — is a function from a node to its children, and determines what is visited during the fold. The node type N may be any type: a struct, an integer index, a string key, a database identifier. The structure of the tree resides in the function, not in the data.

Constructors

Three means of creating a Treeish<N>:

#![allow(unused)]
fn main() {
    #[test]
    fn treeish_constructors() {
        use hylic::prelude::*;

        #[derive(Clone)]
        struct Node { value: u64, children: Vec<Node> }

        let root = Node { value: 1, children: vec![Node { value: 2, children: vec![] }] };

        // Callback-based (zero allocation per visit):
        let g1: Treeish<Node> = treeish_visit(|n: &Node, cb: &mut dyn FnMut(&Node)| {
            for child in &n.children { cb(child); }
        });

        // Vec-returning (allocates per visit):
        let g2: Treeish<Node> = treeish(|n: &Node| n.children.clone());

        // Slice accessor (borrows, zero allocation):
        let g3: Treeish<Node> = treeish_from(|n: &Node| n.children.as_slice());

        assert_eq!(g1.apply(&root).len(), 1);
        assert_eq!(g2.apply(&root).len(), 1);
        assert_eq!(g3.apply(&root).len(), 1);

        // Flat data — nodes are indices, children from adjacency list:
        let adj: Vec<Vec<usize>> = vec![vec![1, 2], vec![], vec![]];
        let g4: Treeish<usize> = treeish_visit(move |n: &usize, cb: &mut dyn FnMut(&usize)| {
            for &c in &adj[*n] { cb(&c); }
        });
        assert_eq!(g4.apply(&0).len(), 2);
    }
}

treeish_visit is the most general form; its callback receives each child without the allocation of a Vec. treeish wraps a Vec-returning function for convenience, and treeish_from extracts a slice reference from a field.

For non-nested data — adjacency lists, maps, external lookups — treeish_visit is the appropriate constructor:

// Adjacency list: nodes are indices
let adj: Vec<Vec<usize>> = vec![vec![1, 2], vec![3], vec![], vec![]];
let graph = treeish_visit(move |n: &usize, cb: &mut dyn FnMut(&usize)| {
    for &c in &adj[*n] { cb(&c); }
});

// HashMap-backed graph: nodes are string keys
let edges: HashMap<String, Vec<String>> = /* ... */;
let graph = treeish_visit(move |n: &String, cb: &mut dyn FnMut(&String)| {
    if let Some(children) = edges.get(n) {
        for c in children { cb(c); }
    }
});

For a runnable adjacency-list example, see intro_flat_example.

Edge transformations

The Edgy<N, E> type generalises Treeish<N> by allowing edges and nodes to be different types. Combinators transform the edge type or the node type:

filter — pruning children

#![allow(unused)]
fn main() {
    #[test]
    fn graph_filter() {
        use hylic::prelude::*;

        #[derive(Clone)]
        struct Node { value: u64, children: Vec<Node> }

        let graph: Treeish<Node> = treeish(|n: &Node| n.children.clone());
        let f:     Fold<Node, u64, u64> = fold(
            |n: &Node| n.value,
            |h: &mut u64, c: &u64| *h += c,
            |h: &u64| *h,
        );

        let root = Node { value: 1, children: vec![
            Node { value: 10, children: vec![] },
            Node { value: 2, children: vec![] },
        ]};

        // Only visit children with value > 5.
        let pruned: Treeish<Node> = graph.filter(|child: &Node| child.value > 5);
        let result: u64 = FUSED.run(&f, &pruned, &root);
        assert_eq!(result, 11); // 1 + 10 (skipped 2)
    }
}

The fold sees fewer children without any awareness that pruning has occurred.

Caching: memoize_treeish

For DAGs in which the same node is reachable from multiple parents, memoize_treeish caches the child enumeration:

#![allow(unused)]
fn main() {
    #[test]
    fn memoize_example() {
        use hylic::prelude::*;
        use std::sync::atomic::{AtomicUsize, Ordering};
        use std::sync::Arc;

        let call_count = Arc::new(AtomicUsize::new(0));
        let cc = call_count.clone();

        let graph: Treeish<u64> = treeish(move |n: &u64| -> Vec<u64> {
            cc.fetch_add(1, Ordering::Relaxed);
            if *n == 0 { vec![] } else { vec![n - 1] }
        });
        let f: Fold<u64, u64, u64> = fold(
            |n: &u64| *n,
            |h: &mut u64, c: &u64| *h += c,
            |h: &u64| *h,
        );

        let cached: Treeish<u64> = memoize_treeish(&graph);
        let _ = FUSED.run(&f, &cached, &3u64);
        let first_count = call_count.load(Ordering::Relaxed);

        // Second run hits the cache; no new calls into `graph`.
        let _ = FUSED.run(&f, &cached, &3u64);
        let second_count = call_count.load(Ordering::Relaxed);
        assert_eq!(first_count, second_count);
    }
}

The first visit to a key computes and caches its children; subsequent visits return the cached result.

Visit combinator

Edgy::at(node) returns a Visit<T, F> — a push-based iterator exposing map, filter, fold, count, and collect_vec. All combinators are callback-based internally.