sim_lib_discrete_graph/
cookbook.rs

1//! Deterministic cookbook builders for discrete graph recipes.
2
3// conformance: staged Bellman selection composes with verified DTW without a copied DP loop.
4
5use crate::{
6    Directedness, DtwPolicy, GapPolicy, Graph, GraphError, bfs, dynamic_time_warp, kruskals_mst,
7    layered_shortest_path, verify_alignment, verify_layered_path,
8};
9
10/// Report produced by the tiny graph cookbook recipe.
11#[derive(Clone, Debug, PartialEq, Eq)]
12pub struct TinyGraphDemo {
13    /// Number of graph nodes.
14    pub node_count: usize,
15    /// Number of graph edges.
16    pub edge_count: usize,
17    /// Breadth-first traversal order from node 0.
18    pub bfs_order: Vec<usize>,
19    /// Minimum-spanning-tree edge ids.
20    pub mst_edge_ids: Vec<usize>,
21    /// Minimum-spanning-tree total weight.
22    pub mst_total_weight: i64,
23}
24
25/// Joint evidence from composing staged dynamic programming and DTW alignment.
26#[derive(Clone, Debug, PartialEq, Eq)]
27pub struct AlignmentCompositionDemo {
28    /// States selected by certified staged optimization.
29    pub staged_states: Vec<i64>,
30    /// Stable state index selected in every stage.
31    pub staged_indices: Vec<usize>,
32    /// Exact staged transition cost.
33    pub staged_cost: i64,
34    /// Bellman cells retained by staged optimization.
35    pub staged_cells: u64,
36    /// Staged transitions examined.
37    pub staged_edges: u64,
38    /// Exact DTW/edit alignment score.
39    pub alignment_score: i64,
40    /// Number of stable operations in the retained alignment path.
41    pub alignment_steps: usize,
42    /// Prefix-grid cells retained by full-memory DTW.
43    pub alignment_cells: u64,
44    /// DTW predecessor edges examined.
45    pub alignment_edges: u64,
46}
47
48/// Build the modeled graph traversal and MST report used by the cookbook.
49pub fn tiny_graph_demo() -> Result<TinyGraphDemo, GraphError> {
50    let mut graph = Graph::with_nodes(vec![0, 1, 2], Directedness::Undirected);
51    graph.add_edge(0, 1, 1_i64)?;
52    graph.add_edge(1, 2, 2_i64)?;
53    graph.add_edge(0, 2, 5_i64)?;
54
55    let traversal = bfs(&graph, 0)?;
56    let mst = kruskals_mst(&graph)?;
57
58    Ok(TinyGraphDemo {
59        node_count: graph.node_count(),
60        edge_count: graph.edge_count(),
61        bfs_order: traversal.order,
62        mst_edge_ids: mst.edges,
63        mst_total_weight: mst.total_weight,
64    })
65}
66
67/// Runs the reusable staged-path and DTW owners as one checked composition.
68///
69/// This is the adapter point for statistics, music, or analysis callers that
70/// first select states and then align sequences. It deliberately invokes both
71/// public algorithms and both verifiers rather than carrying another DP loop.
72pub fn alignment_composition_demo() -> Result<AlignmentCompositionDemo, GraphError> {
73    let layers = vec![vec![0_i64, 3], vec![2_i64, 5], vec![4_i64, 7]];
74    let staged = layered_shortest_path(&layers, |left, right| left.abs_diff(*right) as i64)?;
75    verify_layered_path(
76        &layers,
77        |left, right| Some(left.abs_diff(*right) as i64),
78        &staged,
79    )?;
80
81    let left = [0_i64, 2, 4];
82    let right = [0_i64, 1, 2, 4];
83    let policy = DtwPolicy::new(GapPolicy::new(2_i64, 2_i64));
84    let alignment = dynamic_time_warp(
85        &left,
86        &right,
87        |left, right| left.abs_diff(*right) as i64,
88        policy.clone(),
89    )?;
90    verify_alignment(
91        &left,
92        &right,
93        |left, right| left.abs_diff(*right) as i64,
94        &policy,
95        &alignment,
96    )?;
97
98    Ok(AlignmentCompositionDemo {
99        staged_states: staged.states,
100        staged_indices: staged.indices,
101        staged_cost: staged.total_cost,
102        staged_cells: staged.receipt.cells,
103        staged_edges: staged.receipt.edges,
104        alignment_score: alignment.score,
105        alignment_steps: alignment.steps.as_ref().map_or(0, Vec::len),
106        alignment_cells: alignment.receipt.cells,
107        alignment_edges: alignment.receipt.edges,
108    })
109}
110
111#[cfg(test)]
112mod tests {
113    use super::*;
114
115    #[test]
116    fn graph_demo_runs_bfs_and_mst() {
117        let demo = tiny_graph_demo().expect("valid graph demo");
118
119        assert_eq!(demo.node_count, 3);
120        assert_eq!(demo.edge_count, 3);
121        assert_eq!(demo.bfs_order, vec![0, 1, 2]);
122        assert_eq!(demo.mst_edge_ids, vec![0, 1]);
123        assert_eq!(demo.mst_total_weight, 3);
124    }
125
126    #[test]
127    fn staged_selection_composes_with_dtw_and_verifies_both_certificates() {
128        let demo = alignment_composition_demo().expect("composed alignment evidence");
129        assert_eq!(demo.staged_states, vec![3, 2, 4]);
130        assert_eq!(demo.staged_indices, vec![1, 0, 0]);
131        assert_eq!(demo.staged_cost, 3);
132        assert_eq!(demo.alignment_score, 2);
133        assert_eq!(demo.alignment_steps, 4);
134        assert!(demo.staged_cells > 0 && demo.staged_edges > 0);
135        assert!(demo.alignment_cells > 0 && demo.alignment_edges > 0);
136    }
137}
sim_lib_discrete_graph/cookbook.rs

sim_lib_discrete_graph/
cookbook.rs
