Skip to main content

kernel/graph/
query.rs

1// Copyright 2026 Mark AB (markik)
2// SPDX-License-Identifier: MIT OR Apache-2.0
3
4//! Graph query + traversal — node / edge lookups, neighbor
5//! iteration, BFS / shortest-path / connected-components / SCC, and
6//! the derived-edge views (semantic / arrangement / containment).
7//!
8//! Extracted from `graph/mod.rs` per the 2026-05-11 kernel
9//! decomposition pass. These are the read-only and read-mostly
10//! methods on `Graph`; the mutating counterparts live in `mod.rs`
11//! (node-property setters), `edge_ops.rs` (edge mutators), and
12//! `snapshot.rs` (serialization).
13
14use std::collections::{HashMap, HashSet, VecDeque};
15
16use petgraph::Direction;
17use petgraph::algo::{astar, dijkstra, has_path_connecting, kosaraju_scc};
18use petgraph::visit::{EdgeRef, IntoEdgeReferences, UndirectedAdaptor};
19use uuid::Uuid;
20
21use super::edge_taxonomy::{ContainmentSubKind, EdgeAssertion, RelationSelector};
22use super::identity::{EdgeKey, NodeKey};
23use super::node::Node;
24use super::snapshot::containment_parent_url;
25use super::{ArrangementEdgeView, ContainmentEdgeView, Graph, RelationView, SemanticEdgeView};
26
27impl Graph {
28    /// Get a node by key
29    pub fn get_node(&self, key: NodeKey) -> Option<&Node> {
30        self.inner.node(key)
31    }
32
33    /// Get a mutable node by key.
34    pub(crate) fn get_node_mut(&mut self, key: NodeKey) -> Option<&mut Node> {
35        self.inner.node_mut(key)
36    }
37
38    /// Find a node whose AddressClaims include the given address (any
39    /// `AddressRole`). Returns an arbitrary matching node when multiple
40    /// nodes share the address — the caller is expected to handle
41    /// duplicates explicitly when relevant.
42    ///
43    /// Canonical address lookup per the [node identity + duplicates
44    /// brief](https://github.com/merely-made/mere/blob/main/design_docs/mere_docs/research/2026-05-18_node_identity_and_duplicates_brief.md);
45    /// supersedes the URL-string-keyed `get_node_by_url` (which is
46    /// retained as a transitional shim — see below).
47    pub fn find_node_by_address(
48        &self,
49        address: &crate::address::Address,
50    ) -> Option<(NodeKey, &Node)> {
51        let url = address.as_url_str();
52        let key = self.url_to_nodes.get(url)?.last().copied()?;
53        Some((key, self.inner.node(key)?))
54    }
55
56    /// Convenience wrapper over [`Graph::find_node_by_address`] for
57    /// callers that have a URL string rather than a typed [`Address`].
58    /// Builds the [`Address`] internally and delegates.
59    ///
60    /// Use this for tests and quick lookups; prefer
61    /// [`Graph::find_node_by_address`] in code paths that already have a
62    /// typed [`Address`] in hand.
63    pub fn get_node_by_url(&self, url: &str) -> Option<(NodeKey, &Node)> {
64        let address = crate::address::address_from_url(url);
65        self.find_node_by_address(&address)
66    }
67
68    /// Get all node keys currently mapped to a URL.
69    pub fn get_nodes_by_url(&self, url: &str) -> Vec<NodeKey> {
70        self.url_to_nodes.get(url).cloned().unwrap_or_default()
71    }
72
73    /// Get a node by UUID.
74    pub fn get_node_by_id(&self, id: Uuid) -> Option<(NodeKey, &Node)> {
75        let key = self.inner.key_of(&id)?;
76        Some((key, self.inner.node(key)?))
77    }
78
79    /// Get node key by UUID.
80    pub fn get_node_key_by_id(&self, id: Uuid) -> Option<NodeKey> {
81        self.inner.key_of(&id)
82    }
83
84    /// Iterate over all nodes as (key, node) pairs
85    pub fn nodes(&self) -> impl Iterator<Item = (NodeKey, &Node)> {
86        self.inner.nodes()
87    }
88
89    /// Iterate over all stored relations, one row per recognized
90    /// statement/family carried by the pair-local edge bucket.
91    /// One `EdgePayload` between two nodes may therefore yield
92    /// multiple semantic rows.
93    ///
94    /// Canonical read surface per the 2026-05-11 relation-taxonomy
95    /// plan §2. Stage 4 removed the legacy `EdgeType`-flavoured
96    /// `edges()` iterator that this replaces.
97    pub fn relations(&self) -> impl Iterator<Item = RelationView> + '_ {
98        use super::edge_taxonomy::RelationKind;
99        self.inner.inner().edge_references().flat_map(|edge| {
100            let from = edge.source();
101            let to = edge.target();
102            let payload = edge.weight();
103            let mut out: Vec<RelationView> = Vec::new();
104            for statement in payload.semantic_statements() {
105                if let Some(sub_kind) = statement.recognized_sub_kind {
106                    out.push(RelationView {
107                        from,
108                        to,
109                        kind: RelationKind::Semantic(sub_kind),
110                    });
111                }
112            }
113            // Traversal is event-shaped, no sub-kind. Presence of
114            // any traversal data (events or metrics) yields one
115            // row. Family-aware view callers reach for the
116            // typed payload for actual events.
117            if let Some(traversal) = payload.traversal_data()
118                && (!traversal.traversals.is_empty() || traversal.metrics.total_navigations > 0)
119            {
120                out.push(RelationView {
121                    from,
122                    to,
123                    kind: RelationKind::Traversal,
124                });
125            }
126            if let Some(containment) = payload.containment_data() {
127                for &sub_kind in &containment.sub_kinds {
128                    out.push(RelationView {
129                        from,
130                        to,
131                        kind: RelationKind::Containment(sub_kind),
132                    });
133                }
134            }
135            if let Some(arrangement) = payload.arrangement_data() {
136                for &sub_kind in &arrangement.sub_kinds {
137                    out.push(RelationView {
138                        from,
139                        to,
140                        kind: RelationKind::Arrangement(sub_kind),
141                    });
142                }
143            }
144            if let Some(imported) = payload.imported_data() {
145                for &sub_kind in &imported.sub_kinds {
146                    out.push(RelationView {
147                        from,
148                        to,
149                        kind: RelationKind::Imported(sub_kind),
150                    });
151                }
152            }
153            if let Some(prov) = payload.provenance_data() {
154                for &sub_kind in &prov.sub_kinds {
155                    out.push(RelationView {
156                        from,
157                        to,
158                        kind: RelationKind::Provenance(sub_kind),
159                    });
160                }
161            }
162            out.into_iter()
163        })
164    }
165
166    pub fn semantic_edges(&self) -> impl Iterator<Item = SemanticEdgeView> + '_ {
167        self.inner.inner().edge_references().flat_map(|edge| {
168            let from = edge.source();
169            let to = edge.target();
170            let payload = edge.weight();
171            payload
172                .semantic_statements()
173                .iter()
174                .filter_map(|statement| {
175                    statement
176                        .recognized_sub_kind
177                        .map(|sub_kind| SemanticEdgeView {
178                            from,
179                            to,
180                            sub_kind,
181                            label: statement.label.clone(),
182                        })
183                })
184                .collect::<Vec<_>>()
185                .into_iter()
186        })
187    }
188
189    pub fn arrangement_edges(&self) -> impl Iterator<Item = ArrangementEdgeView> + '_ {
190        self.inner.inner().edge_references().flat_map(|e| {
191            let from = e.source();
192            let to = e.target();
193            e.weight()
194                .arrangement_data()
195                .map(|data| {
196                    data.sub_kinds
197                        .iter()
198                        .copied()
199                        .map(move |sub_kind| ArrangementEdgeView { from, to, sub_kind })
200                })
201                .into_iter()
202                .flatten()
203        })
204    }
205
206    pub fn containment_edges(&self) -> impl Iterator<Item = ContainmentEdgeView> + '_ {
207        self.inner.inner().edge_references().flat_map(|e| {
208            let from = e.source();
209            let to = e.target();
210            e.weight()
211                .containment_data()
212                .map(|data| {
213                    data.sub_kinds
214                        .iter()
215                        .copied()
216                        .map(move |sub_kind| ContainmentEdgeView { from, to, sub_kind })
217                })
218                .into_iter()
219                .flatten()
220        })
221    }
222
223    /// Rebuild derived containment edges from current node URLs.
224    ///
225    /// Derived relations are additive/read-only and are never persisted.
226    /// Derive the containment this one node's address implies, at the moment
227    /// the node is created.
228    ///
229    /// The **UrlPath half** of [`rebuild_derived_containment_relations`],
230    /// applied to a single node. It exists because that rebuild runs only on
231    /// snapshot load, which used to mean a node visited under a folder had no
232    /// containment edge until the session was saved and reloaded. Anything
233    /// reading containment live (a graph behavior's watch, which names a
234    /// region by its container) saw nothing there. Deriving at creation makes
235    /// containment mean the same thing live and loaded.
236    ///
237    /// The **Domain half is deliberately not here.** A domain anchor is the
238    /// shallowest node on a host, so minting one node can re-anchor every
239    /// other node sharing that host: a whole-graph fact, which stays with the
240    /// whole-graph rebuild. This one is purely local, which is what makes it
241    /// cheap enough to run per node.
242    pub fn derive_containment_for(&mut self, key: NodeKey) {
243        let Some(node) = self.get_node(key) else {
244            return;
245        };
246        let Ok(parsed) = url::Url::parse(node.url()) else {
247            return;
248        };
249        let Some(parent_url) = containment_parent_url(&parsed) else {
250            return;
251        };
252        let Some((parent_key, _)) = self.get_node_by_url(&parent_url) else {
253            return;
254        };
255        if parent_key == key {
256            return;
257        }
258        // Child to container, the direction the rebuild uses.
259        let _ = self.assert_relation(
260            key,
261            parent_key,
262            EdgeAssertion::Containment {
263                sub_kind: ContainmentSubKind::UrlPath,
264            },
265        );
266    }
267
268    pub(crate) fn rebuild_derived_containment_relations(&mut self) {
269        let edge_ids: Vec<EdgeKey> = self.inner.inner().edge_indices().collect();
270        let mut empty_edges = Vec::new();
271        // This rebuild retracts containment relations and removes empty edges directly on `inner`
272        // (bypassing the bumping API), so track the structural change and bump once. The
273        // `assert_relation` calls below bump on their own when they re-derive the edges.
274        let mut changed = false;
275        for edge_id in edge_ids {
276            if let Some(payload) = self.inner.edge_mut(edge_id) {
277                let mut removed_any = false;
278                removed_any |= payload
279                    .retract_relation(RelationSelector::Containment(ContainmentSubKind::UrlPath));
280                removed_any |= payload
281                    .retract_relation(RelationSelector::Containment(ContainmentSubKind::Domain));
282                if removed_any {
283                    changed = true;
284                }
285                if removed_any && payload.is_empty() {
286                    empty_edges.push(edge_id);
287                }
288            }
289        }
290        for edge_id in empty_edges {
291            let _ = self.inner.disconnect(edge_id);
292        }
293        if changed {
294            self.bump_revision();
295        }
296
297        let mut domain_anchor: HashMap<String, (NodeKey, usize, Uuid)> = HashMap::new();
298        for (key, node) in self.nodes() {
299            let Ok(parsed) = url::Url::parse(node.url()) else {
300                continue;
301            };
302            let depth = parsed.path_segments().map_or(0, |segments| {
303                segments.filter(|segment| !segment.is_empty()).count()
304            });
305
306            let Some(host) = parsed.host_str() else {
307                continue;
308            };
309            let host = host.to_ascii_lowercase();
310            let candidate = (key, depth, node.id);
311            domain_anchor
312                .entry(host)
313                .and_modify(|current| {
314                    if candidate.1 < current.1
315                        || (candidate.1 == current.1 && candidate.2 < current.2)
316                    {
317                        *current = candidate;
318                    }
319                })
320                .or_insert(candidate);
321        }
322
323        let mut url_parent_edges = Vec::new();
324        let mut domain_edges = Vec::new();
325        for (key, node) in self.nodes() {
326            let Ok(parsed) = url::Url::parse(node.url()) else {
327                continue;
328            };
329
330            if let Some(parent_url) = containment_parent_url(&parsed)
331                && let Some((parent_key, _)) = self.get_node_by_url(&parent_url)
332                && parent_key != key
333            {
334                url_parent_edges.push((key, parent_key));
335            }
336
337            if let Some(host) = parsed.host_str() {
338                let host = host.to_ascii_lowercase();
339                if let Some((anchor_key, _, _)) = domain_anchor.get(&host)
340                    && *anchor_key != key
341                {
342                    domain_edges.push((key, *anchor_key));
343                }
344            }
345        }
346
347        for (from, to) in url_parent_edges {
348            let _ = self.assert_relation(
349                from,
350                to,
351                EdgeAssertion::Containment {
352                    sub_kind: ContainmentSubKind::UrlPath,
353                },
354            );
355        }
356        for (from, to) in domain_edges {
357            let _ = self.assert_relation(
358                from,
359                to,
360                EdgeAssertion::Containment {
361                    sub_kind: ContainmentSubKind::Domain,
362                },
363            );
364        }
365    }
366
367    /// Iterate outgoing neighbor keys for a node
368    pub fn out_neighbors(&self, key: NodeKey) -> impl Iterator<Item = NodeKey> + '_ {
369        self.inner
370            .inner()
371            .neighbors_directed(key, Direction::Outgoing)
372    }
373
374    /// Iterate incoming neighbor keys for a node
375    pub fn in_neighbors(&self, key: NodeKey) -> impl Iterator<Item = NodeKey> + '_ {
376        self.inner
377            .inner()
378            .neighbors_directed(key, Direction::Incoming)
379    }
380
381    /// Iterate undirected neighbor keys for a node.
382    pub fn neighbors_undirected(&self, key: NodeKey) -> impl Iterator<Item = NodeKey> + '_ {
383        self.inner.inner().neighbors_undirected(key)
384    }
385
386    /// Undirected neighbors sorted by stable node-key order.
387    pub fn neighbors_undirected_sorted(&self, key: NodeKey) -> Vec<NodeKey> {
388        let mut neighbors: Vec<NodeKey> = self
389            .neighbors_undirected(key)
390            .filter(|neighbor| *neighbor != key && self.get_node(*neighbor).is_some())
391            .collect::<HashSet<_>>()
392            .into_iter()
393            .collect();
394        neighbors.sort_by_key(|neighbor| neighbor.index());
395        neighbors
396    }
397
398    /// Seed nodes plus one-hop undirected neighbors for frame import workflows.
399    pub fn connected_frame_import_nodes(&self, seeds: &[NodeKey]) -> Vec<NodeKey> {
400        let mut out = HashSet::new();
401        for seed in seeds {
402            if self.get_node(*seed).is_none() {
403                continue;
404            }
405            out.insert(*seed);
406            out.extend(self.neighbors_undirected(*seed));
407        }
408        let mut nodes: Vec<NodeKey> = out
409            .into_iter()
410            .filter(|key| self.get_node(*key).is_some())
411            .collect();
412        nodes.sort_by_key(|key| key.index());
413        nodes
414    }
415
416    /// Connected candidate expansion around a source node with depth annotations.
417    ///
418    /// `max_depth` currently supports 1 or 2, matching connected-open scope behavior.
419    pub fn connected_candidates_with_depth(
420        &self,
421        source: NodeKey,
422        max_depth: u8,
423    ) -> Vec<(NodeKey, u8)> {
424        if self.get_node(source).is_none() || max_depth == 0 {
425            return Vec::new();
426        }
427
428        let mut out = Vec::new();
429        let mut visited = HashSet::from([source]);
430
431        let depth1 = self.neighbors_undirected_sorted(source);
432        for neighbor in depth1 {
433            if visited.insert(neighbor) {
434                out.push((neighbor, 1));
435            }
436        }
437
438        if max_depth < 2 {
439            return out;
440        }
441
442        let depth1_nodes: Vec<NodeKey> = out
443            .iter()
444            .filter_map(|(node, depth)| (*depth == 1).then_some(*node))
445            .collect();
446        for depth1_node in depth1_nodes {
447            for neighbor in self.neighbors_undirected_sorted(depth1_node) {
448                if visited.insert(neighbor) {
449                    out.push((neighbor, 2));
450                }
451            }
452        }
453
454        out
455    }
456
457    /// Undirected hop distances from `source` using unit edge weights.
458    pub fn hop_distances_from(&self, source: NodeKey) -> HashMap<NodeKey, usize> {
459        if self.get_node(source).is_none() {
460            return HashMap::new();
461        }
462        dijkstra(&UndirectedAdaptor(self.inner.inner()), source, None, |_| {
463            1_usize
464        })
465        .into_iter()
466        .collect()
467    }
468
469    /// Nodes with no incoming or outgoing edges.
470    pub fn orphan_node_keys(&self) -> Vec<NodeKey> {
471        let inner = self.inner.inner();
472        inner
473            .node_indices()
474            .filter(|&key| {
475                inner
476                    .edges_directed(key, Direction::Outgoing)
477                    .next()
478                    .is_none()
479                    && inner
480                        .edges_directed(key, Direction::Incoming)
481                        .next()
482                        .is_none()
483            })
484            .collect()
485    }
486
487    /// Shortest undirected path between two nodes using unit edge weights.
488    pub fn shortest_path(&self, from: NodeKey, to: NodeKey) -> Option<Vec<NodeKey>> {
489        if self.get_node(from).is_none() || self.get_node(to).is_none() {
490            return None;
491        }
492        astar(
493            &UndirectedAdaptor(self.inner.inner()),
494            from,
495            |node| node == to,
496            |_| 1_usize,
497            |_| 0_usize,
498        )
499        .map(|(_, path)| path)
500    }
501
502    /// Reachability in the undirected graph.
503    pub fn is_reachable(&self, from: NodeKey, to: NodeKey) -> bool {
504        if self.get_node(from).is_none() || self.get_node(to).is_none() {
505            return false;
506        }
507        has_path_connecting(&UndirectedAdaptor(self.inner.inner()), from, to, None)
508    }
509
510    /// Weakly connected components (undirected projection).
511    pub fn weakly_connected_components(&self) -> Vec<Vec<NodeKey>> {
512        let mut visited = HashSet::new();
513        let mut components = Vec::new();
514        for start in self.inner.inner().node_indices() {
515            if !visited.insert(start) {
516                continue;
517            }
518            let mut component = Vec::new();
519            let mut stack = vec![start];
520            while let Some(current) = stack.pop() {
521                component.push(current);
522                for neighbor in self.neighbors_undirected(current) {
523                    if visited.insert(neighbor) {
524                        stack.push(neighbor);
525                    }
526                }
527            }
528            components.push(component);
529        }
530        components
531    }
532
533    /// The connected component of `seed` — it plus every node reachable through relations
534    /// (undirected), breadth-first. Empty if `seed` is not in the graph. `selectors` is the
535    /// **edge projection**: only edges matching a selector are followed (an empty slice
536    /// follows every family). So the *same* nodes can be one Component under one projection
537    /// and a different one under another. The **Component** graphlet's derivation. (Graphlet
538    /// derivation, Phase 3 — selectors.)
539    pub fn component_members(
540        &self,
541        seed: uuid::Uuid,
542        selectors: &[super::RelationSelector],
543    ) -> Vec<uuid::Uuid> {
544        self.bfs_members(seed, None, selectors)
545    }
546
547    /// The **Ego** neighborhood of `seed`: itself plus every node within `radius`
548    /// undirected hops, breadth-first (`radius` 0 = just the seed), over the `selectors`
549    /// edge projection (empty = all families). The Ego graphlet's derivation. (Graphlet
550    /// derivation, Phase 3 — selectors.)
551    pub fn ego_members(
552        &self,
553        seed: uuid::Uuid,
554        radius: u8,
555        selectors: &[super::RelationSelector],
556    ) -> Vec<uuid::Uuid> {
557        self.bfs_members(seed, Some(radius), selectors)
558    }
559
560    /// Breadth-first member uuids from `seed` over undirected neighbors, bounded to
561    /// `max_depth` hops (`None` = unbounded = the whole component) and to the `selectors`
562    /// edge projection. Shared by [`component_members`](Self::component_members) and
563    /// [`ego_members`](Self::ego_members).
564    fn bfs_members(
565        &self,
566        seed: uuid::Uuid,
567        max_depth: Option<u8>,
568        selectors: &[super::RelationSelector],
569    ) -> Vec<uuid::Uuid> {
570        let Some((start, _)) = self.get_node_by_id(seed) else {
571            return Vec::new();
572        };
573        let mut seen = HashSet::new();
574        let mut order = Vec::new();
575        let mut queue = std::collections::VecDeque::new();
576        seen.insert(start);
577        queue.push_back((start, 0u8));
578        while let Some((key, depth)) = queue.pop_front() {
579            if let Some(node) = self.get_node(key) {
580                order.push(node.id);
581            }
582            if max_depth.is_some_and(|m| depth >= m) {
583                continue;
584            }
585            for neighbor in self.neighbors_undirected_sorted(key) {
586                // Edge projection: only follow an edge matching a selector (empty = all
587                // families). This is what makes the same nodes derive a different shape
588                // under a different relation projection. (Graphlet derivation — selectors.)
589                if !selectors.is_empty() && !self.edge_matches_selectors(key, neighbor, selectors) {
590                    continue;
591                }
592                if seen.insert(neighbor) {
593                    queue.push_back((neighbor, depth + 1));
594                }
595            }
596        }
597        order
598    }
599
600    /// Whether the edge between `a` and `b` (either direction) matches any of `selectors`
601    /// (a relation family or sub-kind). Used by the selector-projected derivation walk.
602    fn edge_matches_selectors(
603        &self,
604        a: NodeKey,
605        b: NodeKey,
606        selectors: &[super::RelationSelector],
607    ) -> bool {
608        self.find_edge_key(a, b)
609            .or_else(|| self.find_edge_key(b, a))
610            .and_then(|k| self.inner.edge(k))
611            .is_some_and(|payload| selectors.iter().any(|&s| payload.has_relation(s)))
612    }
613
614    /// Strongly connected components in the directed graph.
615    pub fn strongly_connected_components(&self) -> Vec<Vec<NodeKey>> {
616        kosaraju_scc(self.inner.inner())
617    }
618
619    /// Check if a directed edge exists from `from` to `to`
620    pub fn has_edge_between(&self, from: NodeKey, to: NodeKey) -> bool {
621        self.inner.inner().find_edge(from, to).is_some()
622    }
623
624    /// Count of nodes in the graph
625    pub fn node_count(&self) -> usize {
626        self.inner.node_count()
627    }
628
629    /// Count of edges in the graph
630    pub fn edge_count(&self) -> usize {
631        self.inner.edge_count()
632    }
633}
634
635#[cfg(test)]
636mod derivation_tests {
637    use super::*;
638    use crate::graph::SemanticSubKind;
639    use euclid::default::Point2D;
640
641    /// An A–B–C chain plus an isolated D. Returns the graph and `[a, b, c, d]` uuids.
642    fn chain_plus_isolate() -> (Graph, [uuid::Uuid; 4]) {
643        let mut g = Graph::new();
644        let a = g.add_node("https://a".to_string(), Point2D::new(0.0, 0.0));
645        let b = g.add_node("https://b".to_string(), Point2D::new(1.0, 0.0));
646        let c = g.add_node("https://c".to_string(), Point2D::new(2.0, 0.0));
647        let d = g.add_node("https://d".to_string(), Point2D::new(9.0, 9.0));
648        let sem = || EdgeAssertion::Semantic {
649            sub_kind: SemanticSubKind::Hyperlink,
650            label: None,
651            decay_progress: None,
652        };
653        g.assert_relation(a, b, sem());
654        g.assert_relation(b, c, sem());
655        let ids = [
656            g.get_node(a).unwrap().id,
657            g.get_node(b).unwrap().id,
658            g.get_node(c).unwrap().id,
659            g.get_node(d).unwrap().id,
660        ];
661        (g, ids)
662    }
663
664    #[test]
665    fn component_members_is_the_whole_connected_component() {
666        let (g, [a, _b, _c, d]) = chain_plus_isolate();
667        assert_eq!(g.component_members(a, &[]).len(), 3, "A reaches B and C");
668        assert_eq!(g.component_members(d, &[]).len(), 1, "D is isolated");
669        assert!(
670            g.component_members(uuid::Uuid::nil(), &[]).is_empty(),
671            "unknown seed: empty"
672        );
673    }
674
675    #[test]
676    fn ego_members_is_radius_bounded() {
677        let (g, [a, _b, _c, _d]) = chain_plus_isolate();
678        assert_eq!(
679            g.ego_members(a, 0, &[]).len(),
680            1,
681            "radius 0 is just the seed"
682        );
683        assert_eq!(
684            g.ego_members(a, 1, &[]).len(),
685            2,
686            "radius 1 reaches B, not C"
687        );
688        assert_eq!(g.ego_members(a, 2, &[]).len(), 3, "radius 2 reaches C");
689    }
690
691    #[test]
692    fn the_selector_projection_changes_the_derived_shape() {
693        use crate::graph::{ContainmentSubKind, EdgeFamily, RelationSelector};
694        // A —Semantic→ B —Containment→ C. The same three nodes, two relation families.
695        let mut g = Graph::new();
696        let a = g.add_node("https://a".to_string(), Point2D::new(0.0, 0.0));
697        let b = g.add_node("https://b".to_string(), Point2D::new(1.0, 0.0));
698        let c = g.add_node("https://c".to_string(), Point2D::new(2.0, 0.0));
699        g.assert_relation(
700            a,
701            b,
702            EdgeAssertion::Semantic {
703                sub_kind: SemanticSubKind::Hyperlink,
704                label: None,
705                decay_progress: None,
706            },
707        );
708        g.assert_relation(
709            b,
710            c,
711            EdgeAssertion::Containment {
712                sub_kind: ContainmentSubKind::CollectionMember,
713            },
714        );
715        let a_id = g.get_node(a).unwrap().id;
716
717        let semantic = [RelationSelector::Family(EdgeFamily::Semantic)];
718        let containment = [RelationSelector::Family(EdgeFamily::Containment)];
719        // Whole graph under no projection; Semantic stops at B; Containment never leaves A.
720        assert_eq!(
721            g.component_members(a_id, &[]).len(),
722            3,
723            "all families: A, B, C"
724        );
725        assert_eq!(
726            g.component_members(a_id, &semantic).len(),
727            2,
728            "Semantic projection: A, B (B→C is Containment, not followed)"
729        );
730        assert_eq!(
731            g.component_members(a_id, &containment).len(),
732            1,
733            "Containment projection: just A (no Containment edge from A)"
734        );
735    }
736}