Skip to main content

kernel/graph/
query.rs

1// Copyright 2026 Mark Alan Boykin
2// This Source Code Form is subject to the terms of the Mozilla Public
3// License, v. 2.0. If a copy of the MPL was not distributed with this
4// file, You can obtain one at https://mozilla.org/MPL/2.0/.
5// SPDX-License-Identifier: MPL-2.0
6
7//! Graph query + traversal — node / edge lookups, neighbor
8//! iteration, BFS / shortest-path / connected-components / SCC, and
9//! the derived-edge views (semantic / arrangement / containment).
10//!
11//! Extracted from `graph/mod.rs` per the 2026-05-11 kernel
12//! decomposition pass. These are the read-only and read-mostly
13//! methods on `Graph`; the mutating counterparts live in `mod.rs`
14//! (node-property setters), `edge_ops.rs` (edge mutators), and
15//! `snapshot.rs` (serialization).
16
17use std::collections::{HashMap, HashSet, VecDeque};
18
19use petgraph::Direction;
20use petgraph::algo::kosaraju_scc;
21use petgraph::graph::DiGraph;
22use petgraph::visit::{EdgeRef, IntoEdgeReferences};
23use uuid::Uuid;
24
25use super::edge_payload::EdgePayload;
26use super::edge_taxonomy::{ContainmentSubKind, EdgeAssertion, RelationSelector};
27use super::identity::{EdgeKey, NodeKey, RelationKey};
28use super::node::Node;
29use super::snapshot::containment_parent_url;
30use super::{ArrangementEdgeView, ContainmentEdgeView, Graph, RelationView, SemanticEdgeView};
31
32/// Expand one pair-local edge bucket into held [`RelationView`] rows: one
33/// per held semantic statement (`Semantic(sub_kind)` when recognized, else
34/// `OpenPredicate`), one for traversal-sidecar presence, and one per
35/// sub-kind in each of the remaining families. Shared by every relation
36/// iterator so per-node and whole-graph reads agree row for row.
37///
38/// Row families agree with [`EdgePayload::families`] for every edge
39/// shape (Q1 ruling, 2026-09-12; pinned by `row_family_parity_tests`).
40fn relation_rows(from: NodeKey, to: NodeKey, payload: &EdgePayload) -> Vec<RelationView> {
41    use super::edge_taxonomy::RelationKind;
42    let mut out: Vec<RelationView> = Vec::new();
43    for statement in payload.held_assertions() {
44        out.push(RelationView {
45            from,
46            to,
47            kind: statement.relation_kind(),
48        });
49    }
50    // Traversal is event-shaped, no sub-kind. Presence of the
51    // traversal sidecar yields one row, matching
52    // `has_family(Traversal)`; an event-free sidecar (reachable
53    // only by deserializing such a snapshot) still counts.
54    // Family-aware view callers reach for the typed payload for
55    // actual events.
56    if payload.traversal_data().is_some() {
57        out.push(RelationView {
58            from,
59            to,
60            kind: RelationKind::Traversal,
61        });
62    }
63    out
64}
65
66#[cfg(test)]
67mod projected_relation_tests {
68    use super::*;
69    use crate::graph::{ResourceNode, SemanticStatement, SemanticSubKind};
70    use crate::persistence::PersistedResourceRecord;
71    use crate::types::GraphScope;
72
73    #[test]
74    fn projected_rows_keep_owner_direction_multiplicity_and_all_shown_pairs() {
75        let mut graph = Graph::new();
76        let [a, alias_a, b, alias_b, unbound] = std::array::from_fn::<_, 5, _>(|i| {
77            graph.add_node(format!("https://surface.test/{i}"), Default::default())
78        });
79        let surface_key = graph
80            .assert_relation(
81                a,
82                b,
83                EdgeAssertion::Semantic {
84                    sub_kind: SemanticSubKind::UserGrouped,
85                    label: None,
86                },
87            )
88            .unwrap();
89        let [ra, rb, unshown] = ["a", "b", "unshown"].map(|suffix| {
90            let iri = format!("https://resource.test/{suffix}");
91            let resource = ResourceNode::for_term(&iri);
92            assert!(graph.set_resource_record(
93                resource.id(),
94                Some(PersistedResourceRecord {
95                    canonical_iri: iri,
96                    facets: vec![],
97                })
98            ));
99            resource.id()
100        });
101        for (from, to, ids) in [
102            (ra, rb, vec!["forward-1", "forward-2"]),
103            (rb, ra, vec!["backward"]),
104            (ra, ra, vec!["self"]),
105            (ra, unshown, vec!["not-shown"]),
106        ] {
107            let records: Vec<_> = ids
108                .into_iter()
109                .map(|id| {
110                    let mut payload = EdgePayload::new();
111                    payload.push_persisted_semantic_statement(SemanticStatement {
112                        statement_id: id.into(),
113                        predicate: crate::graph::predicate_iri(SemanticSubKind::Cites).into(),
114                        recognized_sub_kind: Some(SemanticSubKind::Cites),
115                        label: Some(id.into()),
116                        graph_scope: GraphScope::Default,
117                        provenance_iri: Some("https://author.test/".into()),
118                        asserted_at_ms: Some(17),
119                        first_asserted_ms: Some(17),
120                        withdrawn: None,
121                        basis: Default::default(),
122                    });
123                    super::super::snapshot::persisted_edge_for_ids(from, to, &payload)
124                })
125                .collect();
126            assert!(graph.set_resource_edges_between(from, to, &records));
127        }
128        assert_eq!(
129            graph.projected_relations().count(),
130            1,
131            "unshown truth stays stored"
132        );
133        for (surface, resource) in [(a, ra), (alias_a, ra), (b, rb), (alias_b, rb)] {
134            assert!(graph.set_shown_resource(graph.get_node(surface).unwrap().id, Some(resource)));
135        }
136        let rows: Vec<_> = graph.projected_relations().collect();
137        assert_eq!(rows.len(), 17); // surface + 8 forward + 4 backward + 4 self
138        assert_eq!(rows[0].0, surface_key, "surface prefix keeps its owner");
139        for source in [a, alias_a] {
140            for target in [b, alias_b] {
141                assert_eq!(
142                    rows.iter()
143                        .filter(|(key, row)| matches!(key, RelationKey::Resource(_))
144                            && row.from == source
145                            && row.to == target)
146                        .count(),
147                    2
148                );
149                assert_eq!(
150                    rows.iter()
151                        .filter(|(key, row)| matches!(key, RelationKey::Resource(_))
152                            && row.from == target
153                            && row.to == source)
154                        .count(),
155                    1
156                );
157            }
158            for target in [a, alias_a] {
159                assert_eq!(
160                    rows.iter()
161                        .filter(|(_, row)| row.from == source && row.to == target)
162                        .count(),
163                    1,
164                    "resource self-loop lifts every alias pair"
165                );
166            }
167        }
168        assert!(
169            rows.iter()
170                .all(|(key, _)| graph.get_relation(*key).is_some())
171        );
172        assert!(
173            rows.iter()
174                .all(|(_, row)| row.from != unbound && row.to != unbound)
175        );
176        assert_eq!(
177            graph.resource_relations().count(),
178            5,
179            "unshown assertion was retained"
180        );
181        assert!(graph.set_shown_resource(graph.get_node(alias_b).unwrap().id, None));
182        assert_eq!(graph.projected_relations().count(), 11);
183        assert_eq!(graph.resource_relations().count(), 5);
184    }
185}
186
187impl Graph {
188    /// Get a node by key
189    pub fn get_node(&self, key: NodeKey) -> Option<&Node> {
190        self.inner.node(key)
191    }
192
193    /// Get a mutable node by key.
194    pub(crate) fn get_node_mut(&mut self, key: NodeKey) -> Option<&mut Node> {
195        self.inner.node_mut(key)
196    }
197
198    /// Find a node whose AddressClaims include the given address (any
199    /// `AddressRole`). Returns an arbitrary matching node when multiple
200    /// nodes share the address — the caller is expected to handle
201    /// duplicates explicitly when relevant.
202    ///
203    /// Canonical address lookup per the [node identity + duplicates
204    /// brief](https://github.com/merely-made/mere/blob/main/design_docs/mere_docs/research/2026-05-18_node_identity_and_duplicates_brief.md);
205    /// supersedes the URL-string-keyed `get_node_by_url` (which is
206    /// retained as a transitional shim — see below).
207    pub fn find_node_by_address(
208        &self,
209        address: &crate::address::Address,
210    ) -> Option<(NodeKey, &Node)> {
211        let url = address.as_url_str();
212        let key = self.url_to_nodes.get(url)?.last().copied()?;
213        Some((key, self.inner.node(key)?))
214    }
215
216    /// Convenience wrapper over [`Graph::find_node_by_address`] for
217    /// callers that have a URL string rather than a typed [`Address`].
218    /// Builds the [`Address`] internally and delegates.
219    ///
220    /// Use this for tests and quick lookups; prefer
221    /// [`Graph::find_node_by_address`] in code paths that already have a
222    /// typed [`Address`] in hand.
223    pub fn get_node_by_url(&self, url: &str) -> Option<(NodeKey, &Node)> {
224        let address = crate::address::address_from_url(url);
225        self.find_node_by_address(&address)
226    }
227
228    /// Get all node keys currently mapped to a URL.
229    pub fn get_nodes_by_url(&self, url: &str) -> Vec<NodeKey> {
230        self.url_to_nodes.get(url).cloned().unwrap_or_default()
231    }
232
233    /// Get a node by UUID.
234    pub fn get_node_by_id(&self, id: Uuid) -> Option<(NodeKey, &Node)> {
235        let key = self.inner.key_of(&id)?;
236        Some((key, self.inner.node(key)?))
237    }
238
239    /// Get node key by UUID.
240    pub fn get_node_key_by_id(&self, id: Uuid) -> Option<NodeKey> {
241        self.inner.key_of(&id)
242    }
243
244    /// Iterate over all nodes as (key, node) pairs
245    pub fn nodes(&self) -> impl Iterator<Item = (NodeKey, &Node)> {
246        self.inner.nodes()
247    }
248
249    /// Iterate over all stored relations, one row per recognized
250    /// statement/family carried by the pair-local edge bucket.
251    /// One `EdgePayload` between two nodes may therefore yield
252    /// multiple semantic rows.
253    ///
254    /// Canonical read surface per the 2026-05-11 relation-taxonomy
255    /// plan §2. Stage 4 removed the legacy `EdgeType`-flavoured
256    /// `edges()` iterator that this replaces.
257    pub fn relations(&self) -> impl Iterator<Item = RelationView> + '_ {
258        self.inner
259            .inner()
260            .edge_references()
261            .flat_map(|edge| relation_rows(edge.source(), edge.target(), edge.weight()))
262    }
263
264    /// Retained Surface buckets without expanding statements or lifting
265    /// Resource relations. Each handle names its exact bucket, including
266    /// parallel pairs. This is a raw retained-history view; use held relation
267    /// iterators for ordinary reads. Tombstone-only buckets remain included.
268    pub fn surface_relation_buckets(
269        &self,
270    ) -> impl Iterator<Item = (EdgeKey, NodeKey, NodeKey, &EdgePayload)> + '_ {
271        self.inner
272            .inner()
273            .edge_references()
274            .map(|edge| (edge.id(), edge.source(), edge.target(), edge.weight()))
275    }
276
277    /// Held Surface buckets outgoing from `from`, including every parallel
278    /// bucket without expanding its assertions. Cost is proportional to the
279    /// node's out-degree.
280    pub fn surface_outgoing_relation_buckets(
281        &self,
282        from: NodeKey,
283    ) -> impl Iterator<Item = (EdgeKey, NodeKey, NodeKey, &EdgePayload)> + '_ {
284        self.inner
285            .inner()
286            .edges_directed(from, Direction::Outgoing)
287            .map(|edge| (edge.id(), edge.source(), edge.target(), edge.weight()))
288    }
289
290    /// Surface relations followed by content relations lifted to every pair of
291    /// surfaces showing their endpoints. The handle retains its owning store;
292    /// projection does not copy resource assertions into the surface graph.
293    pub fn projected_relations(&self) -> impl Iterator<Item = (RelationKey, RelationView)> + '_ {
294        let surfaces = self.inner.inner().edge_references().flat_map(|edge| {
295            let key = RelationKey::Surface(edge.id());
296            relation_rows(edge.source(), edge.target(), edge.weight())
297                .into_iter()
298                .map(move |row| (key, row))
299        });
300        let resources = self
301            .resource_relations()
302            .flat_map(|(key, from, to, payload)| {
303                let sources = self.surface_ids_showing_resource(from);
304                let targets = self.surface_ids_showing_resource(to);
305                let mut rows = Vec::new();
306                for source in sources {
307                    let Some(source) = self.get_node_key_by_id(source) else {
308                        continue;
309                    };
310                    for target in &targets {
311                        let Some(target) = self.get_node_key_by_id(*target) else {
312                            continue;
313                        };
314                        rows.extend(
315                            relation_rows(source, target, payload)
316                                .into_iter()
317                                .map(|row| (RelationKey::Resource(key), row)),
318                        );
319                    }
320                }
321                rows
322            });
323        surfaces.chain(resources)
324    }
325
326    /// Every exact held assertion lifted to its displayed endpoint pairs.
327    /// Traversal remains an event rollup and is not an assertion record.
328    pub fn projected_assertions(
329        &self,
330    ) -> impl Iterator<Item = (RelationKey, NodeKey, NodeKey, &super::SemanticStatement)> + '_ {
331        let surfaces = self.inner.inner().edge_references().flat_map(|edge| {
332            let (key, from, to) = (
333                RelationKey::Surface(edge.id()),
334                edge.source(),
335                edge.target(),
336            );
337            edge.weight()
338                .held_assertions()
339                .map(move |record| (key, from, to, record))
340        });
341        let resources =
342            self.resource_relations()
343                .flat_map(|(key, from, to, payload)| {
344                    let mut rows = Vec::new();
345                    for source in self.surface_ids_showing_resource(from) {
346                        let Some(source) = self.get_node_key_by_id(source) else {
347                            continue;
348                        };
349                        for target in self.surface_ids_showing_resource(to) {
350                            let Some(target) = self.get_node_key_by_id(target) else {
351                                continue;
352                            };
353                            rows.extend(payload.held_assertions().map(|record| {
354                                (RelationKey::Resource(key), source, target, record)
355                            }));
356                        }
357                    }
358                    rows
359                });
360        surfaces.chain(resources)
361    }
362
363    /// Relations whose `from` endpoint is `key`, expanded with exactly the
364    /// row semantics of [`Self::relations`] but visiting only that node's
365    /// outgoing edges. Cost is proportional to the node's out-degree, not
366    /// the graph's edge count.
367    pub fn outgoing_relations(&self, key: NodeKey) -> impl Iterator<Item = RelationView> + '_ {
368        self.inner
369            .inner()
370            .edges_directed(key, Direction::Outgoing)
371            .flat_map(|edge| relation_rows(edge.source(), edge.target(), edge.weight()))
372    }
373
374    /// Relations whose `to` endpoint is `key`, expanded with exactly the
375    /// row semantics of [`Self::relations`] but visiting only that node's
376    /// incoming edges. Cost is proportional to the node's in-degree, not
377    /// the graph's edge count.
378    pub fn incoming_relations(&self, key: NodeKey) -> impl Iterator<Item = RelationView> + '_ {
379        self.inner
380            .inner()
381            .edges_directed(key, Direction::Incoming)
382            .flat_map(|edge| relation_rows(edge.source(), edge.target(), edge.weight()))
383    }
384
385    pub fn semantic_edges(&self) -> impl Iterator<Item = SemanticEdgeView> + '_ {
386        self.inner.inner().edge_references().flat_map(|edge| {
387            let from = edge.source();
388            let to = edge.target();
389            let payload = edge.weight();
390            payload
391                .held_semantic_statements()
392                .filter_map(|statement| {
393                    statement
394                        .recognized_sub_kind
395                        .map(|sub_kind| SemanticEdgeView {
396                            from,
397                            to,
398                            sub_kind,
399                            label: statement.label.clone(),
400                        })
401                })
402                .collect::<Vec<_>>()
403                .into_iter()
404        })
405    }
406
407    pub fn arrangement_edges(&self) -> impl Iterator<Item = ArrangementEdgeView> + '_ {
408        self.inner.inner().edge_references().flat_map(|e| {
409            let from = e.source();
410            let to = e.target();
411            e.weight()
412                .arrangement_data()
413                .map(|data| {
414                    data.sub_kinds
415                        .into_iter()
416                        .map(move |sub_kind| ArrangementEdgeView { from, to, sub_kind })
417                })
418                .into_iter()
419                .flatten()
420        })
421    }
422
423    pub fn containment_edges(&self) -> impl Iterator<Item = ContainmentEdgeView> + '_ {
424        self.inner.inner().edge_references().flat_map(|e| {
425            let from = e.source();
426            let to = e.target();
427            e.weight()
428                .containment_data()
429                .map(|data| {
430                    data.sub_kinds
431                        .into_iter()
432                        .map(move |sub_kind| ContainmentEdgeView { from, to, sub_kind })
433                })
434                .into_iter()
435                .flatten()
436        })
437    }
438
439    /// Derive the containment this one node's address implies, at the moment
440    /// the node is created.
441    ///
442    /// Current relation routing stores this assertion on Resources. Ordinary
443    /// snapshot loading separately rebuilds compatibility Surface containment;
444    /// recorded loading preserves stored relations without that rebuild. Both
445    /// strata are included in snapshots.
446    ///
447    /// The **UrlPath half** of [`rebuild_derived_containment_relations`],
448    /// applied to a single node. It exists because that rebuild runs only on
449    /// snapshot load, which used to mean a node visited under a folder had no
450    /// containment edge until the session was saved and reloaded. Anything
451    /// reading containment live (a graph behavior's watch, which names a
452    /// region by its container) saw nothing there. Deriving at creation makes
453    /// the local relation available before the first save.
454    ///
455    /// The **Domain half is deliberately not here.** A domain anchor is the
456    /// shallowest node on a host, so minting one node can re-anchor every
457    /// other node sharing that host: a whole-graph fact, which stays with the
458    /// whole-graph rebuild. This one is purely local, which is what makes it
459    /// cheap enough to run per node.
460    pub fn derive_containment_for(&mut self, key: NodeKey) {
461        let Some(node) = self.get_node(key) else {
462            return;
463        };
464        let Ok(parsed) = url::Url::parse(node.url()) else {
465            return;
466        };
467        let Some(parent_url) = containment_parent_url(&parsed) else {
468            return;
469        };
470        let Some((parent_key, _)) = self.get_node_by_url(&parent_url) else {
471            return;
472        };
473        if parent_key == key {
474            return;
475        }
476        // Child to container, the direction the rebuild uses.
477        let _ = self.assert_relation(
478            key,
479            parent_key,
480            EdgeAssertion::Containment {
481                sub_kind: ContainmentSubKind::UrlPath,
482            },
483        );
484    }
485
486    pub(crate) fn rebuild_derived_containment_relations(&mut self) {
487        let edge_ids: Vec<EdgeKey> = self.inner.inner().edge_indices().collect();
488        let mut empty_edges = Vec::new();
489        // This rebuild replaces only held, positively rule-marked containment
490        // rows on `inner` (bypassing the bumping API), so track the structural
491        // change and bump once. The `assert_relation` calls below bump on their
492        // own when they re-derive the edges.
493        let mut changed = false;
494        for edge_id in edge_ids {
495            if let Some(payload) = self.inner.edge_mut(edge_id) {
496                let before = payload.assertions().len();
497                payload.assertions.statements.retain(|statement| {
498                    !(statement.is_held()
499                        && is_derived_containment_record(statement)
500                        && matches!(
501                            statement.relation_kind(),
502                            super::RelationKind::Containment(
503                                ContainmentSubKind::UrlPath | ContainmentSubKind::Domain
504                            )
505                        ))
506                });
507                let removed_any = payload.assertions().len() != before;
508                if removed_any {
509                    payload.assertions.rebuild_compat();
510                    changed = true;
511                }
512                if removed_any && payload.is_empty() {
513                    empty_edges.push(edge_id);
514                }
515            }
516        }
517        for edge_id in empty_edges {
518            let _ = self.inner.disconnect(edge_id);
519        }
520        if changed {
521            self.bump_revision();
522        }
523
524        // Resource assertions keep their recorded owner and metadata. The
525        // compatibility rebuild below retains its prior Surface-only behavior.
526
527        let mut domain_anchor: HashMap<String, (NodeKey, usize, Uuid)> = HashMap::new();
528        for (key, node) in self.nodes() {
529            let Ok(parsed) = url::Url::parse(node.url()) else {
530                continue;
531            };
532            let depth = parsed.path_segments().map_or(0, |segments| {
533                segments.filter(|segment| !segment.is_empty()).count()
534            });
535
536            let Some(host) = parsed.host_str() else {
537                continue;
538            };
539            let host = host.to_ascii_lowercase();
540            let candidate = (key, depth, node.id);
541            domain_anchor
542                .entry(host)
543                .and_modify(|current| {
544                    if candidate.1 < current.1
545                        || (candidate.1 == current.1 && candidate.2 < current.2)
546                    {
547                        *current = candidate;
548                    }
549                })
550                .or_insert(candidate);
551        }
552
553        let mut url_parent_edges = Vec::new();
554        let mut domain_edges = Vec::new();
555        for (key, node) in self.nodes() {
556            let Ok(parsed) = url::Url::parse(node.url()) else {
557                continue;
558            };
559
560            if let Some(parent_url) = containment_parent_url(&parsed)
561                && let Some((parent_key, _)) = self.get_node_by_url(&parent_url)
562                && parent_key != key
563            {
564                url_parent_edges.push((key, parent_key));
565            }
566
567            if let Some(host) = parsed.host_str() {
568                let host = host.to_ascii_lowercase();
569                if let Some((anchor_key, _, _)) = domain_anchor.get(&host)
570                    && *anchor_key != key
571                {
572                    domain_edges.push((key, *anchor_key));
573                }
574            }
575        }
576
577        for (from, to) in url_parent_edges {
578            let _ = self.assert_surface_relation_as(
579                from,
580                to,
581                EdgeAssertion::Containment {
582                    sub_kind: ContainmentSubKind::UrlPath,
583                },
584                self.write_author().asserter_iri(),
585                None,
586            );
587        }
588        for (from, to) in domain_edges {
589            let _ = self.assert_surface_relation_as(
590                from,
591                to,
592                EdgeAssertion::Containment {
593                    sub_kind: ContainmentSubKind::Domain,
594                },
595                self.write_author().asserter_iri(),
596                None,
597            );
598        }
599    }
600
601    /// Iterate outgoing neighbor keys for a node
602    pub fn out_neighbors(&self, key: NodeKey) -> impl Iterator<Item = NodeKey> + '_ {
603        self.inner
604            .inner()
605            .edges_directed(key, Direction::Outgoing)
606            .filter(|edge| edge.weight().has_held_topology())
607            .map(|edge| edge.target())
608    }
609
610    /// Iterate incoming neighbor keys for a node
611    pub fn in_neighbors(&self, key: NodeKey) -> impl Iterator<Item = NodeKey> + '_ {
612        self.inner
613            .inner()
614            .edges_directed(key, Direction::Incoming)
615            .filter(|edge| edge.weight().has_held_topology())
616            .map(|edge| edge.source())
617    }
618
619    /// Iterate undirected neighbor keys for a node, Surface stratum only.
620    /// [`projected_neighbors`](Self::projected_neighbors) reads both strata.
621    pub fn neighbors_undirected(&self, key: NodeKey) -> impl Iterator<Item = NodeKey> + '_ {
622        let inner = self.inner.inner();
623        let outgoing = inner
624            .edges_directed(key, Direction::Outgoing)
625            .filter(|edge| edge.weight().has_held_topology())
626            .map(|edge| edge.target());
627        let incoming = inner
628            .edges_directed(key, Direction::Incoming)
629            .filter(|edge| edge.weight().has_held_topology() && edge.source() != edge.target())
630            .map(|edge| edge.source());
631        outgoing.chain(incoming)
632    }
633
634    /// Every node adjacent to `key` in either direction across both strata: the
635    /// Surface neighbours, plus the surfaces showing the far end of each Resource
636    /// relation of the resource `key` shows. One entry per incident held relation,
637    /// so parallel relations repeat; a self-loop is read once, from its outgoing
638    /// side, so a node adjacent to itself appears once. Hides are a view concern
639    /// and do not apply here.
640    pub fn projected_neighbors(&self, key: NodeKey) -> impl Iterator<Item = NodeKey> + '_ {
641        let incoming = self
642            .projected_incoming_relations(key)
643            .filter(|(_, relation, _)| !self.is_self_loop(*relation));
644        self.projected_outgoing_relations(key)
645            .chain(incoming)
646            .map(|(neighbor, _, _)| neighbor)
647    }
648
649    /// Whether `relation` joins one node, or one resource, to itself.
650    fn is_self_loop(&self, relation: RelationKey) -> bool {
651        match relation {
652            RelationKey::Surface(edge) => self
653                .inner
654                .inner()
655                .edge_endpoints(edge)
656                .is_some_and(|(from, to)| from == to),
657            RelationKey::Resource(edge) => self
658                .resources
659                .inner()
660                .edge_endpoints(edge.raw())
661                .is_some_and(|(from, to)| from == to),
662        }
663    }
664
665    /// Undirected neighbors sorted by stable node-key order.
666    pub fn neighbors_undirected_sorted(&self, key: NodeKey) -> Vec<NodeKey> {
667        let mut neighbors: Vec<NodeKey> = self
668            .neighbors_undirected(key)
669            .filter(|neighbor| *neighbor != key && self.get_node(*neighbor).is_some())
670            .collect::<HashSet<_>>()
671            .into_iter()
672            .collect();
673        neighbors.sort_by_key(|neighbor| neighbor.index());
674        neighbors
675    }
676
677    /// Seed nodes plus one-hop undirected neighbors for frame import workflows.
678    pub fn connected_frame_import_nodes(&self, seeds: &[NodeKey]) -> Vec<NodeKey> {
679        let mut out = HashSet::new();
680        for seed in seeds {
681            if self.get_node(*seed).is_none() {
682                continue;
683            }
684            out.insert(*seed);
685            out.extend(self.neighbors_undirected(*seed));
686        }
687        let mut nodes: Vec<NodeKey> = out
688            .into_iter()
689            .filter(|key| self.get_node(*key).is_some())
690            .collect();
691        nodes.sort_by_key(|key| key.index());
692        nodes
693    }
694
695    /// Connected candidate expansion around a source node with depth annotations.
696    ///
697    /// `max_depth` currently supports 1 or 2, matching connected-open scope behavior.
698    pub fn connected_candidates_with_depth(
699        &self,
700        source: NodeKey,
701        max_depth: u8,
702    ) -> Vec<(NodeKey, u8)> {
703        if self.get_node(source).is_none() || max_depth == 0 {
704            return Vec::new();
705        }
706
707        let mut out = Vec::new();
708        let mut visited = HashSet::from([source]);
709
710        let depth1 = self.neighbors_undirected_sorted(source);
711        for neighbor in depth1 {
712            if visited.insert(neighbor) {
713                out.push((neighbor, 1));
714            }
715        }
716
717        if max_depth < 2 {
718            return out;
719        }
720
721        let depth1_nodes: Vec<NodeKey> = out
722            .iter()
723            .filter_map(|(node, depth)| (*depth == 1).then_some(*node))
724            .collect();
725        for depth1_node in depth1_nodes {
726            for neighbor in self.neighbors_undirected_sorted(depth1_node) {
727                if visited.insert(neighbor) {
728                    out.push((neighbor, 2));
729                }
730            }
731        }
732
733        out
734    }
735
736    /// Undirected hop distances from `source` using unit edge weights.
737    pub fn hop_distances_from(&self, source: NodeKey) -> HashMap<NodeKey, usize> {
738        if self.get_node(source).is_none() {
739            return HashMap::new();
740        }
741        let mut distances = HashMap::from([(source, 0)]);
742        let mut queue = VecDeque::from([source]);
743        while let Some(node) = queue.pop_front() {
744            let next_distance = distances[&node] + 1;
745            for neighbor in self.neighbors_undirected(node) {
746                if let std::collections::hash_map::Entry::Vacant(entry) = distances.entry(neighbor)
747                {
748                    entry.insert(next_distance);
749                    queue.push_back(neighbor);
750                }
751            }
752        }
753        distances
754    }
755
756    /// Nodes with no incoming or outgoing edges.
757    pub fn orphan_node_keys(&self) -> Vec<NodeKey> {
758        self.inner
759            .inner()
760            .node_indices()
761            .filter(|&key| self.neighbors_undirected(key).next().is_none())
762            .collect()
763    }
764
765    /// Shortest undirected path between two nodes using unit edge weights.
766    pub fn shortest_path(&self, from: NodeKey, to: NodeKey) -> Option<Vec<NodeKey>> {
767        if self.get_node(from).is_none() || self.get_node(to).is_none() {
768            return None;
769        }
770        let mut previous = HashMap::from([(from, from)]);
771        let mut queue = VecDeque::from([from]);
772        while let Some(node) = queue.pop_front() {
773            if node == to {
774                break;
775            }
776            for neighbor in self.neighbors_undirected(node) {
777                if let std::collections::hash_map::Entry::Vacant(entry) = previous.entry(neighbor) {
778                    entry.insert(node);
779                    queue.push_back(neighbor);
780                }
781            }
782        }
783        if !previous.contains_key(&to) {
784            return None;
785        }
786        let mut path = vec![to];
787        while *path.last().unwrap() != from {
788            path.push(previous[path.last().unwrap()]);
789        }
790        path.reverse();
791        Some(path)
792    }
793
794    /// Reachability in the undirected graph.
795    pub fn is_reachable(&self, from: NodeKey, to: NodeKey) -> bool {
796        if self.get_node(from).is_none() || self.get_node(to).is_none() {
797            return false;
798        }
799        self.shortest_path(from, to).is_some()
800    }
801
802    /// Weakly connected components of the surface stratum (undirected projection),
803    /// a topology metric like [`Self::orphan_node_keys`]. Resource relations and
804    /// shown bindings do not join here; the semantic Component is
805    /// [`Self::component_members`].
806    pub fn weakly_connected_components(&self) -> Vec<Vec<NodeKey>> {
807        let mut visited = HashSet::new();
808        let mut components = Vec::new();
809        for start in self.inner.inner().node_indices() {
810            if !visited.insert(start) {
811                continue;
812            }
813            let mut component = Vec::new();
814            let mut stack = vec![start];
815            while let Some(current) = stack.pop() {
816                component.push(current);
817                for neighbor in self.neighbors_undirected(current) {
818                    if visited.insert(neighbor) {
819                        stack.push(neighbor);
820                    }
821                }
822            }
823            components.push(component);
824        }
825        components
826    }
827
828    /// Surfaces reachable from `seed` through either stratum's undirected relations.
829    /// Shown bindings join at zero hops, including through unshown resources.
830    /// Empty if `seed` is not a surface in the graph. `selectors` is the
831    /// **edge projection**: only edges matching a selector are followed (an empty slice
832    /// follows every family). So the *same* nodes can be one Component under one projection
833    /// and a different one under another. The **Component** subgraph's derivation. (Subgraph
834    /// derivation, Phase 3 — selectors.)
835    pub fn component_members(
836        &self,
837        seed: uuid::Uuid,
838        selectors: &[super::RelationSelector],
839    ) -> Vec<uuid::Uuid> {
840        self.bfs_members(seed, None, selectors)
841    }
842
843    /// The **Ego** neighborhood of `seed`: surfaces within `radius` undirected
844    /// relation hops across both strata. Shown bindings cost zero, so radius 0
845    /// also includes surfaces showing the seed's resource. Uses the `selectors`
846    /// edge projection (empty = all families). The Ego subgraph's derivation. (Subgraph
847    /// derivation, Phase 3 — selectors.)
848    pub fn ego_members(
849        &self,
850        seed: uuid::Uuid,
851        radius: u8,
852        selectors: &[super::RelationSelector],
853    ) -> Vec<uuid::Uuid> {
854        self.bfs_members(seed, Some(radius), selectors)
855    }
856
857    /// Collapse zero-hop shown bindings, then walk relation hops breadth-first.
858    fn bfs_members(
859        &self,
860        seed: uuid::Uuid,
861        max_depth: Option<u8>,
862        selectors: &[super::RelationSelector],
863    ) -> Vec<uuid::Uuid> {
864        let Some((start, _)) = self.get_node_by_id(seed) else {
865            return Vec::new();
866        };
867        #[derive(Clone, Copy, PartialEq, Eq, PartialOrd, Ord, Hash)]
868        enum WalkNode {
869            Surface(NodeKey),
870            Resource(Uuid),
871        }
872        let owner = |surface| {
873            self.shown_resource_id(surface)
874                .filter(|resource| self.resource(*resource).is_some())
875                .map(WalkNode::Resource)
876                .unwrap_or(WalkNode::Surface(surface))
877        };
878        let mut shown = HashMap::<Uuid, Vec<NodeKey>>::new();
879        for (key, _) in self.nodes() {
880            if let WalkNode::Resource(resource) = owner(key) {
881                shown.entry(resource).or_default().push(key);
882            }
883        }
884        for surfaces in shown.values_mut() {
885            surfaces.sort_by_key(|key| key.index());
886        }
887        let start = owner(start);
888        let mut seen = HashSet::new();
889        let mut order = Vec::new();
890        let mut queue = VecDeque::new();
891        seen.insert(start);
892        queue.push_back((start, 0usize));
893        while let Some((current, depth)) = queue.pop_front() {
894            let surfaces = match current {
895                WalkNode::Surface(key) => vec![key],
896                WalkNode::Resource(resource) => shown.get(&resource).cloned().unwrap_or_default(),
897            };
898            if current == start {
899                order.push(seed);
900            }
901            for key in &surfaces {
902                let id = self.get_node(*key).expect("walk surface exists").id;
903                if id != seed {
904                    order.push(id);
905                }
906            }
907            if max_depth.is_some_and(|m| depth >= usize::from(m)) {
908                continue;
909            }
910            let mut neighbors = Vec::new();
911            for key in surfaces {
912                for neighbor in self.neighbors_undirected_sorted(key) {
913                    if selectors.is_empty() || self.edge_matches_selectors(key, neighbor, selectors)
914                    {
915                        neighbors.push(owner(neighbor));
916                    }
917                }
918            }
919            if let WalkNode::Resource(resource) = current {
920                let key = self
921                    .resources
922                    .key_of(&resource)
923                    .expect("walk resource exists");
924                for direction in [Direction::Outgoing, Direction::Incoming] {
925                    for edge in self.resources.inner().edges_directed(key, direction) {
926                        if !edge.weight().has_held_topology() {
927                            continue;
928                        }
929                        if !selectors.is_empty()
930                            && !selectors
931                                .iter()
932                                .any(|&selector| edge.weight().has_relation(selector))
933                        {
934                            continue;
935                        }
936                        let neighbor = match direction {
937                            Direction::Outgoing => edge.target(),
938                            Direction::Incoming => edge.source(),
939                        };
940                        neighbors.push(WalkNode::Resource(
941                            self.resources
942                                .node(neighbor)
943                                .expect("resource endpoint exists")
944                                .id(),
945                        ));
946                    }
947                }
948            }
949            neighbors.sort_unstable();
950            neighbors.dedup();
951            for neighbor in neighbors {
952                if seen.insert(neighbor) {
953                    queue.push_back((neighbor, depth + 1));
954                }
955            }
956        }
957        order
958    }
959
960    /// Whether any edge between `a` and `b` (either direction, every
961    /// parallel edge) matches any of `selectors` (a relation family or
962    /// sub-kind). Used by the selector-projected derivation walk. Scans
963    /// the whole pair via [`Self::edges_between_undirected`] so an
964    /// antiparallel pair with different families (a->b Semantic, b->a
965    /// Traversal) is crossed from either end (Q2 ruling, 2026-09-12).
966    fn edge_matches_selectors(
967        &self,
968        a: NodeKey,
969        b: NodeKey,
970        selectors: &[super::RelationSelector],
971    ) -> bool {
972        self.edges_between_undirected(a, b)
973            .any(|(_, payload)| selectors.iter().any(|&s| payload.has_relation(s)))
974    }
975
976    /// Strongly connected components in the directed graph.
977    pub fn strongly_connected_components(&self) -> Vec<Vec<NodeKey>> {
978        let mut active = DiGraph::<(), ()>::new();
979        let mut keys = Vec::new();
980        let mut mapped = HashMap::new();
981        for key in self.inner.inner().node_indices() {
982            let mapped_key = active.add_node(());
983            keys.push(key);
984            mapped.insert(key, mapped_key);
985        }
986        for edge in self
987            .inner
988            .inner()
989            .edge_references()
990            .filter(|edge| edge.weight().has_held_topology())
991        {
992            active.add_edge(mapped[&edge.source()], mapped[&edge.target()], ());
993        }
994        kosaraju_scc(&active)
995            .into_iter()
996            .map(|component| {
997                component
998                    .into_iter()
999                    .map(|node| keys[node.index()])
1000                    .collect()
1001            })
1002            .collect()
1003    }
1004
1005    /// Check if a directed edge exists from `from` to `to`
1006    pub fn has_edge_between(&self, from: NodeKey, to: NodeKey) -> bool {
1007        self.inner
1008            .inner()
1009            .edges_connecting(from, to)
1010            .any(|edge| edge.weight().has_held_topology())
1011    }
1012
1013    /// Count of nodes in the graph
1014    pub fn node_count(&self) -> usize {
1015        self.inner.node_count()
1016    }
1017
1018    /// Count of retained Surface buckets, including tombstone-only history.
1019    /// Use held topology queries when asking how many relations are active.
1020    pub fn edge_count(&self) -> usize {
1021        self.inner.edge_count()
1022    }
1023}
1024
1025/// Only rows positively identified as outputs of the containment rule may be
1026/// replaced by a current derivation. Same-predicate authored/imported rows
1027/// remain retained graph facts.
1028pub(crate) fn is_derived_containment_record(statement: &super::SemanticStatement) -> bool {
1029    statement.basis.method.as_ref().is_some_and(|method| {
1030        method.iri == "urn:mere:method:derived-containment"
1031            && method.version.as_deref() == Some("1")
1032    })
1033}
1034
1035#[cfg(test)]
1036mod derivation_tests {
1037    use super::*;
1038    use crate::graph::SemanticSubKind;
1039    use euclid::default::Point2D;
1040
1041    #[test]
1042    fn shown_joins_cost_zero_and_hidden_resources_carry_relation_hops() {
1043        use crate::graph::{EdgeFamily, NavigationTrigger, ResourceNode, SemanticStatement};
1044        use crate::persistence::PersistedResourceRecord;
1045        use crate::types::GraphScope;
1046
1047        let mut graph = Graph::new();
1048        let [ra, hidden, rc] = ["a", "hidden", "c"].map(|name| {
1049            let iri = format!("https://resource.test/{name}");
1050            let resource = ResourceNode::for_term(&iri);
1051            assert!(graph.set_resource_record(
1052                resource.id(),
1053                Some(PersistedResourceRecord {
1054                    canonical_iri: iri,
1055                    facets: vec![],
1056                })
1057            ));
1058            resource.id()
1059        });
1060        let [a, alias, c, d, isolated] = std::array::from_fn::<_, 5, _>(|i| {
1061            // Equal UUIDs in different strata must not join accidentally.
1062            let id = if i == 3 {
1063                hidden
1064            } else {
1065                Uuid::from_u128(100 + i as u128)
1066            };
1067            graph.add_node_with_id(id, format!("https://surface.test/{i}"), Default::default())
1068        });
1069        let ids = [a, alias, c, d, isolated].map(|key| graph.get_node(key).unwrap().id);
1070        for (key, resource) in [(a, ra), (alias, ra), (c, rc)] {
1071            assert!(graph.set_shown_resource(graph.get_node(key).unwrap().id, Some(resource)));
1072        }
1073        for (from, to, kinds) in [
1074            (
1075                ra,
1076                hidden,
1077                vec![SemanticSubKind::Cites, SemanticSubKind::Quotes],
1078            ),
1079            (rc, hidden, vec![SemanticSubKind::Cites]),
1080            (hidden, hidden, vec![SemanticSubKind::Cites]),
1081        ] {
1082            let records: Vec<_> = kinds
1083                .into_iter()
1084                .enumerate()
1085                .map(|(i, kind)| {
1086                    let mut payload = EdgePayload::new();
1087                    payload.push_persisted_semantic_statement(SemanticStatement {
1088                        statement_id: format!("walk:{from}:{to}:{i}"),
1089                        predicate: crate::graph::predicate_iri(kind).into(),
1090                        recognized_sub_kind: Some(kind),
1091                        label: Some("retained".into()),
1092                        graph_scope: GraphScope::Custom("https://scope.test/walk".into()),
1093                        provenance_iri: Some("https://author.test/walk".into()),
1094                        asserted_at_ms: Some(17),
1095                        first_asserted_ms: Some(17),
1096                        withdrawn: None,
1097                        basis: Default::default(),
1098                    });
1099                    super::super::snapshot::persisted_edge_for_ids(from, to, &payload)
1100                })
1101                .collect();
1102            assert!(graph.set_resource_edges_between(from, to, &records));
1103        }
1104        assert!(graph.append_traversal(c, d, NavigationTrigger::LinkClick, Some(19)));
1105        let before = graph.to_snapshot();
1106        let revision = graph.revision();
1107        let [a_id, alias_id, c_id, d_id, isolated_id] = ids;
1108        let semantic = [RelationSelector::Family(EdgeFamily::Semantic)];
1109        let traversal = [RelationSelector::Family(EdgeFamily::Traversal)];
1110        assert_eq!(graph.ego_members(a_id, 0, &[]), vec![a_id, alias_id]);
1111        assert_eq!(graph.ego_members(alias_id, 0, &[]), vec![alias_id, a_id]);
1112        assert_eq!(graph.ego_members(a_id, 1, &[]), vec![a_id, alias_id]);
1113        assert_eq!(graph.ego_members(a_id, 2, &[]), vec![a_id, alias_id, c_id]);
1114        assert_eq!(
1115            graph.ego_members(a_id, 3, &[]),
1116            vec![a_id, alias_id, c_id, d_id]
1117        );
1118        assert_eq!(
1119            graph.component_members(a_id, &semantic),
1120            vec![a_id, alias_id, c_id]
1121        );
1122        assert_eq!(
1123            graph.component_members(a_id, &traversal),
1124            vec![a_id, alias_id]
1125        );
1126        assert_eq!(
1127            graph.component_members(a_id, &[RelationSelector::Semantic(SemanticSubKind::Quotes)]),
1128            vec![a_id, alias_id]
1129        );
1130        assert_eq!(
1131            graph.component_members(c_id, &semantic),
1132            vec![c_id, a_id, alias_id]
1133        );
1134        assert_eq!(
1135            graph.component_members(a_id, &[]),
1136            vec![a_id, alias_id, c_id, d_id]
1137        );
1138        assert_eq!(graph.component_members(isolated_id, &[]), vec![isolated_id]);
1139        assert!(graph.component_members(Uuid::nil(), &[]).is_empty());
1140        assert_eq!(graph.resource_relations().count(), 4);
1141        assert_eq!(
1142            serde_json::to_value(graph.to_snapshot()).unwrap(),
1143            serde_json::to_value(before).unwrap(),
1144            "walking retains all stored assertions"
1145        );
1146        assert_eq!(graph.revision(), revision, "walking is read-only");
1147    }
1148
1149    /// An A–B–C chain plus an isolated D. Returns the graph and `[a, b, c, d]` uuids.
1150    fn chain_plus_isolate() -> (Graph, [uuid::Uuid; 4]) {
1151        let mut g = Graph::new();
1152        let a = g.add_node("https://a".to_string(), Point2D::new(0.0, 0.0));
1153        let b = g.add_node("https://b".to_string(), Point2D::new(1.0, 0.0));
1154        let c = g.add_node("https://c".to_string(), Point2D::new(2.0, 0.0));
1155        let d = g.add_node("https://d".to_string(), Point2D::new(9.0, 9.0));
1156        let sem = || EdgeAssertion::Semantic {
1157            sub_kind: SemanticSubKind::Hyperlink,
1158            label: None,
1159        };
1160        g.assert_relation(a, b, sem());
1161        g.assert_relation(b, c, sem());
1162        let ids = [
1163            g.get_node(a).unwrap().id,
1164            g.get_node(b).unwrap().id,
1165            g.get_node(c).unwrap().id,
1166            g.get_node(d).unwrap().id,
1167        ];
1168        (g, ids)
1169    }
1170
1171    #[test]
1172    fn component_members_is_the_whole_connected_component() {
1173        let (g, [a, _b, _c, d]) = chain_plus_isolate();
1174        assert_eq!(g.component_members(a, &[]).len(), 3, "A reaches B and C");
1175        assert_eq!(g.component_members(d, &[]).len(), 1, "D is isolated");
1176        assert!(
1177            g.component_members(uuid::Uuid::nil(), &[]).is_empty(),
1178            "unknown seed: empty"
1179        );
1180    }
1181
1182    #[test]
1183    fn ego_members_is_radius_bounded() {
1184        let (g, [a, _b, _c, _d]) = chain_plus_isolate();
1185        assert_eq!(
1186            g.ego_members(a, 0, &[]).len(),
1187            1,
1188            "radius 0 is just the seed"
1189        );
1190        assert_eq!(
1191            g.ego_members(a, 1, &[]).len(),
1192            2,
1193            "radius 1 reaches B, not C"
1194        );
1195        assert_eq!(g.ego_members(a, 2, &[]).len(), 3, "radius 2 reaches C");
1196    }
1197
1198    #[test]
1199    fn the_selector_projection_changes_the_derived_shape() {
1200        use crate::graph::{ContainmentSubKind, EdgeFamily, RelationSelector};
1201        // A —Semantic→ B —Containment→ C. The same three nodes, two relation families.
1202        let mut g = Graph::new();
1203        let a = g.add_node("https://a".to_string(), Point2D::new(0.0, 0.0));
1204        let b = g.add_node("https://b".to_string(), Point2D::new(1.0, 0.0));
1205        let c = g.add_node("https://c".to_string(), Point2D::new(2.0, 0.0));
1206        g.assert_relation(
1207            a,
1208            b,
1209            EdgeAssertion::Semantic {
1210                sub_kind: SemanticSubKind::Hyperlink,
1211                label: None,
1212            },
1213        );
1214        g.assert_relation(
1215            b,
1216            c,
1217            EdgeAssertion::Containment {
1218                sub_kind: ContainmentSubKind::CollectionMember,
1219            },
1220        );
1221        let a_id = g.get_node(a).unwrap().id;
1222
1223        let semantic = [RelationSelector::Family(EdgeFamily::Semantic)];
1224        let containment = [RelationSelector::Family(EdgeFamily::Containment)];
1225        // Whole graph under no projection; Semantic stops at B; Containment never leaves A.
1226        assert_eq!(
1227            g.component_members(a_id, &[]).len(),
1228            3,
1229            "all families: A, B, C"
1230        );
1231        assert_eq!(
1232            g.component_members(a_id, &semantic).len(),
1233            2,
1234            "Semantic projection: A, B (B→C is Containment, not followed)"
1235        );
1236        assert_eq!(
1237            g.component_members(a_id, &containment).len(),
1238            1,
1239            "Containment projection: just A (no Containment edge from A)"
1240        );
1241    }
1242
1243    /// Q2 (ruled 2026-09-12): an antiparallel pair carrying different
1244    /// families on each arc (n1->n2 Semantic hyperlink, n2->n1 Traversal,
1245    /// the shape `tests/snapshot_basic.rs::test_snapshot_preserves_edge_types`
1246    /// pins as two separate edges) is crossed by a selector-projected walk
1247    /// from either end, because `edge_matches_selectors` scans the whole
1248    /// pair rather than the first arc `find_edge_key` happens to return.
1249    #[test]
1250    fn antiparallel_pair_is_crossed_from_either_end() {
1251        use crate::graph::{EdgeFamily, NavigationTrigger, RelationSelector};
1252        let mut g = Graph::new();
1253        let n1 = g.add_node("https://a".to_string(), Point2D::new(0.0, 0.0));
1254        let n2 = g.add_node("https://b".to_string(), Point2D::new(1.0, 0.0));
1255        g.assert_relation(
1256            n1,
1257            n2,
1258            EdgeAssertion::Semantic {
1259                sub_kind: SemanticSubKind::Hyperlink,
1260                label: None,
1261            },
1262        );
1263        assert!(g.append_traversal(n2, n1, NavigationTrigger::LinkClick, Some(1_000_000)));
1264        assert_eq!(g.edge_count(), 1, "Traversal remains Surface");
1265        assert_eq!(
1266            g.resource_relations().count(),
1267            1,
1268            "Hyperlink belongs to Resource"
1269        );
1270        let pair: Vec<_> = g
1271            .projected_relations_between(n1, n2)
1272            .chain(g.projected_relations_between(n2, n1))
1273            .collect();
1274        assert_eq!(pair.len(), 2, "the pair primitive sees both arcs");
1275        assert_eq!(
1276            g.projected_relations_between(n2, n1)
1277                .chain(g.projected_relations_between(n1, n2))
1278                .count(),
1279            2,
1280            "and from the other end"
1281        );
1282        let id1 = g.get_node(n1).unwrap().id;
1283        let id2 = g.get_node(n2).unwrap().id;
1284
1285        for family in [EdgeFamily::Traversal, EdgeFamily::Semantic] {
1286            let sel = [RelationSelector::Family(family)];
1287            for (seed, other) in [(id1, id2), (id2, id1)] {
1288                let members = g.component_members(seed, &sel);
1289                assert!(
1290                    members.contains(&seed) && members.contains(&other),
1291                    "{family:?} projection seeded at {seed} must cross the pair; got {members:?}"
1292                );
1293            }
1294        }
1295        // A family on neither arc still excludes.
1296        let sel = [RelationSelector::Family(EdgeFamily::Containment)];
1297        assert_eq!(g.component_members(id1, &sel), vec![id1]);
1298        assert_eq!(g.component_members(id2, &sel), vec![id2]);
1299    }
1300}
1301
1302/// Q1 (ruled 2026-09-12): `has_family` / `families()` and the row set
1303/// from `relation_rows` agree for every family on every edge shape,
1304/// including the two that used to diverge (open-predicate-only Semantic,
1305/// event-free Traversal sidecar).
1306#[cfg(test)]
1307mod row_family_parity_tests {
1308    use super::*;
1309    use crate::graph::{
1310        ArrangementSubKind, EdgeFamily, ImportedSubKind, NavigationTrigger, ProvenanceSubKind,
1311        RelationKind, SemanticSubKind,
1312    };
1313    use euclid::default::Point2D;
1314    use std::collections::BTreeSet;
1315
1316    fn row_families(
1317        g: &Graph,
1318    ) -> Vec<(
1319        RelationKey,
1320        NodeKey,
1321        NodeKey,
1322        BTreeSet<EdgeFamily>,
1323        BTreeSet<EdgeFamily>,
1324    )> {
1325        g.nodes()
1326            .flat_map(|(from, _)| {
1327                g.projected_outgoing_relations(from)
1328                    .map(move |(to, key, payload)| {
1329                        let rows = relation_rows(from, to, payload);
1330                        let from_rows: BTreeSet<EdgeFamily> =
1331                            rows.iter().map(|r| r.kind.family()).collect();
1332                        (key, from, to, payload.families(), from_rows)
1333                    })
1334            })
1335            .collect()
1336    }
1337
1338    #[test]
1339    fn families_equal_row_families_for_every_edge_shape() {
1340        let mut g = Graph::new();
1341        let mut node = |g: &mut Graph, i: usize| {
1342            g.add_node(format!("https://n{i}"), Point2D::new(i as f32, 0.0))
1343        };
1344        let hub = node(&mut g, 0);
1345        let open = node(&mut g, 1);
1346        let hyper = node(&mut g, 2);
1347        let trav = node(&mut g, 3);
1348        let cont = node(&mut g, 4);
1349        let arr = node(&mut g, 5);
1350        let imp = node(&mut g, 6);
1351        let prov = node(&mut g, 7);
1352        let mixed = node(&mut g, 8);
1353        let sem = || EdgeAssertion::Semantic {
1354            sub_kind: SemanticSubKind::Hyperlink,
1355            label: None,
1356        };
1357
1358        // Open predicate only: Semantic to `has_family`, formerly no rows.
1359        let open_key = g
1360            .assert_semantic_predicate(hub, open, "https://schema.org/citation".to_string())
1361            .expect("open-predicate edge");
1362        g.assert_relation(hub, hyper, sem());
1363        assert!(g.append_traversal(hub, trav, NavigationTrigger::LinkClick, Some(1)));
1364        g.assert_relation(
1365            hub,
1366            cont,
1367            EdgeAssertion::Containment {
1368                sub_kind: ContainmentSubKind::CollectionMember,
1369            },
1370        );
1371        g.assert_relation(
1372            hub,
1373            arr,
1374            EdgeAssertion::Arrangement {
1375                sub_kind: ArrangementSubKind::FrameMember,
1376            },
1377        );
1378        g.assert_relation(
1379            hub,
1380            imp,
1381            EdgeAssertion::Imported {
1382                sub_kind: ImportedSubKind::BookmarkFolder,
1383            },
1384        );
1385        g.assert_relation(
1386            hub,
1387            prov,
1388            EdgeAssertion::Provenance {
1389                sub_kind: ProvenanceSubKind::ClippedFrom,
1390            },
1391        );
1392        // Historical mixed Surface payload remains readable beside live Resource claims.
1393        g.assert_surface_relation_as(hub, mixed, sem(), g.write_author().asserter_iri(), None);
1394        g.assert_surface_semantic_statement(
1395            hub,
1396            mixed,
1397            crate::graph::SemanticStatementSpec {
1398                predicate: "https://example.org/related".into(),
1399                ..Default::default()
1400            },
1401        );
1402        assert!(g.append_traversal(hub, mixed, NavigationTrigger::Back, Some(2)));
1403
1404        // The open-predicate edge yields exactly one OpenPredicate row.
1405        let open_rows = relation_rows(hub, open, g.get_relation(open_key).unwrap());
1406        assert_eq!(
1407            open_rows.iter().map(|r| r.kind).collect::<Vec<_>>(),
1408            vec![RelationKind::OpenPredicate]
1409        );
1410
1411        // Live graph: every edge agrees.
1412        for (_, from, to, families, from_rows) in row_families(&g) {
1413            assert_eq!(families, from_rows, "live edge {from:?}->{to:?}");
1414        }
1415
1416        // Event-free Traversal sidecar: unreachable from the writers
1417        // (`push_traversal` always records metrics), so reach it through
1418        // a snapshot whose traversal record has no events and zero
1419        // metrics. `has_family(Traversal)` is sidecar presence, and the
1420        // row must follow it.
1421        let mut snapshot = g.to_snapshot();
1422        let mut stripped = 0;
1423        for edge in &mut snapshot.edges {
1424            if let Some(t) = edge.traversal.as_mut() {
1425                t.traversals.clear();
1426                t.metrics = Default::default();
1427                stripped += 1;
1428            }
1429        }
1430        assert_eq!(stripped, 2, "the traversal-only edge and the mixed edge");
1431        let restored = Graph::from_snapshot(&snapshot);
1432        // Note: the restored graph is not asserted edge-for-edge equal to
1433        // the live one. `snapshot/from.rs` only restores `UrlPath` /
1434        // `Domain` containment sub-kinds, so the CollectionMember edge
1435        // does not come back; that gap predates this test and is not
1436        // what it pins. Parity is checked on every edge that survives.
1437        let mut saw_event_free_traversal = 0;
1438        let mut saw_open_predicate = 0;
1439        for (key, from, to, families, from_rows) in row_families(&restored) {
1440            assert_eq!(families, from_rows, "restored edge {from:?}->{to:?}");
1441            let payload = restored.get_relation(key).unwrap();
1442            if families.contains(&EdgeFamily::Traversal) {
1443                assert!(payload.traversals().is_empty());
1444                assert_eq!(payload.metrics().total_navigations, 0);
1445                saw_event_free_traversal += 1;
1446            }
1447            saw_open_predicate += relation_rows(from, to, payload)
1448                .iter()
1449                .filter(|r| r.kind == RelationKind::OpenPredicate)
1450                .count();
1451        }
1452        assert_eq!(
1453            saw_event_free_traversal, 2,
1454            "traversal-only and mixed edges"
1455        );
1456        assert_eq!(saw_open_predicate, 2, "open-predicate-only and mixed edges");
1457    }
1458
1459    #[test]
1460    fn open_predicate_tag_round_trips_and_keeps_the_semantic_family_byte() {
1461        let tag = RelationKind::OpenPredicate.tag();
1462        assert_eq!(
1463            tag >> 24,
1464            RelationKind::Semantic(SemanticSubKind::Hyperlink).tag() >> 24
1465        );
1466        assert_eq!(
1467            RelationKind::from_tag(tag),
1468            Some(RelationKind::OpenPredicate)
1469        );
1470        assert_eq!(RelationKind::OpenPredicate.family(), EdgeFamily::Semantic);
1471    }
1472}