oxirs_core/model/
graph.rs

1//! RDF Graph implementation
2
3use crate::model::{Object, Predicate, Subject, Triple, TripleRef};
4use std::collections::HashSet;
5use std::iter::FromIterator;
6
7/// An in-memory RDF Graph
8///
9/// A graph is a set of RDF triples representing a collection of statements.
10/// This implementation uses a HashSet for efficient insertion, removal, and
11/// lookup operations with O(1) average-case performance.
12///
13/// # Examples
14///
15/// ```rust
16/// use oxirs_core::model::{Graph, Triple, NamedNode, Literal};
17///
18/// // Create a new empty graph
19/// let mut graph = Graph::new();
20///
21/// // Create some triples
22/// let triple1 = Triple::new(
23///     NamedNode::new("http://example.org/alice").expect("valid IRI"),
24///     NamedNode::new("http://example.org/name").expect("valid IRI"),
25///     Literal::new("Alice"),
26/// );
27///
28/// let triple2 = Triple::new(
29///     NamedNode::new("http://example.org/alice").expect("valid IRI"),
30///     NamedNode::new("http://example.org/age").expect("valid IRI"),
31///     Literal::new("30"),
32/// );
33///
34/// // Insert triples into the graph
35/// graph.insert(triple1.clone());
36/// graph.insert(triple2);
37///
38/// // Check if graph contains a triple
39/// assert_eq!(graph.len(), 2);
40/// assert!(graph.contains(&triple1));
41/// ```
42///
43/// # Performance Characteristics
44///
45/// - **Insertion**: O(1) average case
46/// - **Removal**: O(1) average case  
47/// - **Lookup**: O(1) average case
48/// - **Memory**: Each triple stored once (set semantics)
49#[derive(Debug, Clone, PartialEq, Eq)]
50pub struct Graph {
51    triples: HashSet<Triple>,
52}
53
54impl Graph {
55    /// Creates a new empty graph
56    ///
57    /// # Examples
58    ///
59    /// ```rust
60    /// use oxirs_core::model::Graph;
61    ///
62    /// let graph = Graph::new();
63    /// assert_eq!(graph.len(), 0);
64    /// assert!(graph.is_empty());
65    /// ```
66    pub fn new() -> Self {
67        Graph {
68            triples: HashSet::new(),
69        }
70    }
71
72    /// Creates a new graph with the specified initial capacity
73    ///
74    /// This can improve performance when you know approximately how many
75    /// triples the graph will contain, as it avoids unnecessary reallocations.
76    ///
77    /// # Arguments
78    ///
79    /// * `capacity` - The initial capacity for the underlying hash set
80    ///
81    /// # Examples
82    ///
83    /// ```rust
84    /// use oxirs_core::model::Graph;
85    ///
86    /// // Create a graph optimized for ~1000 triples
87    /// let graph = Graph::with_capacity(1000);
88    /// assert_eq!(graph.len(), 0);
89    /// ```
90    pub fn with_capacity(capacity: usize) -> Self {
91        Graph {
92            triples: HashSet::with_capacity(capacity),
93        }
94    }
95
96    /// Creates a graph from a vector of triples
97    ///
98    /// Duplicates are automatically removed as graphs maintain set semantics.
99    ///
100    /// # Arguments
101    ///
102    /// * `triples` - A vector of triples to insert into the graph
103    ///
104    /// # Examples
105    ///
106    /// ```rust
107    /// use oxirs_core::model::{Graph, Triple, NamedNode, Literal};
108    ///
109    /// let triples = vec![
110    ///     Triple::new(
111    ///         NamedNode::new("http://example.org/alice").expect("valid IRI"),
112    ///         NamedNode::new("http://example.org/name").expect("valid IRI"),
113    ///         Literal::new("Alice"),
114    ///     ),
115    ///     Triple::new(
116    ///         NamedNode::new("http://example.org/bob").expect("valid IRI"),
117    ///         NamedNode::new("http://example.org/name").expect("valid IRI"),
118    ///         Literal::new("Bob"),
119    ///     ),
120    /// ];
121    ///
122    /// let graph = Graph::from_triples(triples);
123    /// assert_eq!(graph.len(), 2);
124    /// ```
125    pub fn from_triples(triples: Vec<Triple>) -> Self {
126        Graph {
127            triples: triples.into_iter().collect(),
128        }
129    }
130
131    /// Inserts a triple into the graph
132    ///
133    /// Returns `true` if the triple was not already present, `false` otherwise.
134    pub fn insert(&mut self, triple: Triple) -> bool {
135        self.triples.insert(triple)
136    }
137
138    /// Removes a triple from the graph
139    ///
140    /// Returns `true` if the triple was present, `false` otherwise.
141    pub fn remove(&mut self, triple: &Triple) -> bool {
142        self.triples.remove(triple)
143    }
144
145    /// Returns `true` if the graph contains the specified triple
146    pub fn contains(&self, triple: &Triple) -> bool {
147        self.triples.contains(triple)
148    }
149
150    /// Returns the number of triples in the graph
151    pub fn len(&self) -> usize {
152        self.triples.len()
153    }
154
155    /// Returns `true` if the graph contains no triples
156    pub fn is_empty(&self) -> bool {
157        self.triples.is_empty()
158    }
159
160    /// Clears the graph, removing all triples
161    pub fn clear(&mut self) {
162        self.triples.clear();
163    }
164
165    /// Returns an iterator over all triples in the graph
166    pub fn iter(&self) -> impl Iterator<Item = &Triple> {
167        self.triples.iter()
168    }
169
170    /// Returns an iterator over all triples in the graph as references
171    pub fn iter_ref(&self) -> impl Iterator<Item = TripleRef<'_>> {
172        self.triples.iter().map(|t| t.into())
173    }
174
175    /// Finds all triples matching the given pattern
176    ///
177    /// `None` values in the pattern act as wildcards.
178    pub fn triples_for_pattern<'a>(
179        &'a self,
180        subject: Option<&'a Subject>,
181        predicate: Option<&'a Predicate>,
182        object: Option<&'a Object>,
183    ) -> impl Iterator<Item = &'a Triple> {
184        self.triples.iter().filter(move |triple| {
185            if let Some(s) = subject {
186                if triple.subject() != s {
187                    return false;
188                }
189            }
190            if let Some(p) = predicate {
191                if triple.predicate() != p {
192                    return false;
193                }
194            }
195            if let Some(o) = object {
196                if triple.object() != o {
197                    return false;
198                }
199            }
200            true
201        })
202    }
203
204    /// Finds all triples with the given subject
205    pub fn triples_for_subject<'a>(
206        &'a self,
207        subject: &'a Subject,
208    ) -> impl Iterator<Item = &'a Triple> {
209        self.triples_for_pattern(Some(subject), None, None)
210    }
211
212    /// Finds all triples with the given predicate
213    pub fn triples_for_predicate<'a>(
214        &'a self,
215        predicate: &'a Predicate,
216    ) -> impl Iterator<Item = &'a Triple> {
217        self.triples_for_pattern(None, Some(predicate), None)
218    }
219
220    /// Finds all triples with the given object
221    pub fn triples_for_object<'a>(
222        &'a self,
223        object: &'a Object,
224    ) -> impl Iterator<Item = &'a Triple> {
225        self.triples_for_pattern(None, None, Some(object))
226    }
227
228    /// Finds all triples with the given subject and predicate
229    pub fn triples_for_subject_predicate<'a>(
230        &'a self,
231        subject: &'a Subject,
232        predicate: &'a Predicate,
233    ) -> impl Iterator<Item = &'a Triple> {
234        self.triples_for_pattern(Some(subject), Some(predicate), None)
235    }
236
237    /// Extends the graph with triples from an iterator
238    pub fn extend<I>(&mut self, triples: I)
239    where
240        I: IntoIterator<Item = Triple>,
241    {
242        self.triples.extend(triples);
243    }
244
245    /// Retains only the triples specified by the predicate
246    pub fn retain<F>(&mut self, f: F)
247    where
248        F: FnMut(&Triple) -> bool,
249    {
250        self.triples.retain(f);
251    }
252
253    /// Creates the union of this graph with another graph
254    pub fn union(&self, other: &Graph) -> Graph {
255        let mut result = self.clone();
256        result.triples.extend(other.triples.iter().cloned());
257        result
258    }
259
260    /// Creates the intersection of this graph with another graph
261    pub fn intersection(&self, other: &Graph) -> Graph {
262        Graph {
263            triples: self.triples.intersection(&other.triples).cloned().collect(),
264        }
265    }
266
267    /// Creates the difference of this graph with another graph
268    pub fn difference(&self, other: &Graph) -> Graph {
269        Graph {
270            triples: self.triples.difference(&other.triples).cloned().collect(),
271        }
272    }
273
274    /// Returns `true` if this graph is a subset of another graph
275    pub fn is_subset(&self, other: &Graph) -> bool {
276        self.triples.is_subset(&other.triples)
277    }
278
279    /// Returns `true` if this graph is a superset of another graph
280    pub fn is_superset(&self, other: &Graph) -> bool {
281        self.triples.is_superset(&other.triples)
282    }
283
284    /// Returns `true` if this graph is disjoint from another graph
285    pub fn is_disjoint(&self, other: &Graph) -> bool {
286        self.triples.is_disjoint(&other.triples)
287    }
288}
289
290impl Default for Graph {
291    fn default() -> Self {
292        Self::new()
293    }
294}
295
296impl FromIterator<Triple> for Graph {
297    fn from_iter<T: IntoIterator<Item = Triple>>(iter: T) -> Self {
298        Graph {
299            triples: HashSet::from_iter(iter),
300        }
301    }
302}
303
304impl Extend<Triple> for Graph {
305    fn extend<T: IntoIterator<Item = Triple>>(&mut self, iter: T) {
306        self.triples.extend(iter);
307    }
308}
309
310impl IntoIterator for Graph {
311    type Item = Triple;
312    type IntoIter = std::collections::hash_set::IntoIter<Triple>;
313
314    fn into_iter(self) -> Self::IntoIter {
315        self.triples.into_iter()
316    }
317}
318
319impl<'a> IntoIterator for &'a Graph {
320    type Item = &'a Triple;
321    type IntoIter = std::collections::hash_set::Iter<'a, Triple>;
322
323    fn into_iter(self) -> Self::IntoIter {
324        self.triples.iter()
325    }
326}
327
328#[cfg(test)]
329mod tests {
330    use super::*;
331    use crate::model::{Literal, NamedNode};
332
333    fn create_test_triple() -> Triple {
334        let subject = NamedNode::new("http://example.org/subject").expect("valid IRI");
335        let predicate = NamedNode::new("http://example.org/predicate").expect("valid IRI");
336        let object = Literal::new("object");
337        Triple::new(subject, predicate, object)
338    }
339
340    #[test]
341    fn test_graph_basic_operations() {
342        let mut graph = Graph::new();
343        let triple = create_test_triple();
344
345        assert!(graph.is_empty());
346        assert_eq!(graph.len(), 0);
347
348        assert!(graph.insert(triple.clone()));
349        assert!(!graph.is_empty());
350        assert_eq!(graph.len(), 1);
351        assert!(graph.contains(&triple));
352
353        assert!(!graph.insert(triple.clone())); // Already exists
354        assert_eq!(graph.len(), 1);
355
356        assert!(graph.remove(&triple));
357        assert!(graph.is_empty());
358        assert_eq!(graph.len(), 0);
359        assert!(!graph.contains(&triple));
360    }
361
362    #[test]
363    fn test_graph_iteration() {
364        let mut graph = Graph::new();
365        let triple1 = create_test_triple();
366
367        let subject2 = NamedNode::new("http://example.org/subject2").expect("valid IRI");
368        let predicate2 = NamedNode::new("http://example.org/predicate2").expect("valid IRI");
369        let object2 = Literal::new("object2");
370        let triple2 = Triple::new(subject2, predicate2, object2);
371
372        graph.insert(triple1.clone());
373        graph.insert(triple2.clone());
374
375        let mut collected: Vec<_> = graph.iter().cloned().collect();
376        collected.sort_by_key(|t| format!("{t}"));
377
378        assert_eq!(collected.len(), 2);
379        assert!(collected.contains(&triple1));
380        assert!(collected.contains(&triple2));
381    }
382
383    #[test]
384    fn test_graph_pattern_matching() {
385        let mut graph = Graph::new();
386
387        let subject = NamedNode::new("http://example.org/subject").expect("valid IRI");
388        let predicate1 = NamedNode::new("http://example.org/predicate1").expect("valid IRI");
389        let predicate2 = NamedNode::new("http://example.org/predicate2").expect("valid IRI");
390        let object1 = Literal::new("object1");
391        let object2 = Literal::new("object2");
392
393        let triple1 = Triple::new(subject.clone(), predicate1.clone(), object1);
394        let triple2 = Triple::new(subject.clone(), predicate2, object2);
395
396        graph.insert(triple1.clone());
397        graph.insert(triple2.clone());
398
399        // Find by subject
400        let by_subject: Vec<_> = graph
401            .triples_for_subject(&Subject::NamedNode(subject.clone()))
402            .cloned()
403            .collect();
404        assert_eq!(by_subject.len(), 2);
405
406        // Find by predicate
407        let by_predicate: Vec<_> = graph
408            .triples_for_predicate(&Predicate::NamedNode(predicate1))
409            .cloned()
410            .collect();
411        assert_eq!(by_predicate.len(), 1);
412        assert_eq!(by_predicate[0], triple1);
413    }
414
415    #[test]
416    fn test_graph_set_operations() {
417        let mut graph1 = Graph::new();
418        let mut graph2 = Graph::new();
419
420        let triple1 = create_test_triple();
421        let subject2 = NamedNode::new("http://example.org/subject2").expect("valid IRI");
422        let predicate2 = NamedNode::new("http://example.org/predicate2").expect("valid IRI");
423        let object2 = Literal::new("object2");
424        let triple2 = Triple::new(subject2, predicate2, object2);
425
426        graph1.insert(triple1.clone());
427        graph2.insert(triple1.clone());
428        graph2.insert(triple2.clone());
429
430        let union = graph1.union(&graph2);
431        assert_eq!(union.len(), 2);
432
433        let intersection = graph1.intersection(&graph2);
434        assert_eq!(intersection.len(), 1);
435        assert!(intersection.contains(&triple1));
436
437        assert!(graph1.is_subset(&graph2));
438        assert!(!graph1.is_superset(&graph2));
439        assert!(graph2.is_superset(&graph1));
440    }
441}
oxirs_core/model/graph.rs

oxirs_core/model/
graph.rs
