datasynth_audit_optimizer/
graph.rs

1//! Convert audit blueprints to petgraph directed graphs.
2//!
3//! Each node represents a `(procedure_id, state)` pair and each edge
4//! represents a transition within a procedure's FSM aggregate.
5
6use std::collections::HashMap;
7
8use petgraph::graph::{DiGraph, NodeIndex};
9
10use datasynth_audit_fsm::schema::AuditBlueprint;
11
12// ---------------------------------------------------------------------------
13// Node and edge types
14// ---------------------------------------------------------------------------
15
16/// A graph node representing a procedure state.
17#[derive(Debug, Clone, PartialEq, Eq, Hash)]
18pub struct StateNode {
19    /// The procedure this state belongs to.
20    pub procedure_id: String,
21    /// The state name within the procedure's FSM aggregate.
22    pub state: String,
23}
24
25/// A graph edge representing a transition between states.
26#[derive(Debug, Clone)]
27pub struct TransitionEdge {
28    /// Command that triggers this transition (if any).
29    pub command: Option<String>,
30    /// Event emitted when the transition fires (if any).
31    pub emits: Option<String>,
32    /// Guard predicates that must pass before the transition can fire.
33    pub guards: Vec<String>,
34}
35
36// ---------------------------------------------------------------------------
37// Conversion
38// ---------------------------------------------------------------------------
39
40/// Convert an [`AuditBlueprint`] into a petgraph [`DiGraph`].
41///
42/// Iterates over all phases and their procedures, creating one node per
43/// `(procedure_id, state)` pair and one edge per FSM transition.
44pub fn blueprint_to_graph(blueprint: &AuditBlueprint) -> DiGraph<StateNode, TransitionEdge> {
45    let mut graph = DiGraph::new();
46    // Map from (procedure_id, state) -> NodeIndex for deduplication.
47    let mut node_map: HashMap<(String, String), NodeIndex> = HashMap::new();
48
49    for phase in &blueprint.phases {
50        for procedure in &phase.procedures {
51            let agg = &procedure.aggregate;
52
53            // Ensure all declared states have nodes.
54            for state in &agg.states {
55                let key = (procedure.id.clone(), state.clone());
56                node_map.entry(key.clone()).or_insert_with(|| {
57                    graph.add_node(StateNode {
58                        procedure_id: key.0,
59                        state: key.1,
60                    })
61                });
62            }
63
64            // Create edges for each transition.
65            for transition in &agg.transitions {
66                let from_key = (procedure.id.clone(), transition.from_state.clone());
67                let to_key = (procedure.id.clone(), transition.to_state.clone());
68
69                // Lazily create nodes for states referenced in transitions but
70                // not listed in the explicit states vector.
71                let from_idx = *node_map.entry(from_key.clone()).or_insert_with(|| {
72                    graph.add_node(StateNode {
73                        procedure_id: from_key.0,
74                        state: from_key.1,
75                    })
76                });
77                let to_idx = *node_map.entry(to_key.clone()).or_insert_with(|| {
78                    graph.add_node(StateNode {
79                        procedure_id: to_key.0,
80                        state: to_key.1,
81                    })
82                });
83
84                graph.add_edge(
85                    from_idx,
86                    to_idx,
87                    TransitionEdge {
88                        command: transition.command.clone(),
89                        emits: transition.emits.clone(),
90                        guards: transition.guards.clone(),
91                    },
92                );
93            }
94        }
95    }
96
97    graph
98}
99
100// ---------------------------------------------------------------------------
101// Analysis helpers
102// ---------------------------------------------------------------------------
103
104/// Return nodes with no incoming edges (entry points / initial states).
105pub fn find_initial_nodes(graph: &DiGraph<StateNode, TransitionEdge>) -> Vec<NodeIndex> {
106    graph
107        .node_indices()
108        .filter(|&idx| {
109            graph
110                .neighbors_directed(idx, petgraph::Direction::Incoming)
111                .next()
112                .is_none()
113        })
114        .collect()
115}
116
117/// Return nodes with no outgoing edges (terminal / completed states).
118pub fn find_terminal_nodes(graph: &DiGraph<StateNode, TransitionEdge>) -> Vec<NodeIndex> {
119    graph
120        .node_indices()
121        .filter(|&idx| {
122            graph
123                .neighbors_directed(idx, petgraph::Direction::Outgoing)
124                .next()
125                .is_none()
126        })
127        .collect()
128}
129
130// ---------------------------------------------------------------------------
131// Tests
132// ---------------------------------------------------------------------------
133
134#[cfg(test)]
135mod tests {
136    use super::*;
137    use datasynth_audit_fsm::loader::BlueprintWithPreconditions;
138
139    #[test]
140    fn test_fsa_graph_has_nodes_and_edges() {
141        let bwp = BlueprintWithPreconditions::load_builtin_fsa().unwrap();
142        let graph = blueprint_to_graph(&bwp.blueprint);
143        assert!(
144            graph.node_count() > 0,
145            "FSA graph should have nodes, got {}",
146            graph.node_count()
147        );
148        assert!(
149            graph.edge_count() > 0,
150            "FSA graph should have edges, got {}",
151            graph.edge_count()
152        );
153    }
154
155    #[test]
156    fn test_fsa_graph_has_initial_and_terminal_nodes() {
157        let bwp = BlueprintWithPreconditions::load_builtin_fsa().unwrap();
158        let graph = blueprint_to_graph(&bwp.blueprint);
159        let initials = find_initial_nodes(&graph);
160        let terminals = find_terminal_nodes(&graph);
161        assert!(
162            !initials.is_empty(),
163            "FSA graph should have initial nodes (no incoming edges)"
164        );
165        assert!(
166            !terminals.is_empty(),
167            "FSA graph should have terminal nodes (no outgoing edges)"
168        );
169    }
170
171    #[test]
172    fn test_ia_graph_larger_than_fsa() {
173        let fsa_bwp = BlueprintWithPreconditions::load_builtin_fsa().unwrap();
174        let ia_bwp = BlueprintWithPreconditions::load_builtin_ia().unwrap();
175        let fsa_graph = blueprint_to_graph(&fsa_bwp.blueprint);
176        let ia_graph = blueprint_to_graph(&ia_bwp.blueprint);
177        assert!(
178            ia_graph.node_count() > fsa_graph.node_count(),
179            "IA graph ({} nodes) should have more nodes than FSA graph ({} nodes)",
180            ia_graph.node_count(),
181            fsa_graph.node_count()
182        );
183        assert!(
184            ia_graph.edge_count() > fsa_graph.edge_count(),
185            "IA graph ({} edges) should have more edges than FSA graph ({} edges)",
186            ia_graph.edge_count(),
187            fsa_graph.edge_count()
188        );
189    }
190}
datasynth_audit_optimizer/graph.rs

datasynth_audit_optimizer/
graph.rs
