fabryk_graph/
validation.rs

1//! Graph validation and integrity checking.
2//!
3//! Provides functions to validate graph structure and detect issues
4//! such as orphan nodes, self-loops, duplicate edges, prerequisite
5//! cycles, and invalid canonical references.
6
7use crate::{GraphData, Relationship};
8use petgraph::Direction;
9use serde::{Deserialize, Serialize};
10use std::collections::HashSet;
11
12// ============================================================================
13// Types
14// ============================================================================
15
16/// Result of graph validation.
17#[derive(Clone, Debug, Serialize, Deserialize)]
18pub struct ValidationResult {
19    /// Whether the graph is valid (no critical issues).
20    pub valid: bool,
21    /// Critical issues that should be fixed.
22    pub errors: Vec<ValidationIssue>,
23    /// Non-critical issues (warnings).
24    pub warnings: Vec<ValidationIssue>,
25    /// Informational findings.
26    pub info: Vec<ValidationIssue>,
27}
28
29impl ValidationResult {
30    /// Create a new empty (valid) result.
31    pub fn new() -> Self {
32        Self {
33            valid: true,
34            errors: Vec::new(),
35            warnings: Vec::new(),
36            info: Vec::new(),
37        }
38    }
39
40    /// Add an error (marks graph as invalid).
41    pub fn add_error(&mut self, issue: ValidationIssue) {
42        self.valid = false;
43        self.errors.push(issue);
44    }
45
46    /// Add a warning.
47    pub fn add_warning(&mut self, issue: ValidationIssue) {
48        self.warnings.push(issue);
49    }
50
51    /// Add an informational finding.
52    pub fn add_info(&mut self, issue: ValidationIssue) {
53        self.info.push(issue);
54    }
55
56    /// Total issue count (errors + warnings).
57    pub fn total_issues(&self) -> usize {
58        self.errors.len() + self.warnings.len()
59    }
60}
61
62impl Default for ValidationResult {
63    fn default() -> Self {
64        Self::new()
65    }
66}
67
68/// A validation issue found in the graph.
69#[derive(Clone, Debug, Serialize, Deserialize)]
70pub struct ValidationIssue {
71    /// Issue type/code.
72    pub code: String,
73    /// Human-readable message.
74    pub message: String,
75    /// Affected node IDs (if applicable).
76    pub nodes: Vec<String>,
77    /// Affected edge descriptions (if applicable).
78    pub edges: Vec<String>,
79}
80
81impl ValidationIssue {
82    /// Create a new issue.
83    pub fn new(code: impl Into<String>, message: impl Into<String>) -> Self {
84        Self {
85            code: code.into(),
86            message: message.into(),
87            nodes: Vec::new(),
88            edges: Vec::new(),
89        }
90    }
91
92    /// Attach affected nodes.
93    pub fn with_nodes(mut self, nodes: Vec<String>) -> Self {
94        self.nodes = nodes;
95        self
96    }
97
98    /// Attach affected edges.
99    pub fn with_edges(mut self, edges: Vec<String>) -> Self {
100        self.edges = edges;
101        self
102    }
103}
104
105// ============================================================================
106// Validation functions
107// ============================================================================
108
109/// Validate a graph for common issues.
110///
111/// Checks for:
112/// - Orphan nodes (no connections)
113/// - Self-loops (edge from node to itself)
114/// - Duplicate edges (same from, to, relationship)
115/// - Prerequisite cycles
116/// - Missing canonical references
117pub fn validate_graph(graph: &GraphData) -> ValidationResult {
118    let mut result = ValidationResult::new();
119
120    check_orphans(graph, &mut result);
121    check_self_loops(graph, &mut result);
122    check_duplicate_edges(graph, &mut result);
123    check_prerequisite_cycles(graph, &mut result);
124    check_canonical_references(graph, &mut result);
125
126    result
127}
128
129/// Quick check if graph has any validation errors.
130pub fn is_valid(graph: &GraphData) -> bool {
131    validate_graph(graph).valid
132}
133
134// ============================================================================
135// Individual checks
136// ============================================================================
137
138/// Check for orphan nodes (no incoming or outgoing edges).
139fn check_orphans(graph: &GraphData, result: &mut ValidationResult) {
140    let orphans: Vec<String> = graph
141        .iter_nodes()
142        .filter(|node| {
143            if let Some(idx) = graph.get_index(&node.id) {
144                let in_count = graph.graph.edges_directed(idx, Direction::Incoming).count();
145                let out_count = graph.graph.edges_directed(idx, Direction::Outgoing).count();
146                in_count == 0 && out_count == 0
147            } else {
148                false
149            }
150        })
151        .map(|node| node.id.clone())
152        .collect();
153
154    if !orphans.is_empty() {
155        result.add_warning(
156            ValidationIssue::new(
157                "ORPHAN_NODES",
158                format!("{} node(s) have no connections", orphans.len()),
159            )
160            .with_nodes(orphans),
161        );
162    }
163}
164
165/// Check for self-loops (edges from a node to itself).
166fn check_self_loops(graph: &GraphData, result: &mut ValidationResult) {
167    let self_loops: Vec<String> = graph
168        .iter_edges()
169        .filter(|edge| edge.from == edge.to)
170        .map(|edge| format!("{} -> {}", edge.from, edge.to))
171        .collect();
172
173    if !self_loops.is_empty() {
174        result.add_error(
175            ValidationIssue::new(
176                "SELF_LOOPS",
177                format!("{} edge(s) are self-loops", self_loops.len()),
178            )
179            .with_edges(self_loops),
180        );
181    }
182}
183
184/// Check for duplicate edges (same from, to, and relationship).
185fn check_duplicate_edges(graph: &GraphData, result: &mut ValidationResult) {
186    let mut seen: HashSet<(String, String, String)> = HashSet::new();
187    let mut duplicates: Vec<String> = Vec::new();
188
189    for edge in graph.iter_edges() {
190        let key = (
191            edge.from.clone(),
192            edge.to.clone(),
193            edge.relationship.name().to_string(),
194        );
195        if !seen.insert(key) {
196            duplicates.push(format!(
197                "{} -[{}]-> {}",
198                edge.from,
199                edge.relationship.name(),
200                edge.to
201            ));
202        }
203    }
204
205    if !duplicates.is_empty() {
206        result.add_warning(
207            ValidationIssue::new(
208                "DUPLICATE_EDGES",
209                format!("{} duplicate edge(s) found", duplicates.len()),
210            )
211            .with_edges(duplicates),
212        );
213    }
214}
215
216/// Check for cycles in prerequisite relationships.
217fn check_prerequisite_cycles(graph: &GraphData, result: &mut ValidationResult) {
218    use petgraph::algo::toposort;
219    use petgraph::graph::DiGraph;
220    use std::collections::HashMap;
221
222    // Build a subgraph with only prerequisite edges
223    let mut prereq_graph: DiGraph<String, ()> = DiGraph::new();
224    let mut indices: HashMap<String, petgraph::graph::NodeIndex> = HashMap::new();
225
226    for node in graph.iter_nodes() {
227        let idx = prereq_graph.add_node(node.id.clone());
228        indices.insert(node.id.clone(), idx);
229    }
230
231    for edge in graph.iter_edges() {
232        if edge.relationship == Relationship::Prerequisite
233            && let (Some(&from_idx), Some(&to_idx)) =
234                (indices.get(&edge.from), indices.get(&edge.to))
235        {
236            prereq_graph.add_edge(from_idx, to_idx, ());
237        }
238    }
239
240    if toposort(&prereq_graph, None).is_err() {
241        result.add_error(ValidationIssue::new(
242            "PREREQUISITE_CYCLE",
243            "Cycle detected in prerequisite relationships",
244        ));
245    }
246}
247
248/// Check that variant nodes reference valid canonical nodes.
249fn check_canonical_references(graph: &GraphData, result: &mut ValidationResult) {
250    let mut invalid_refs: Vec<String> = Vec::new();
251
252    for node in graph.iter_nodes() {
253        if !node.is_canonical {
254            if let Some(ref canonical_id) = node.canonical_id {
255                if !graph.contains_node(canonical_id) {
256                    invalid_refs.push(format!(
257                        "{} references missing canonical {}",
258                        node.id, canonical_id
259                    ));
260                }
261            } else {
262                invalid_refs.push(format!(
263                    "{} is non-canonical but has no canonical_id",
264                    node.id
265                ));
266            }
267        }
268    }
269
270    if !invalid_refs.is_empty() {
271        result.add_error(
272            ValidationIssue::new(
273                "INVALID_CANONICAL_REF",
274                format!("{} invalid canonical reference(s)", invalid_refs.len()),
275            )
276            .with_nodes(invalid_refs),
277        );
278    }
279}
280
281// ============================================================================
282// Tests
283// ============================================================================
284
285#[cfg(test)]
286mod tests {
287    use super::*;
288    use crate::types::*;
289
290    fn create_valid_graph() -> GraphData {
291        let mut graph = GraphData::new();
292
293        graph.add_node(Node::new("a", "A").with_category("basics"));
294        graph.add_node(Node::new("b", "B").with_category("basics"));
295        graph.add_node(Node::new("c", "C").with_category("advanced"));
296
297        graph
298            .add_edge(Edge::new("a", "b", Relationship::Prerequisite))
299            .unwrap();
300        graph
301            .add_edge(Edge::new("b", "c", Relationship::LeadsTo))
302            .unwrap();
303
304        graph
305    }
306
307    // ------------------------------------------------------------------------
308    // Full validation
309    // ------------------------------------------------------------------------
310
311    #[test]
312    fn test_validate_valid_graph() {
313        let graph = create_valid_graph();
314        let result = validate_graph(&graph);
315
316        assert!(result.valid);
317        assert!(result.errors.is_empty());
318        assert!(result.warnings.is_empty());
319    }
320
321    #[test]
322    fn test_validate_empty_graph() {
323        let graph = GraphData::new();
324        let result = validate_graph(&graph);
325
326        assert!(result.valid);
327        assert!(result.errors.is_empty());
328    }
329
330    #[test]
331    fn test_is_valid_helper() {
332        let graph = create_valid_graph();
333        assert!(is_valid(&graph));
334    }
335
336    // ------------------------------------------------------------------------
337    // Orphan detection
338    // ------------------------------------------------------------------------
339
340    #[test]
341    fn test_orphan_detection() {
342        let mut graph = create_valid_graph();
343        graph.add_node(Node::new("orphan", "Orphan"));
344
345        let result = validate_graph(&graph);
346
347        assert!(result.valid); // orphans are warnings, not errors
348        assert_eq!(result.warnings.len(), 1);
349        assert_eq!(result.warnings[0].code, "ORPHAN_NODES");
350        assert!(result.warnings[0].nodes.contains(&"orphan".to_string()));
351    }
352
353    #[test]
354    fn test_no_orphans() {
355        let graph = create_valid_graph();
356        let result = validate_graph(&graph);
357
358        assert!(result.warnings.iter().all(|w| w.code != "ORPHAN_NODES"));
359    }
360
361    // ------------------------------------------------------------------------
362    // Self-loop detection
363    // ------------------------------------------------------------------------
364
365    #[test]
366    fn test_self_loop_detection() {
367        let mut graph = GraphData::new();
368        graph.add_node(Node::new("a", "A"));
369        graph.add_node(Node::new("b", "B"));
370
371        graph
372            .add_edge(Edge::new("a", "b", Relationship::Prerequisite))
373            .unwrap();
374        graph
375            .add_edge(Edge::new("a", "a", Relationship::RelatesTo))
376            .unwrap();
377
378        let result = validate_graph(&graph);
379
380        assert!(!result.valid);
381        assert!(result.errors.iter().any(|e| e.code == "SELF_LOOPS"));
382        assert_eq!(
383            result
384                .errors
385                .iter()
386                .find(|e| e.code == "SELF_LOOPS")
387                .unwrap()
388                .edges
389                .len(),
390            1
391        );
392    }
393
394    #[test]
395    fn test_no_self_loops() {
396        let graph = create_valid_graph();
397        let result = validate_graph(&graph);
398
399        assert!(!result.errors.iter().any(|e| e.code == "SELF_LOOPS"));
400    }
401
402    // ------------------------------------------------------------------------
403    // Duplicate edge detection
404    // ------------------------------------------------------------------------
405
406    #[test]
407    fn test_duplicate_edge_detection() {
408        let mut graph = GraphData::new();
409        graph.add_node(Node::new("a", "A"));
410        graph.add_node(Node::new("b", "B"));
411
412        // Add same edge twice
413        graph
414            .add_edge(Edge::new("a", "b", Relationship::Prerequisite))
415            .unwrap();
416        graph
417            .add_edge(Edge::new("a", "b", Relationship::Prerequisite))
418            .unwrap();
419
420        let result = validate_graph(&graph);
421
422        assert!(result.warnings.iter().any(|w| w.code == "DUPLICATE_EDGES"));
423    }
424
425    #[test]
426    fn test_different_relationship_not_duplicate() {
427        let mut graph = GraphData::new();
428        graph.add_node(Node::new("a", "A"));
429        graph.add_node(Node::new("b", "B"));
430
431        // Same nodes, different relationships — not duplicates
432        graph
433            .add_edge(Edge::new("a", "b", Relationship::Prerequisite))
434            .unwrap();
435        graph
436            .add_edge(Edge::new("a", "b", Relationship::RelatesTo))
437            .unwrap();
438
439        let result = validate_graph(&graph);
440
441        assert!(!result.warnings.iter().any(|w| w.code == "DUPLICATE_EDGES"));
442    }
443
444    // ------------------------------------------------------------------------
445    // Prerequisite cycle detection
446    // ------------------------------------------------------------------------
447
448    #[test]
449    fn test_prerequisite_cycle_detection() {
450        let mut graph = GraphData::new();
451        graph.add_node(Node::new("a", "A"));
452        graph.add_node(Node::new("b", "B"));
453
454        // a -> b and b -> a (cycle)
455        graph
456            .add_edge(Edge::new("a", "b", Relationship::Prerequisite))
457            .unwrap();
458        graph
459            .add_edge(Edge::new("b", "a", Relationship::Prerequisite))
460            .unwrap();
461
462        let result = validate_graph(&graph);
463
464        assert!(!result.valid);
465        assert!(result.errors.iter().any(|e| e.code == "PREREQUISITE_CYCLE"));
466    }
467
468    #[test]
469    fn test_non_prerequisite_cycle_ok() {
470        let mut graph = GraphData::new();
471        graph.add_node(Node::new("a", "A"));
472        graph.add_node(Node::new("b", "B"));
473
474        // Cycle in RelatesTo is fine (only Prerequisite cycles are errors)
475        graph
476            .add_edge(Edge::new("a", "b", Relationship::RelatesTo))
477            .unwrap();
478        graph
479            .add_edge(Edge::new("b", "a", Relationship::RelatesTo))
480            .unwrap();
481
482        let result = validate_graph(&graph);
483
484        assert!(!result.errors.iter().any(|e| e.code == "PREREQUISITE_CYCLE"));
485    }
486
487    #[test]
488    fn test_no_prerequisite_cycles() {
489        let graph = create_valid_graph();
490        let result = validate_graph(&graph);
491
492        assert!(!result.errors.iter().any(|e| e.code == "PREREQUISITE_CYCLE"));
493    }
494
495    // ------------------------------------------------------------------------
496    // Canonical reference validation
497    // ------------------------------------------------------------------------
498
499    #[test]
500    fn test_valid_canonical_reference() {
501        let mut graph = GraphData::new();
502        graph.add_node(Node::new("canonical", "Canonical Concept"));
503        graph.add_node(Node::new("variant", "Variant").as_variant_of("canonical"));
504
505        let result = validate_graph(&graph);
506
507        assert!(
508            !result
509                .errors
510                .iter()
511                .any(|e| e.code == "INVALID_CANONICAL_REF")
512        );
513    }
514
515    #[test]
516    fn test_missing_canonical_reference() {
517        let mut graph = GraphData::new();
518        graph.add_node(Node::new("variant", "Variant").as_variant_of("missing-canonical"));
519
520        let result = validate_graph(&graph);
521
522        assert!(!result.valid);
523        assert!(
524            result
525                .errors
526                .iter()
527                .any(|e| e.code == "INVALID_CANONICAL_REF")
528        );
529    }
530
531    #[test]
532    fn test_non_canonical_without_canonical_id() {
533        let mut graph = GraphData::new();
534        let mut node = Node::new("bad", "Bad Node");
535        node.is_canonical = false;
536        node.canonical_id = None;
537        graph.add_node(node);
538
539        let result = validate_graph(&graph);
540
541        assert!(!result.valid);
542        assert!(
543            result
544                .errors
545                .iter()
546                .any(|e| e.code == "INVALID_CANONICAL_REF")
547        );
548    }
549
550    // ------------------------------------------------------------------------
551    // ValidationResult API
552    // ------------------------------------------------------------------------
553
554    #[test]
555    fn test_validation_result_new() {
556        let result = ValidationResult::new();
557
558        assert!(result.valid);
559        assert!(result.errors.is_empty());
560        assert!(result.warnings.is_empty());
561        assert!(result.info.is_empty());
562        assert_eq!(result.total_issues(), 0);
563    }
564
565    #[test]
566    fn test_validation_result_add_error() {
567        let mut result = ValidationResult::new();
568        result.add_error(ValidationIssue::new("TEST", "test error"));
569
570        assert!(!result.valid);
571        assert_eq!(result.errors.len(), 1);
572        assert_eq!(result.total_issues(), 1);
573    }
574
575    #[test]
576    fn test_validation_result_add_warning() {
577        let mut result = ValidationResult::new();
578        result.add_warning(ValidationIssue::new("TEST", "test warning"));
579
580        assert!(result.valid); // warnings don't invalidate
581        assert_eq!(result.warnings.len(), 1);
582        assert_eq!(result.total_issues(), 1);
583    }
584
585    #[test]
586    fn test_validation_result_add_info() {
587        let mut result = ValidationResult::new();
588        result.add_info(ValidationIssue::new("TEST", "test info"));
589
590        assert!(result.valid);
591        assert_eq!(result.info.len(), 1);
592        assert_eq!(result.total_issues(), 0); // info not counted
593    }
594
595    #[test]
596    fn test_validation_result_default() {
597        let result = ValidationResult::default();
598        assert!(result.valid);
599    }
600
601    // ------------------------------------------------------------------------
602    // ValidationIssue API
603    // ------------------------------------------------------------------------
604
605    #[test]
606    fn test_validation_issue_builder() {
607        let issue = ValidationIssue::new("CODE", "message")
608            .with_nodes(vec!["a".to_string(), "b".to_string()])
609            .with_edges(vec!["a -> b".to_string()]);
610
611        assert_eq!(issue.code, "CODE");
612        assert_eq!(issue.message, "message");
613        assert_eq!(issue.nodes.len(), 2);
614        assert_eq!(issue.edges.len(), 1);
615    }
616
617    #[test]
618    fn test_validation_issue_serialization() {
619        let issue =
620            ValidationIssue::new("TEST", "test message").with_nodes(vec!["node1".to_string()]);
621
622        let json = serde_json::to_string(&issue).unwrap();
623        let parsed: ValidationIssue = serde_json::from_str(&json).unwrap();
624
625        assert_eq!(parsed.code, "TEST");
626        assert_eq!(parsed.nodes.len(), 1);
627    }
628
629    #[test]
630    fn test_validation_result_serialization() {
631        let mut result = ValidationResult::new();
632        result.add_error(ValidationIssue::new("ERR", "error"));
633        result.add_warning(ValidationIssue::new("WARN", "warning"));
634
635        let json = serde_json::to_string(&result).unwrap();
636        let parsed: ValidationResult = serde_json::from_str(&json).unwrap();
637
638        assert!(!parsed.valid);
639        assert_eq!(parsed.errors.len(), 1);
640        assert_eq!(parsed.warnings.len(), 1);
641    }
642}
fabryk_graph/validation.rs

fabryk_graph/
validation.rs
