1use std::collections::{HashMap, HashSet, VecDeque};
15
16use petgraph::Direction;
17use petgraph::algo::{astar, dijkstra, has_path_connecting, kosaraju_scc};
18use petgraph::visit::{EdgeRef, IntoEdgeReferences, UndirectedAdaptor};
19use uuid::Uuid;
20
21use super::edge_taxonomy::{ContainmentSubKind, EdgeAssertion, RelationSelector};
22use super::identity::{EdgeKey, NodeKey};
23use super::node::Node;
24use super::snapshot::containment_parent_url;
25use super::{ArrangementEdgeView, ContainmentEdgeView, Graph, RelationView, SemanticEdgeView};
26
27impl Graph {
28 pub fn get_node(&self, key: NodeKey) -> Option<&Node> {
30 self.inner.node(key)
31 }
32
33 pub(crate) fn get_node_mut(&mut self, key: NodeKey) -> Option<&mut Node> {
35 self.inner.node_mut(key)
36 }
37
38 pub fn find_node_by_address(
48 &self,
49 address: &crate::address::Address,
50 ) -> Option<(NodeKey, &Node)> {
51 let url = address.as_url_str();
52 let key = self.url_to_nodes.get(url)?.last().copied()?;
53 Some((key, self.inner.node(key)?))
54 }
55
56 pub fn get_node_by_url(&self, url: &str) -> Option<(NodeKey, &Node)> {
64 let address = crate::address::address_from_url(url);
65 self.find_node_by_address(&address)
66 }
67
68 pub fn get_nodes_by_url(&self, url: &str) -> Vec<NodeKey> {
70 self.url_to_nodes.get(url).cloned().unwrap_or_default()
71 }
72
73 pub fn get_node_by_id(&self, id: Uuid) -> Option<(NodeKey, &Node)> {
75 let key = self.inner.key_of(&id)?;
76 Some((key, self.inner.node(key)?))
77 }
78
79 pub fn get_node_key_by_id(&self, id: Uuid) -> Option<NodeKey> {
81 self.inner.key_of(&id)
82 }
83
84 pub fn nodes(&self) -> impl Iterator<Item = (NodeKey, &Node)> {
86 self.inner.nodes()
87 }
88
89 pub fn relations(&self) -> impl Iterator<Item = RelationView> + '_ {
98 use super::edge_taxonomy::RelationKind;
99 self.inner.inner().edge_references().flat_map(|edge| {
100 let from = edge.source();
101 let to = edge.target();
102 let payload = edge.weight();
103 let mut out: Vec<RelationView> = Vec::new();
104 for statement in payload.semantic_statements() {
105 if let Some(sub_kind) = statement.recognized_sub_kind {
106 out.push(RelationView {
107 from,
108 to,
109 kind: RelationKind::Semantic(sub_kind),
110 });
111 }
112 }
113 if let Some(traversal) = payload.traversal_data()
118 && (!traversal.traversals.is_empty() || traversal.metrics.total_navigations > 0)
119 {
120 out.push(RelationView {
121 from,
122 to,
123 kind: RelationKind::Traversal,
124 });
125 }
126 if let Some(containment) = payload.containment_data() {
127 for &sub_kind in &containment.sub_kinds {
128 out.push(RelationView {
129 from,
130 to,
131 kind: RelationKind::Containment(sub_kind),
132 });
133 }
134 }
135 if let Some(arrangement) = payload.arrangement_data() {
136 for &sub_kind in &arrangement.sub_kinds {
137 out.push(RelationView {
138 from,
139 to,
140 kind: RelationKind::Arrangement(sub_kind),
141 });
142 }
143 }
144 if let Some(imported) = payload.imported_data() {
145 for &sub_kind in &imported.sub_kinds {
146 out.push(RelationView {
147 from,
148 to,
149 kind: RelationKind::Imported(sub_kind),
150 });
151 }
152 }
153 if let Some(prov) = payload.provenance_data() {
154 for &sub_kind in &prov.sub_kinds {
155 out.push(RelationView {
156 from,
157 to,
158 kind: RelationKind::Provenance(sub_kind),
159 });
160 }
161 }
162 out.into_iter()
163 })
164 }
165
166 pub fn semantic_edges(&self) -> impl Iterator<Item = SemanticEdgeView> + '_ {
167 self.inner.inner().edge_references().flat_map(|edge| {
168 let from = edge.source();
169 let to = edge.target();
170 let payload = edge.weight();
171 payload
172 .semantic_statements()
173 .iter()
174 .filter_map(|statement| {
175 statement
176 .recognized_sub_kind
177 .map(|sub_kind| SemanticEdgeView {
178 from,
179 to,
180 sub_kind,
181 label: statement.label.clone(),
182 })
183 })
184 .collect::<Vec<_>>()
185 .into_iter()
186 })
187 }
188
189 pub fn arrangement_edges(&self) -> impl Iterator<Item = ArrangementEdgeView> + '_ {
190 self.inner.inner().edge_references().flat_map(|e| {
191 let from = e.source();
192 let to = e.target();
193 e.weight()
194 .arrangement_data()
195 .map(|data| {
196 data.sub_kinds
197 .iter()
198 .copied()
199 .map(move |sub_kind| ArrangementEdgeView { from, to, sub_kind })
200 })
201 .into_iter()
202 .flatten()
203 })
204 }
205
206 pub fn containment_edges(&self) -> impl Iterator<Item = ContainmentEdgeView> + '_ {
207 self.inner.inner().edge_references().flat_map(|e| {
208 let from = e.source();
209 let to = e.target();
210 e.weight()
211 .containment_data()
212 .map(|data| {
213 data.sub_kinds
214 .iter()
215 .copied()
216 .map(move |sub_kind| ContainmentEdgeView { from, to, sub_kind })
217 })
218 .into_iter()
219 .flatten()
220 })
221 }
222
223 pub fn derive_containment_for(&mut self, key: NodeKey) {
243 let Some(node) = self.get_node(key) else {
244 return;
245 };
246 let Ok(parsed) = url::Url::parse(node.url()) else {
247 return;
248 };
249 let Some(parent_url) = containment_parent_url(&parsed) else {
250 return;
251 };
252 let Some((parent_key, _)) = self.get_node_by_url(&parent_url) else {
253 return;
254 };
255 if parent_key == key {
256 return;
257 }
258 let _ = self.assert_relation(
260 key,
261 parent_key,
262 EdgeAssertion::Containment {
263 sub_kind: ContainmentSubKind::UrlPath,
264 },
265 );
266 }
267
268 pub(crate) fn rebuild_derived_containment_relations(&mut self) {
269 let edge_ids: Vec<EdgeKey> = self.inner.inner().edge_indices().collect();
270 let mut empty_edges = Vec::new();
271 let mut changed = false;
275 for edge_id in edge_ids {
276 if let Some(payload) = self.inner.edge_mut(edge_id) {
277 let mut removed_any = false;
278 removed_any |= payload
279 .retract_relation(RelationSelector::Containment(ContainmentSubKind::UrlPath));
280 removed_any |= payload
281 .retract_relation(RelationSelector::Containment(ContainmentSubKind::Domain));
282 if removed_any {
283 changed = true;
284 }
285 if removed_any && payload.is_empty() {
286 empty_edges.push(edge_id);
287 }
288 }
289 }
290 for edge_id in empty_edges {
291 let _ = self.inner.disconnect(edge_id);
292 }
293 if changed {
294 self.bump_revision();
295 }
296
297 let mut domain_anchor: HashMap<String, (NodeKey, usize, Uuid)> = HashMap::new();
298 for (key, node) in self.nodes() {
299 let Ok(parsed) = url::Url::parse(node.url()) else {
300 continue;
301 };
302 let depth = parsed.path_segments().map_or(0, |segments| {
303 segments.filter(|segment| !segment.is_empty()).count()
304 });
305
306 let Some(host) = parsed.host_str() else {
307 continue;
308 };
309 let host = host.to_ascii_lowercase();
310 let candidate = (key, depth, node.id);
311 domain_anchor
312 .entry(host)
313 .and_modify(|current| {
314 if candidate.1 < current.1
315 || (candidate.1 == current.1 && candidate.2 < current.2)
316 {
317 *current = candidate;
318 }
319 })
320 .or_insert(candidate);
321 }
322
323 let mut url_parent_edges = Vec::new();
324 let mut domain_edges = Vec::new();
325 for (key, node) in self.nodes() {
326 let Ok(parsed) = url::Url::parse(node.url()) else {
327 continue;
328 };
329
330 if let Some(parent_url) = containment_parent_url(&parsed)
331 && let Some((parent_key, _)) = self.get_node_by_url(&parent_url)
332 && parent_key != key
333 {
334 url_parent_edges.push((key, parent_key));
335 }
336
337 if let Some(host) = parsed.host_str() {
338 let host = host.to_ascii_lowercase();
339 if let Some((anchor_key, _, _)) = domain_anchor.get(&host)
340 && *anchor_key != key
341 {
342 domain_edges.push((key, *anchor_key));
343 }
344 }
345 }
346
347 for (from, to) in url_parent_edges {
348 let _ = self.assert_relation(
349 from,
350 to,
351 EdgeAssertion::Containment {
352 sub_kind: ContainmentSubKind::UrlPath,
353 },
354 );
355 }
356 for (from, to) in domain_edges {
357 let _ = self.assert_relation(
358 from,
359 to,
360 EdgeAssertion::Containment {
361 sub_kind: ContainmentSubKind::Domain,
362 },
363 );
364 }
365 }
366
367 pub fn out_neighbors(&self, key: NodeKey) -> impl Iterator<Item = NodeKey> + '_ {
369 self.inner
370 .inner()
371 .neighbors_directed(key, Direction::Outgoing)
372 }
373
374 pub fn in_neighbors(&self, key: NodeKey) -> impl Iterator<Item = NodeKey> + '_ {
376 self.inner
377 .inner()
378 .neighbors_directed(key, Direction::Incoming)
379 }
380
381 pub fn neighbors_undirected(&self, key: NodeKey) -> impl Iterator<Item = NodeKey> + '_ {
383 self.inner.inner().neighbors_undirected(key)
384 }
385
386 pub fn neighbors_undirected_sorted(&self, key: NodeKey) -> Vec<NodeKey> {
388 let mut neighbors: Vec<NodeKey> = self
389 .neighbors_undirected(key)
390 .filter(|neighbor| *neighbor != key && self.get_node(*neighbor).is_some())
391 .collect::<HashSet<_>>()
392 .into_iter()
393 .collect();
394 neighbors.sort_by_key(|neighbor| neighbor.index());
395 neighbors
396 }
397
398 pub fn connected_frame_import_nodes(&self, seeds: &[NodeKey]) -> Vec<NodeKey> {
400 let mut out = HashSet::new();
401 for seed in seeds {
402 if self.get_node(*seed).is_none() {
403 continue;
404 }
405 out.insert(*seed);
406 out.extend(self.neighbors_undirected(*seed));
407 }
408 let mut nodes: Vec<NodeKey> = out
409 .into_iter()
410 .filter(|key| self.get_node(*key).is_some())
411 .collect();
412 nodes.sort_by_key(|key| key.index());
413 nodes
414 }
415
416 pub fn connected_candidates_with_depth(
420 &self,
421 source: NodeKey,
422 max_depth: u8,
423 ) -> Vec<(NodeKey, u8)> {
424 if self.get_node(source).is_none() || max_depth == 0 {
425 return Vec::new();
426 }
427
428 let mut out = Vec::new();
429 let mut visited = HashSet::from([source]);
430
431 let depth1 = self.neighbors_undirected_sorted(source);
432 for neighbor in depth1 {
433 if visited.insert(neighbor) {
434 out.push((neighbor, 1));
435 }
436 }
437
438 if max_depth < 2 {
439 return out;
440 }
441
442 let depth1_nodes: Vec<NodeKey> = out
443 .iter()
444 .filter_map(|(node, depth)| (*depth == 1).then_some(*node))
445 .collect();
446 for depth1_node in depth1_nodes {
447 for neighbor in self.neighbors_undirected_sorted(depth1_node) {
448 if visited.insert(neighbor) {
449 out.push((neighbor, 2));
450 }
451 }
452 }
453
454 out
455 }
456
457 pub fn hop_distances_from(&self, source: NodeKey) -> HashMap<NodeKey, usize> {
459 if self.get_node(source).is_none() {
460 return HashMap::new();
461 }
462 dijkstra(&UndirectedAdaptor(self.inner.inner()), source, None, |_| {
463 1_usize
464 })
465 .into_iter()
466 .collect()
467 }
468
469 pub fn orphan_node_keys(&self) -> Vec<NodeKey> {
471 let inner = self.inner.inner();
472 inner
473 .node_indices()
474 .filter(|&key| {
475 inner
476 .edges_directed(key, Direction::Outgoing)
477 .next()
478 .is_none()
479 && inner
480 .edges_directed(key, Direction::Incoming)
481 .next()
482 .is_none()
483 })
484 .collect()
485 }
486
487 pub fn shortest_path(&self, from: NodeKey, to: NodeKey) -> Option<Vec<NodeKey>> {
489 if self.get_node(from).is_none() || self.get_node(to).is_none() {
490 return None;
491 }
492 astar(
493 &UndirectedAdaptor(self.inner.inner()),
494 from,
495 |node| node == to,
496 |_| 1_usize,
497 |_| 0_usize,
498 )
499 .map(|(_, path)| path)
500 }
501
502 pub fn is_reachable(&self, from: NodeKey, to: NodeKey) -> bool {
504 if self.get_node(from).is_none() || self.get_node(to).is_none() {
505 return false;
506 }
507 has_path_connecting(&UndirectedAdaptor(self.inner.inner()), from, to, None)
508 }
509
510 pub fn weakly_connected_components(&self) -> Vec<Vec<NodeKey>> {
512 let mut visited = HashSet::new();
513 let mut components = Vec::new();
514 for start in self.inner.inner().node_indices() {
515 if !visited.insert(start) {
516 continue;
517 }
518 let mut component = Vec::new();
519 let mut stack = vec![start];
520 while let Some(current) = stack.pop() {
521 component.push(current);
522 for neighbor in self.neighbors_undirected(current) {
523 if visited.insert(neighbor) {
524 stack.push(neighbor);
525 }
526 }
527 }
528 components.push(component);
529 }
530 components
531 }
532
533 pub fn component_members(
540 &self,
541 seed: uuid::Uuid,
542 selectors: &[super::RelationSelector],
543 ) -> Vec<uuid::Uuid> {
544 self.bfs_members(seed, None, selectors)
545 }
546
547 pub fn ego_members(
552 &self,
553 seed: uuid::Uuid,
554 radius: u8,
555 selectors: &[super::RelationSelector],
556 ) -> Vec<uuid::Uuid> {
557 self.bfs_members(seed, Some(radius), selectors)
558 }
559
560 fn bfs_members(
565 &self,
566 seed: uuid::Uuid,
567 max_depth: Option<u8>,
568 selectors: &[super::RelationSelector],
569 ) -> Vec<uuid::Uuid> {
570 let Some((start, _)) = self.get_node_by_id(seed) else {
571 return Vec::new();
572 };
573 let mut seen = HashSet::new();
574 let mut order = Vec::new();
575 let mut queue = std::collections::VecDeque::new();
576 seen.insert(start);
577 queue.push_back((start, 0u8));
578 while let Some((key, depth)) = queue.pop_front() {
579 if let Some(node) = self.get_node(key) {
580 order.push(node.id);
581 }
582 if max_depth.is_some_and(|m| depth >= m) {
583 continue;
584 }
585 for neighbor in self.neighbors_undirected_sorted(key) {
586 if !selectors.is_empty() && !self.edge_matches_selectors(key, neighbor, selectors) {
590 continue;
591 }
592 if seen.insert(neighbor) {
593 queue.push_back((neighbor, depth + 1));
594 }
595 }
596 }
597 order
598 }
599
600 fn edge_matches_selectors(
603 &self,
604 a: NodeKey,
605 b: NodeKey,
606 selectors: &[super::RelationSelector],
607 ) -> bool {
608 self.find_edge_key(a, b)
609 .or_else(|| self.find_edge_key(b, a))
610 .and_then(|k| self.inner.edge(k))
611 .is_some_and(|payload| selectors.iter().any(|&s| payload.has_relation(s)))
612 }
613
614 pub fn strongly_connected_components(&self) -> Vec<Vec<NodeKey>> {
616 kosaraju_scc(self.inner.inner())
617 }
618
619 pub fn has_edge_between(&self, from: NodeKey, to: NodeKey) -> bool {
621 self.inner.inner().find_edge(from, to).is_some()
622 }
623
624 pub fn node_count(&self) -> usize {
626 self.inner.node_count()
627 }
628
629 pub fn edge_count(&self) -> usize {
631 self.inner.edge_count()
632 }
633}
634
635#[cfg(test)]
636mod derivation_tests {
637 use super::*;
638 use crate::graph::SemanticSubKind;
639 use euclid::default::Point2D;
640
641 fn chain_plus_isolate() -> (Graph, [uuid::Uuid; 4]) {
643 let mut g = Graph::new();
644 let a = g.add_node("https://a".to_string(), Point2D::new(0.0, 0.0));
645 let b = g.add_node("https://b".to_string(), Point2D::new(1.0, 0.0));
646 let c = g.add_node("https://c".to_string(), Point2D::new(2.0, 0.0));
647 let d = g.add_node("https://d".to_string(), Point2D::new(9.0, 9.0));
648 let sem = || EdgeAssertion::Semantic {
649 sub_kind: SemanticSubKind::Hyperlink,
650 label: None,
651 decay_progress: None,
652 };
653 g.assert_relation(a, b, sem());
654 g.assert_relation(b, c, sem());
655 let ids = [
656 g.get_node(a).unwrap().id,
657 g.get_node(b).unwrap().id,
658 g.get_node(c).unwrap().id,
659 g.get_node(d).unwrap().id,
660 ];
661 (g, ids)
662 }
663
664 #[test]
665 fn component_members_is_the_whole_connected_component() {
666 let (g, [a, _b, _c, d]) = chain_plus_isolate();
667 assert_eq!(g.component_members(a, &[]).len(), 3, "A reaches B and C");
668 assert_eq!(g.component_members(d, &[]).len(), 1, "D is isolated");
669 assert!(
670 g.component_members(uuid::Uuid::nil(), &[]).is_empty(),
671 "unknown seed: empty"
672 );
673 }
674
675 #[test]
676 fn ego_members_is_radius_bounded() {
677 let (g, [a, _b, _c, _d]) = chain_plus_isolate();
678 assert_eq!(
679 g.ego_members(a, 0, &[]).len(),
680 1,
681 "radius 0 is just the seed"
682 );
683 assert_eq!(
684 g.ego_members(a, 1, &[]).len(),
685 2,
686 "radius 1 reaches B, not C"
687 );
688 assert_eq!(g.ego_members(a, 2, &[]).len(), 3, "radius 2 reaches C");
689 }
690
691 #[test]
692 fn the_selector_projection_changes_the_derived_shape() {
693 use crate::graph::{ContainmentSubKind, EdgeFamily, RelationSelector};
694 let mut g = Graph::new();
696 let a = g.add_node("https://a".to_string(), Point2D::new(0.0, 0.0));
697 let b = g.add_node("https://b".to_string(), Point2D::new(1.0, 0.0));
698 let c = g.add_node("https://c".to_string(), Point2D::new(2.0, 0.0));
699 g.assert_relation(
700 a,
701 b,
702 EdgeAssertion::Semantic {
703 sub_kind: SemanticSubKind::Hyperlink,
704 label: None,
705 decay_progress: None,
706 },
707 );
708 g.assert_relation(
709 b,
710 c,
711 EdgeAssertion::Containment {
712 sub_kind: ContainmentSubKind::CollectionMember,
713 },
714 );
715 let a_id = g.get_node(a).unwrap().id;
716
717 let semantic = [RelationSelector::Family(EdgeFamily::Semantic)];
718 let containment = [RelationSelector::Family(EdgeFamily::Containment)];
719 assert_eq!(
721 g.component_members(a_id, &[]).len(),
722 3,
723 "all families: A, B, C"
724 );
725 assert_eq!(
726 g.component_members(a_id, &semantic).len(),
727 2,
728 "Semantic projection: A, B (B→C is Containment, not followed)"
729 );
730 assert_eq!(
731 g.component_members(a_id, &containment).len(),
732 1,
733 "Containment projection: just A (no Containment edge from A)"
734 );
735 }
736}