1use 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
32fn 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 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); 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 pub fn get_node(&self, key: NodeKey) -> Option<&Node> {
190 self.inner.node(key)
191 }
192
193 pub(crate) fn get_node_mut(&mut self, key: NodeKey) -> Option<&mut Node> {
195 self.inner.node_mut(key)
196 }
197
198 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 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 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 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 pub fn get_node_key_by_id(&self, id: Uuid) -> Option<NodeKey> {
241 self.inner.key_of(&id)
242 }
243
244 pub fn nodes(&self) -> impl Iterator<Item = (NodeKey, &Node)> {
246 self.inner.nodes()
247 }
248
249 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 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 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 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 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 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 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 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 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 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 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 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 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 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 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 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 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 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 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 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 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 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 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 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 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 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 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 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 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 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 pub fn node_count(&self) -> usize {
1015 self.inner.node_count()
1016 }
1017
1018 pub fn edge_count(&self) -> usize {
1021 self.inner.edge_count()
1022 }
1023}
1024
1025pub(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 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 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 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 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 #[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 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#[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 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 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 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 for (_, from, to, families, from_rows) in row_families(&g) {
1413 assert_eq!(families, from_rows, "live edge {from:?}->{to:?}");
1414 }
1415
1416 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 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}