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

oxirs_core/model/
graph.rs
