devsper_graph/
validator.rs

1use devsper_core::{GraphMutation, NodeId};
2use petgraph::algo::is_cyclic_directed;
3use petgraph::graph::{DiGraph, NodeIndex};
4use std::collections::HashMap;
5
6/// Validates that graph mutations do not introduce cycles.
7/// Uses petgraph's DFS-based cycle detection.
8pub struct MutationValidator;
9
10impl MutationValidator {
11    pub fn new() -> Self {
12        Self
13    }
14
15    /// Returns Ok(()) if mutation is safe, Err(reason) if it would create a cycle.
16    pub fn validate(
17        &self,
18        graph: &DiGraph<NodeId, ()>,
19        index_map: &HashMap<NodeId, NodeIndex>,
20        mutation: &GraphMutation,
21    ) -> Result<(), String> {
22        match mutation {
23            GraphMutation::AddEdge { from, to } => {
24                self.validate_add_edge(graph, index_map, from, to)
25            }
26            // InjectBefore adds a new node (no incoming edges yet) with one outgoing edge → safe
27            GraphMutation::InjectBefore { .. } => Ok(()),
28            // SplitNode replaces an existing node with new ones — no new cycles possible
29            GraphMutation::SplitNode { .. } => Ok(()),
30            // All other mutations don't add edges
31            _ => Ok(()),
32        }
33    }
34
35    fn validate_add_edge(
36        &self,
37        graph: &DiGraph<NodeId, ()>,
38        index_map: &HashMap<NodeId, NodeIndex>,
39        from: &NodeId,
40        to: &NodeId,
41    ) -> Result<(), String> {
42        let from_idx = index_map
43            .get(from)
44            .copied()
45            .ok_or_else(|| format!("Node not found: {from}"))?;
46        let to_idx = index_map
47            .get(to)
48            .copied()
49            .ok_or_else(|| format!("Node not found: {to}"))?;
50
51        // Clone graph, add edge, check for cycle
52        let mut test_graph = graph.clone();
53        test_graph.add_edge(from_idx, to_idx, ());
54
55        if is_cyclic_directed(&test_graph) {
56            Err(format!("Edge {from} → {to} would create a cycle"))
57        } else {
58            Ok(())
59        }
60    }
61}
62
63impl Default for MutationValidator {
64    fn default() -> Self {
65        Self::new()
66    }
67}
devsper_graph/validator.rs

devsper_graph/
validator.rs
