oxirs_ttl/toolkit/
graph_utils.rs

1//! RDF Graph Utilities
2//!
3//! This module provides utilities for working with RDF graphs, including:
4//! - Graph merging and combining
5//! - Graph comparison and diff generation
6//! - Graph transformation operations
7//! - Graph statistics and analysis
8//!
9//! # Examples
10//!
11//! ## Merging Graphs
12//!
13//! ```rust
14//! use oxirs_ttl::toolkit::graph_utils::GraphMerger;
15//! use oxirs_core::model::{Triple, NamedNode};
16//!
17//! let graph1 = vec![
18//!     Triple::new(
19//!         NamedNode::new("http://example.org/s1")?,
20//!         NamedNode::new("http://example.org/p")?,
21//!         NamedNode::new("http://example.org/o1")?,
22//!     ),
23//! ];
24//!
25//! let graph2 = vec![
26//!     Triple::new(
27//!         NamedNode::new("http://example.org/s2")?,
28//!         NamedNode::new("http://example.org/p")?,
29//!         NamedNode::new("http://example.org/o2")?,
30//!     ),
31//! ];
32//!
33//! let merger = GraphMerger::new();
34//! let merged = merger.merge(&[graph1, graph2]);
35//! assert_eq!(merged.len(), 2);
36//! # Ok::<(), Box<dyn std::error::Error>>(())
37//! ```
38//!
39//! ## Finding Graph Differences
40//!
41//! ```rust
42//! use oxirs_ttl::toolkit::graph_utils::GraphDiff;
43//! use oxirs_core::model::{Triple, NamedNode};
44//!
45//! let graph1 = vec![
46//!     Triple::new(
47//!         NamedNode::new("http://example.org/s")?,
48//!         NamedNode::new("http://example.org/p")?,
49//!         NamedNode::new("http://example.org/o1")?,
50//!     ),
51//! ];
52//!
53//! let graph2 = vec![
54//!     Triple::new(
55//!         NamedNode::new("http://example.org/s")?,
56//!         NamedNode::new("http://example.org/p")?,
57//!         NamedNode::new("http://example.org/o2")?,
58//!     ),
59//! ];
60//!
61//! let diff = GraphDiff::compute(&graph1, &graph2);
62//! assert_eq!(diff.added().len(), 1);
63//! assert_eq!(diff.removed().len(), 1);
64//! # Ok::<(), Box<dyn std::error::Error>>(())
65//! ```
66
67use oxirs_core::model::{Quad, Triple};
68use oxirs_core::RdfTerm;
69use std::collections::{HashMap, HashSet};
70
71/// Graph merger for combining multiple RDF graphs
72///
73/// Provides efficient merging of RDF graphs with deduplication.
74#[derive(Debug, Default)]
75pub struct GraphMerger {
76    deduplicate: bool,
77}
78
79impl GraphMerger {
80    /// Create a new graph merger with default settings
81    pub fn new() -> Self {
82        Self { deduplicate: true }
83    }
84
85    /// Create a merger that allows duplicate triples
86    pub fn with_duplicates() -> Self {
87        Self { deduplicate: false }
88    }
89
90    /// Merge multiple graphs into a single graph
91    ///
92    /// # Example
93    ///
94    /// ```rust
95    /// use oxirs_ttl::toolkit::graph_utils::GraphMerger;
96    ///
97    /// let graphs: Vec<Vec<oxirs_core::model::Triple>> = vec![];
98    /// let merger = GraphMerger::new();
99    /// let merged = merger.merge(&graphs);
100    /// ```
101    pub fn merge(&self, graphs: &[Vec<Triple>]) -> Vec<Triple> {
102        if !self.deduplicate {
103            return graphs.iter().flat_map(|g| g.iter().cloned()).collect();
104        }
105
106        let mut seen = HashSet::new();
107        let mut result = Vec::new();
108
109        for graph in graphs {
110            for triple in graph {
111                if seen.insert(triple.clone()) {
112                    result.push(triple.clone());
113                }
114            }
115        }
116
117        result
118    }
119
120    /// Merge multiple quad graphs
121    pub fn merge_quads(&self, graphs: &[Vec<Quad>]) -> Vec<Quad> {
122        if !self.deduplicate {
123            return graphs.iter().flat_map(|g| g.iter().cloned()).collect();
124        }
125
126        let mut seen = HashSet::new();
127        let mut result = Vec::new();
128
129        for graph in graphs {
130            for quad in graph {
131                if seen.insert(quad.clone()) {
132                    result.push(quad.clone());
133                }
134            }
135        }
136
137        result
138    }
139
140    /// Merge two graphs in-place (modifying the first graph)
141    pub fn merge_into(&self, target: &mut Vec<Triple>, source: &[Triple]) {
142        if !self.deduplicate {
143            target.extend_from_slice(source);
144            return;
145        }
146
147        let existing: HashSet<_> = target.iter().cloned().collect();
148        for triple in source {
149            if !existing.contains(triple) {
150                target.push(triple.clone());
151            }
152        }
153    }
154}
155
156/// Represents differences between two RDF graphs
157#[derive(Debug, Clone)]
158pub struct GraphDiff {
159    added: Vec<Triple>,
160    removed: Vec<Triple>,
161    common: Vec<Triple>,
162}
163
164impl GraphDiff {
165    /// Compute the difference between two graphs
166    ///
167    /// Returns a diff showing triples added, removed, and common to both graphs.
168    pub fn compute(graph1: &[Triple], graph2: &[Triple]) -> Self {
169        let set1: HashSet<_> = graph1.iter().cloned().collect();
170        let set2: HashSet<_> = graph2.iter().cloned().collect();
171
172        let added: Vec<_> = set2.difference(&set1).cloned().collect();
173        let removed: Vec<_> = set1.difference(&set2).cloned().collect();
174        let common: Vec<_> = set1.intersection(&set2).cloned().collect();
175
176        Self {
177            added,
178            removed,
179            common,
180        }
181    }
182
183    /// Get triples that were added in the second graph
184    pub fn added(&self) -> &[Triple] {
185        &self.added
186    }
187
188    /// Get triples that were removed from the first graph
189    pub fn removed(&self) -> &[Triple] {
190        &self.removed
191    }
192
193    /// Get triples common to both graphs
194    pub fn common(&self) -> &[Triple] {
195        &self.common
196    }
197
198    /// Check if the graphs are identical
199    pub fn is_identical(&self) -> bool {
200        self.added.is_empty() && self.removed.is_empty()
201    }
202
203    /// Get the total number of changes (additions + removals)
204    pub fn change_count(&self) -> usize {
205        self.added.len() + self.removed.len()
206    }
207
208    /// Generate a summary of the diff
209    pub fn summary(&self) -> DiffSummary {
210        DiffSummary {
211            added_count: self.added.len(),
212            removed_count: self.removed.len(),
213            common_count: self.common.len(),
214            total_changes: self.change_count(),
215        }
216    }
217}
218
219/// Summary statistics for a graph diff
220#[derive(Debug, Clone, PartialEq, Eq)]
221pub struct DiffSummary {
222    /// Number of triples added
223    pub added_count: usize,
224    /// Number of triples removed
225    pub removed_count: usize,
226    /// Number of triples common to both
227    pub common_count: usize,
228    /// Total number of changes
229    pub total_changes: usize,
230}
231
232impl std::fmt::Display for DiffSummary {
233    fn fmt(&self, f: &mut std::fmt::Formatter<'_>) -> std::fmt::Result {
234        write!(
235            f,
236            "Graph Diff Summary: +{} -{} ={} (total changes: {})",
237            self.added_count, self.removed_count, self.common_count, self.total_changes
238        )
239    }
240}
241
242/// Graph transformation utilities
243#[derive(Debug)]
244pub struct GraphTransformer;
245
246impl GraphTransformer {
247    /// Filter triples by predicate
248    ///
249    /// # Example
250    ///
251    /// ```rust
252    /// use oxirs_ttl::toolkit::graph_utils::GraphTransformer;
253    /// use oxirs_core::model::{Triple, NamedNode};
254    ///
255    /// let triples = vec![
256    ///     Triple::new(
257    ///         NamedNode::new("http://example.org/s")?,
258    ///         NamedNode::new("http://example.org/p1")?,
259    ///         NamedNode::new("http://example.org/o")?,
260    ///     ),
261    ///     Triple::new(
262    ///         NamedNode::new("http://example.org/s")?,
263    ///         NamedNode::new("http://example.org/p2")?,
264    ///         NamedNode::new("http://example.org/o")?,
265    ///     ),
266    /// ];
267    ///
268    /// let filtered = GraphTransformer::filter_by_predicate(
269    ///     &triples,
270    ///     |p| p.ends_with("p1")
271    /// );
272    /// assert_eq!(filtered.len(), 1);
273    /// # Ok::<(), Box<dyn std::error::Error>>(())
274    /// ```
275    pub fn filter_by_predicate<F>(triples: &[Triple], predicate: F) -> Vec<Triple>
276    where
277        F: Fn(&str) -> bool,
278    {
279        triples
280            .iter()
281            .filter(|t| predicate(t.predicate().as_str()))
282            .cloned()
283            .collect()
284    }
285
286    /// Filter triples by subject
287    pub fn filter_by_subject<F>(triples: &[Triple], predicate: F) -> Vec<Triple>
288    where
289        F: Fn(&oxirs_core::model::Subject) -> bool,
290    {
291        triples
292            .iter()
293            .filter(|t| predicate(t.subject()))
294            .cloned()
295            .collect()
296    }
297
298    /// Group triples by subject
299    ///
300    /// Returns a map from subject to all triples with that subject.
301    pub fn group_by_subject(triples: &[Triple]) -> HashMap<String, Vec<Triple>> {
302        let mut groups: HashMap<String, Vec<Triple>> = HashMap::new();
303
304        for triple in triples {
305            let subject_str = triple.subject().to_string();
306            groups.entry(subject_str).or_default().push(triple.clone());
307        }
308
309        groups
310    }
311
312    /// Group triples by predicate
313    pub fn group_by_predicate(triples: &[Triple]) -> HashMap<String, Vec<Triple>> {
314        let mut groups: HashMap<String, Vec<Triple>> = HashMap::new();
315
316        for triple in triples {
317            let predicate_str = triple.predicate().to_string();
318            groups
319                .entry(predicate_str)
320                .or_default()
321                .push(triple.clone());
322        }
323
324        groups
325    }
326
327    /// Get all unique subjects in the graph
328    pub fn unique_subjects(triples: &[Triple]) -> Vec<String> {
329        let subjects: HashSet<_> = triples.iter().map(|t| t.subject().to_string()).collect();
330        subjects.into_iter().collect()
331    }
332
333    /// Get all unique predicates in the graph
334    pub fn unique_predicates(triples: &[Triple]) -> Vec<String> {
335        let predicates: HashSet<_> = triples.iter().map(|t| t.predicate().to_string()).collect();
336        predicates.into_iter().collect()
337    }
338
339    /// Get all unique objects in the graph
340    pub fn unique_objects(triples: &[Triple]) -> Vec<String> {
341        let objects: HashSet<_> = triples.iter().map(|t| t.object().to_string()).collect();
342        objects.into_iter().collect()
343    }
344}
345
346/// Advanced graph statistics
347#[derive(Debug, Clone, PartialEq)]
348pub struct AdvancedGraphStats {
349    /// Total number of triples
350    pub triple_count: usize,
351    /// Number of unique subjects
352    pub unique_subjects: usize,
353    /// Number of unique predicates
354    pub unique_predicates: usize,
355    /// Number of unique objects
356    pub unique_objects: usize,
357    /// Average triples per subject
358    pub avg_triples_per_subject: f64,
359    /// Maximum triples for any subject
360    pub max_triples_per_subject: usize,
361    /// Number of subjects with only one triple
362    pub singleton_subjects: usize,
363    /// Most common predicates (top 10)
364    pub top_predicates: Vec<(String, usize)>,
365}
366
367impl AdvancedGraphStats {
368    /// Compute advanced statistics for a graph
369    ///
370    /// # Example
371    ///
372    /// ```rust
373    /// use oxirs_ttl::toolkit::graph_utils::AdvancedGraphStats;
374    /// use oxirs_core::model::{Triple, NamedNode};
375    ///
376    /// let triples = vec![
377    ///     Triple::new(
378    ///         NamedNode::new("http://example.org/s1")?,
379    ///         NamedNode::new("http://example.org/p")?,
380    ///         NamedNode::new("http://example.org/o1")?,
381    ///     ),
382    ///     Triple::new(
383    ///         NamedNode::new("http://example.org/s1")?,
384    ///         NamedNode::new("http://example.org/p")?,
385    ///         NamedNode::new("http://example.org/o2")?,
386    ///     ),
387    /// ];
388    ///
389    /// let stats = AdvancedGraphStats::compute(&triples);
390    /// assert_eq!(stats.triple_count, 2);
391    /// assert_eq!(stats.unique_subjects, 1);
392    /// # Ok::<(), Box<dyn std::error::Error>>(())
393    /// ```
394    pub fn compute(triples: &[Triple]) -> Self {
395        let triple_count = triples.len();
396
397        // Count unique subjects, predicates, objects
398        let subjects: HashSet<_> = triples.iter().map(|t| t.subject().to_string()).collect();
399        let predicates: HashSet<_> = triples.iter().map(|t| t.predicate().to_string()).collect();
400        let objects: HashSet<_> = triples.iter().map(|t| t.object().to_string()).collect();
401
402        let unique_subjects = subjects.len();
403        let unique_predicates = predicates.len();
404        let unique_objects = objects.len();
405
406        // Group by subject to compute per-subject stats
407        let mut subject_counts: HashMap<String, usize> = HashMap::new();
408        for triple in triples {
409            *subject_counts
410                .entry(triple.subject().to_string())
411                .or_insert(0) += 1;
412        }
413
414        let max_triples_per_subject = subject_counts.values().max().copied().unwrap_or(0);
415        let singleton_subjects = subject_counts.values().filter(|&&c| c == 1).count();
416        let avg_triples_per_subject = if unique_subjects > 0 {
417            triple_count as f64 / unique_subjects as f64
418        } else {
419            0.0
420        };
421
422        // Count predicate frequencies
423        let mut predicate_counts: HashMap<String, usize> = HashMap::new();
424        for triple in triples {
425            *predicate_counts
426                .entry(triple.predicate().to_string())
427                .or_insert(0) += 1;
428        }
429
430        // Get top 10 most common predicates
431        let mut predicate_vec: Vec<_> = predicate_counts.into_iter().collect();
432        predicate_vec.sort_by_key(|b| std::cmp::Reverse(b.1));
433        let top_predicates = predicate_vec.into_iter().take(10).collect();
434
435        Self {
436            triple_count,
437            unique_subjects,
438            unique_predicates,
439            unique_objects,
440            avg_triples_per_subject,
441            max_triples_per_subject,
442            singleton_subjects,
443            top_predicates,
444        }
445    }
446
447    /// Generate a formatted report
448    pub fn report(&self) -> String {
449        let mut report = String::new();
450        report.push_str("=== Advanced Graph Statistics ===\n");
451        report.push_str(&format!("Total triples: {}\n", self.triple_count));
452        report.push_str(&format!("Unique subjects: {}\n", self.unique_subjects));
453        report.push_str(&format!("Unique predicates: {}\n", self.unique_predicates));
454        report.push_str(&format!("Unique objects: {}\n", self.unique_objects));
455        report.push_str(&format!(
456            "Average triples per subject: {:.2}\n",
457            self.avg_triples_per_subject
458        ));
459        report.push_str(&format!(
460            "Max triples per subject: {}\n",
461            self.max_triples_per_subject
462        ));
463        report.push_str(&format!(
464            "Singleton subjects: {}\n",
465            self.singleton_subjects
466        ));
467        report.push_str("\nTop predicates:\n");
468        for (i, (pred, count)) in self.top_predicates.iter().enumerate() {
469            report.push_str(&format!("  {}. {} ({})\n", i + 1, pred, count));
470        }
471        report
472    }
473}
474
475#[cfg(test)]
476mod tests {
477    use super::*;
478    use oxirs_core::model::NamedNode;
479
480    fn create_test_triple(s: &str, p: &str, o: &str) -> Triple {
481        Triple::new(
482            NamedNode::new(s).expect("valid IRI"),
483            NamedNode::new(p).expect("valid IRI"),
484            NamedNode::new(o).expect("valid IRI"),
485        )
486    }
487
488    #[test]
489    fn test_graph_merger() {
490        let graph1 = vec![create_test_triple(
491            "http://example.org/s1",
492            "http://example.org/p",
493            "http://example.org/o",
494        )];
495
496        let graph2 = vec![
497            create_test_triple(
498                "http://example.org/s1",
499                "http://example.org/p",
500                "http://example.org/o",
501            ),
502            create_test_triple(
503                "http://example.org/s2",
504                "http://example.org/p",
505                "http://example.org/o",
506            ),
507        ];
508
509        let merger = GraphMerger::new();
510        let merged = merger.merge(&[graph1, graph2]);
511
512        // Should deduplicate
513        assert_eq!(merged.len(), 2);
514    }
515
516    #[test]
517    fn test_graph_merger_with_duplicates() {
518        let graph1 = vec![create_test_triple(
519            "http://example.org/s",
520            "http://example.org/p",
521            "http://example.org/o",
522        )];
523
524        let graph2 = vec![create_test_triple(
525            "http://example.org/s",
526            "http://example.org/p",
527            "http://example.org/o",
528        )];
529
530        let merger = GraphMerger::with_duplicates();
531        let merged = merger.merge(&[graph1, graph2]);
532
533        // Should NOT deduplicate
534        assert_eq!(merged.len(), 2);
535    }
536
537    #[test]
538    fn test_graph_diff() {
539        let graph1 = vec![
540            create_test_triple(
541                "http://example.org/s",
542                "http://example.org/p1",
543                "http://example.org/o",
544            ),
545            create_test_triple(
546                "http://example.org/s",
547                "http://example.org/p2",
548                "http://example.org/o",
549            ),
550        ];
551
552        let graph2 = vec![
553            create_test_triple(
554                "http://example.org/s",
555                "http://example.org/p2",
556                "http://example.org/o",
557            ),
558            create_test_triple(
559                "http://example.org/s",
560                "http://example.org/p3",
561                "http://example.org/o",
562            ),
563        ];
564
565        let diff = GraphDiff::compute(&graph1, &graph2);
566
567        assert_eq!(diff.added().len(), 1); // p3
568        assert_eq!(diff.removed().len(), 1); // p1
569        assert_eq!(diff.common().len(), 1); // p2
570        assert_eq!(diff.change_count(), 2);
571        assert!(!diff.is_identical());
572    }
573
574    #[test]
575    fn test_graph_transformer_filter() {
576        let triples = vec![
577            create_test_triple(
578                "http://example.org/s",
579                "http://example.org/p1",
580                "http://example.org/o",
581            ),
582            create_test_triple(
583                "http://example.org/s",
584                "http://example.org/p2",
585                "http://example.org/o",
586            ),
587        ];
588
589        let filtered = GraphTransformer::filter_by_predicate(&triples, |p| p.ends_with("p1"));
590
591        assert_eq!(filtered.len(), 1);
592    }
593
594    #[test]
595    fn test_graph_transformer_grouping() {
596        let triples = vec![
597            create_test_triple(
598                "http://example.org/s1",
599                "http://example.org/p",
600                "http://example.org/o1",
601            ),
602            create_test_triple(
603                "http://example.org/s1",
604                "http://example.org/p",
605                "http://example.org/o2",
606            ),
607            create_test_triple(
608                "http://example.org/s2",
609                "http://example.org/p",
610                "http://example.org/o3",
611            ),
612        ];
613
614        let groups = GraphTransformer::group_by_subject(&triples);
615        assert_eq!(groups.len(), 2);
616        assert_eq!(
617            groups
618                .get("<http://example.org/s1>")
619                .expect("key should exist")
620                .len(),
621            2
622        );
623        assert_eq!(
624            groups
625                .get("<http://example.org/s2>")
626                .expect("key should exist")
627                .len(),
628            1
629        );
630    }
631
632    #[test]
633    fn test_advanced_stats() {
634        let triples = vec![
635            create_test_triple(
636                "http://example.org/s1",
637                "http://example.org/p",
638                "http://example.org/o1",
639            ),
640            create_test_triple(
641                "http://example.org/s1",
642                "http://example.org/p",
643                "http://example.org/o2",
644            ),
645            create_test_triple(
646                "http://example.org/s2",
647                "http://example.org/p",
648                "http://example.org/o3",
649            ),
650        ];
651
652        let stats = AdvancedGraphStats::compute(&triples);
653
654        assert_eq!(stats.triple_count, 3);
655        assert_eq!(stats.unique_subjects, 2);
656        assert_eq!(stats.unique_predicates, 1);
657        assert_eq!(stats.unique_objects, 3);
658        assert_eq!(stats.max_triples_per_subject, 2);
659        assert_eq!(stats.singleton_subjects, 1);
660        assert!((stats.avg_triples_per_subject - 1.5).abs() < 0.01);
661    }
662
663    #[test]
664    fn test_unique_extraction() {
665        let triples = vec![
666            create_test_triple(
667                "http://example.org/s1",
668                "http://example.org/p1",
669                "http://example.org/o1",
670            ),
671            create_test_triple(
672                "http://example.org/s1",
673                "http://example.org/p2",
674                "http://example.org/o2",
675            ),
676            create_test_triple(
677                "http://example.org/s2",
678                "http://example.org/p1",
679                "http://example.org/o1",
680            ),
681        ];
682
683        let subjects = GraphTransformer::unique_subjects(&triples);
684        assert_eq!(subjects.len(), 2);
685
686        let predicates = GraphTransformer::unique_predicates(&triples);
687        assert_eq!(predicates.len(), 2);
688
689        let objects = GraphTransformer::unique_objects(&triples);
690        assert_eq!(objects.len(), 2);
691    }
692}
oxirs_ttl/toolkit/graph_utils.rs

oxirs_ttl/toolkit/
graph_utils.rs
