rust_igraph/core/
cache.rs

1//! Per-graph property cache (ALGO-CORE-001f).
2//!
3//! Counterpart of `igraph_i_property_cache_t` from
4//! `references/igraph/src/graph/caching.{h,c}` and the
5//! `igraph_i_property_cache_*` developer-facing API in
6//! `references/igraph/include/igraph_interface.h:89-94`.
7//!
8//! Stores the value of a small set of boolean graph properties (e.g.
9//! `is_dag`, `is_forest`, `has_loop`) so that repeated calls don't
10//! recompute. The cache lives on `Graph` itself and is invalidated on
11//! any structural mutation; selective invalidation (e.g. *adding* an
12//! edge cannot make a connected graph disconnected) mirrors upstream's
13//! `igraph_i_property_cache_invalidate_conditionally`.
14//!
15//! ## Interior mutability
16//!
17//! igraph C updates the cache through a `const igraph_t *` pointer —
18//! computing a property is not considered "modification" of the graph.
19//! We mirror this with `Cell<u32>`: a property compute function takes
20//! `&Graph` and may still populate the cache. Single-threaded for now;
21//! future multi-thread support would swap to `AtomicU32`.
22//!
23//! ## Storage layout
24//!
25//! Two `u32`s, bit `i` corresponding to [`CachedProperty`] discriminant
26//! `i`:
27//!
28//! - `known` — bit set iff property `i` has a cached value;
29//! - `values` — bit set iff cached value of `i` is `true`.
30//!
31//! Reading `values` is only meaningful when the matching `known` bit
32//! is set; `get` therefore returns `Option<bool>` rather than a raw
33//! pair. This matches the C struct in
34//! `references/igraph/src/graph/caching.h:29-34` exactly (one bit
35//! per property in `known`, one byte per property in C `value[]` —
36//! we bit-pack since Rust gives us free integer arithmetic).
37
38use std::cell::Cell;
39
40/// The set of boolean graph properties that may be cached.
41///
42/// Discriminant values **must stay stable** — they are used as bit
43/// indices into the cache's bitfield. Mirrors the
44/// `igraph_cached_property_t` enum at
45/// `references/igraph/include/igraph_datatype.h:31-64`; the order is
46/// preserved so the C-side reasoning (e.g. "adding an edge keeps
47/// `IS_DAG` if cached false") translates by index.
48#[derive(Debug, Clone, Copy, PartialEq, Eq, Hash)]
49#[repr(u8)]
50pub enum CachedProperty {
51    /// Has at least one self-loop.
52    HasLoop = 0,
53    /// Has at least one multi-edge (direction-aware: `(a,b)` + `(b,a)`
54    /// in a *directed* graph does **not** count as a multi-edge).
55    HasMulti = 1,
56    /// Has at least one reciprocal edge pair (directed graphs only).
57    HasMutual = 2,
58    /// Weakly connected.
59    IsWeaklyConnected = 3,
60    /// Strongly connected (directed graphs only).
61    IsStronglyConnected = 4,
62    /// Directed acyclic graph (directed graphs only).
63    IsDag = 5,
64    /// Forest — acyclic when edge directions are ignored.
65    IsForest = 6,
66}
67
68/// Total number of cached property slots. Must equal
69/// `CachedProperty::all().len()`. We keep a constant rather than
70/// reflecting it dynamically so bitmask compile-time checks are easy.
71pub(crate) const PROP_COUNT: u8 = 7;
72
73impl CachedProperty {
74    #[inline]
75    fn bit(self) -> u32 {
76        1u32 << (self as u8)
77    }
78}
79
80/// Boolean property cache, embedded in [`Graph`](crate::Graph).
81///
82/// Field-private; users interact through `Graph::cache_*` helpers.
83/// Cloned by deep copy — the cached values carry over so a `Graph::clone`
84/// doesn't need to recompute properties on the new copy.
85#[derive(Debug, Clone, Default)]
86pub(crate) struct PropertyCache {
87    /// Bit `i` set iff property `i` has a cached value.
88    known: Cell<u32>,
89    /// Bit `i` set iff cached value of property `i` is `true`. Bits
90    /// where `known` is 0 are meaningless.
91    values: Cell<u32>,
92}
93
94impl PropertyCache {
95    pub(crate) fn new() -> Self {
96        Self::default()
97    }
98
99    pub(crate) fn has(&self, prop: CachedProperty) -> bool {
100        self.known.get() & prop.bit() != 0
101    }
102
103    pub(crate) fn get(&self, prop: CachedProperty) -> Option<bool> {
104        if self.has(prop) {
105            Some(self.values.get() & prop.bit() != 0)
106        } else {
107            None
108        }
109    }
110
111    /// Store `value` for `prop`, overwriting any previous cached value.
112    ///
113    /// Counterpart of `igraph_i_property_cache_set_bool`.
114    pub(crate) fn set(&self, prop: CachedProperty, value: bool) {
115        let bit = prop.bit();
116        self.known.set(self.known.get() | bit);
117        let cur = self.values.get();
118        self.values.set(if value { cur | bit } else { cur & !bit });
119    }
120
121    /// Drop the cached value of `prop` (no-op if not cached).
122    ///
123    /// Counterpart of `igraph_i_property_cache_invalidate`.
124    pub(crate) fn invalidate(&self, prop: CachedProperty) {
125        self.known.set(self.known.get() & !prop.bit());
126    }
127
128    /// Drop every cached value.
129    ///
130    /// Counterpart of `igraph_i_property_cache_invalidate_all`.
131    pub(crate) fn invalidate_all(&self) {
132        self.known.set(0);
133    }
134
135    /// Selective invalidation: drop every cached value **except** those
136    /// listed in `keep_always`, plus those listed in `keep_when_false` /
137    /// `keep_when_true` whose currently-cached value matches.
138    ///
139    /// Mask convention: bit `i` corresponds to
140    /// `1u32 << (CachedProperty::X as u8)`. Use [`CachedProperty::bit`]
141    /// when constructing masks externally — but this is `pub(crate)`, so
142    /// in practice callers go through the higher-level helpers below
143    /// (`invalidate_after_add_edge`, etc.).
144    ///
145    /// Counterpart of `igraph_i_property_cache_invalidate_conditionally`.
146    pub(crate) fn invalidate_conditionally(
147        &self,
148        keep_always: u32,
149        keep_when_false: u32,
150        keep_when_true: u32,
151    ) {
152        let mut invalidate = !keep_always;
153        let known = self.known.get();
154        let values = self.values.get();
155        let maybe_keep = known & invalidate & (keep_when_false | keep_when_true);
156        if maybe_keep != 0 {
157            for i in 0..PROP_COUNT {
158                let mask = 1u32 << i;
159                if maybe_keep & mask != 0 {
160                    let cached_value = values & mask != 0;
161                    if (keep_when_false & mask != 0 && !cached_value)
162                        || (keep_when_true & mask != 0 && cached_value)
163                    {
164                        invalidate &= !mask;
165                    }
166                }
167            }
168        }
169        self.known.set(known & !invalidate);
170    }
171}
172
173// ----- pre-baked invalidation policies ---------------------------------------
174
175/// After [`Graph::add_vertices`](crate::Graph::add_vertices): adding
176/// isolated vertices cannot affect any edge-level property
177/// (`HasLoop`, `HasMulti`, `HasMutual`, `IsDag`, `IsForest` are all
178/// preserved). It can only **break** connectivity (a known-disconnected
179/// graph stays disconnected; a known-connected graph may become
180/// disconnected).
181pub(crate) fn invalidate_after_add_vertices(cache: &PropertyCache) {
182    use CachedProperty::{
183        HasLoop, HasMulti, HasMutual, IsDag, IsForest, IsStronglyConnected, IsWeaklyConnected,
184    };
185    cache.invalidate_conditionally(
186        HasLoop.bit() | HasMulti.bit() | HasMutual.bit() | IsDag.bit() | IsForest.bit(),
187        IsWeaklyConnected.bit() | IsStronglyConnected.bit(),
188        0,
189    );
190}
191
192/// After [`Graph::add_edges`](crate::Graph::add_edges): mirrors the
193/// C policy at `type_indexededgelist.c:341-364`.
194///
195/// - Adding an edge **never** disconnects a connected graph and
196///   **never** removes existing self-loops / multi-edges / reciprocal
197///   pairs → keep `IS_*_CONNECTED`, `HAS_LOOP`, `HAS_MULTI`,
198///   `HAS_MUTUAL` if currently cached **true**.
199/// - Adding an edge **may** turn a DAG into a non-DAG, or a forest
200///   into a non-forest → keep `IS_DAG`, `IS_FOREST` only if currently
201///   cached **false**.
202pub(crate) fn invalidate_after_add_edges(cache: &PropertyCache) {
203    use CachedProperty::{
204        HasLoop, HasMulti, HasMutual, IsDag, IsForest, IsStronglyConnected, IsWeaklyConnected,
205    };
206    cache.invalidate_conditionally(
207        0,
208        IsDag.bit() | IsForest.bit(),
209        IsWeaklyConnected.bit()
210            | IsStronglyConnected.bit()
211            | HasLoop.bit()
212            | HasMulti.bit()
213            | HasMutual.bit(),
214    );
215}
216
217#[cfg(test)]
218mod tests {
219    use super::*;
220
221    #[test]
222    fn empty_cache_misses() {
223        let c = PropertyCache::new();
224        assert!(!c.has(CachedProperty::IsDag));
225        assert_eq!(c.get(CachedProperty::IsDag), None);
226    }
227
228    #[test]
229    fn set_then_get_round_trips() {
230        let c = PropertyCache::new();
231        c.set(CachedProperty::IsDag, true);
232        c.set(CachedProperty::IsForest, false);
233        assert_eq!(c.get(CachedProperty::IsDag), Some(true));
234        assert_eq!(c.get(CachedProperty::IsForest), Some(false));
235        assert_eq!(c.get(CachedProperty::HasLoop), None);
236    }
237
238    #[test]
239    fn overwrite_changes_value() {
240        let c = PropertyCache::new();
241        c.set(CachedProperty::HasLoop, true);
242        assert_eq!(c.get(CachedProperty::HasLoop), Some(true));
243        c.set(CachedProperty::HasLoop, false);
244        assert_eq!(c.get(CachedProperty::HasLoop), Some(false));
245    }
246
247    #[test]
248    fn invalidate_one_keeps_others() {
249        let c = PropertyCache::new();
250        c.set(CachedProperty::HasLoop, true);
251        c.set(CachedProperty::IsDag, false);
252        c.invalidate(CachedProperty::HasLoop);
253        assert_eq!(c.get(CachedProperty::HasLoop), None);
254        assert_eq!(c.get(CachedProperty::IsDag), Some(false));
255    }
256
257    #[test]
258    fn invalidate_all_clears_everything() {
259        let c = PropertyCache::new();
260        c.set(CachedProperty::HasLoop, true);
261        c.set(CachedProperty::IsDag, false);
262        c.invalidate_all();
263        for p in [
264            CachedProperty::HasLoop,
265            CachedProperty::IsDag,
266            CachedProperty::IsForest,
267        ] {
268            assert_eq!(c.get(p), None);
269        }
270    }
271
272    #[test]
273    fn invalidate_conditionally_keep_always() {
274        let c = PropertyCache::new();
275        c.set(CachedProperty::IsDag, true);
276        c.set(CachedProperty::HasLoop, false);
277        c.invalidate_conditionally(CachedProperty::IsDag.bit(), 0, 0);
278        assert_eq!(c.get(CachedProperty::IsDag), Some(true));
279        assert_eq!(c.get(CachedProperty::HasLoop), None);
280    }
281
282    #[test]
283    fn invalidate_conditionally_keep_when_false() {
284        let c = PropertyCache::new();
285        c.set(CachedProperty::IsDag, false);
286        c.invalidate_conditionally(0, CachedProperty::IsDag.bit(), 0);
287        assert_eq!(c.get(CachedProperty::IsDag), Some(false));
288
289        // Same mask but value cached as true — should now drop.
290        let c = PropertyCache::new();
291        c.set(CachedProperty::IsDag, true);
292        c.invalidate_conditionally(0, CachedProperty::IsDag.bit(), 0);
293        assert_eq!(c.get(CachedProperty::IsDag), None);
294    }
295
296    #[test]
297    fn invalidate_conditionally_keep_when_true() {
298        let c = PropertyCache::new();
299        c.set(CachedProperty::HasLoop, true);
300        c.invalidate_conditionally(0, 0, CachedProperty::HasLoop.bit());
301        assert_eq!(c.get(CachedProperty::HasLoop), Some(true));
302
303        let c = PropertyCache::new();
304        c.set(CachedProperty::HasLoop, false);
305        c.invalidate_conditionally(0, 0, CachedProperty::HasLoop.bit());
306        assert_eq!(c.get(CachedProperty::HasLoop), None);
307    }
308
309    #[test]
310    fn add_edges_policy_keeps_dag_false_and_loop_true() {
311        let c = PropertyCache::new();
312        c.set(CachedProperty::IsDag, false);
313        c.set(CachedProperty::HasLoop, true);
314        c.set(CachedProperty::IsForest, true); // should drop after add_edges
315        c.set(CachedProperty::HasMulti, false); // should drop
316        invalidate_after_add_edges(&c);
317        assert_eq!(c.get(CachedProperty::IsDag), Some(false));
318        assert_eq!(c.get(CachedProperty::HasLoop), Some(true));
319        assert_eq!(c.get(CachedProperty::IsForest), None);
320        assert_eq!(c.get(CachedProperty::HasMulti), None);
321    }
322
323    #[test]
324    fn add_vertices_policy_keeps_edge_props_unconditionally() {
325        let c = PropertyCache::new();
326        c.set(CachedProperty::HasLoop, false);
327        c.set(CachedProperty::HasMulti, true);
328        c.set(CachedProperty::HasMutual, true);
329        c.set(CachedProperty::IsDag, true);
330        c.set(CachedProperty::IsForest, false);
331        c.set(CachedProperty::IsWeaklyConnected, true); // should drop
332        invalidate_after_add_vertices(&c);
333        assert_eq!(c.get(CachedProperty::HasLoop), Some(false));
334        assert_eq!(c.get(CachedProperty::HasMulti), Some(true));
335        assert_eq!(c.get(CachedProperty::HasMutual), Some(true));
336        assert_eq!(c.get(CachedProperty::IsDag), Some(true));
337        assert_eq!(c.get(CachedProperty::IsForest), Some(false));
338        assert_eq!(c.get(CachedProperty::IsWeaklyConnected), None);
339    }
340
341    #[test]
342    fn clone_preserves_cache() {
343        let c = PropertyCache::new();
344        c.set(CachedProperty::IsDag, true);
345        let c2 = c.clone();
346        assert_eq!(c2.get(CachedProperty::IsDag), Some(true));
347    }
348}
rust_igraph/core/cache.rs

rust_igraph/core/
cache.rs
