gossan_graph/
query.rs

1//! Query layer for graph traversal.
2
3use crate::store::GraphBackend;
4use crate::{schema::EdgeType, Edge, Node};
5use std::collections::{HashSet, VecDeque};
6
7/// Find all nodes of a given type.
8///
9/// # Errors
10///
11/// Returns an error if the backend fails.
12pub fn find_all<B: GraphBackend>(
13    backend: &B,
14    kind: crate::schema::NodeType,
15) -> Result<Vec<Node>, B::Error> {
16    backend.find_nodes_by_type(kind)
17}
18
19/// Find outgoing edges from a node, optionally filtered by edge type.
20///
21/// # Errors
22///
23/// Returns an error if the backend fails.
24pub fn neighbors<B: GraphBackend>(
25    backend: &B,
26    node_id: &str,
27    edge_type: Option<EdgeType>,
28) -> Result<Vec<Edge>, B::Error> {
29    backend.neighbors(node_id, edge_type)
30}
31
32/// Find a path from `start` to `goal` using BFS over edges.
33///
34/// Returns the list of node ids forming the path, or `None` if unreachable.
35///
36/// # Errors
37///
38/// Returns an error if the backend fails.
39pub fn path<B: GraphBackend>(
40    backend: &B,
41    start: &str,
42    goal: &str,
43) -> Result<Option<Vec<String>>, B::Error> {
44    let mut visited = HashSet::new();
45    let mut queue = VecDeque::new();
46    let mut parents: std::collections::HashMap<String, String> = std::collections::HashMap::new();
47
48    visited.insert(start.to_string());
49    queue.push_back(start.to_string());
50
51    while let Some(current) = queue.pop_front() {
52        if current == goal {
53            let mut path = vec![goal.to_string()];
54            let mut cursor = goal.to_string();
55            while let Some(parent) = parents.get(&cursor) {
56                path.push(parent.clone());
57                cursor = parent.clone();
58            }
59            path.reverse();
60            return Ok(Some(path));
61        }
62
63        for edge in backend.neighbors(&current, None)? {
64            if visited.insert(edge.target_id.clone()) {
65                parents.insert(edge.target_id.clone(), current.clone());
66                queue.push_back(edge.target_id.clone());
67            }
68        }
69    }
70
71    Ok(None)
72}
73
74#[cfg(test)]
75mod tests {
76    use super::*;
77    use crate::schema::NodeType;
78    use crate::store::sqlite::SqliteBackend;
79
80    #[test]
81    fn find_all_filters_by_type() {
82        let mut backend = SqliteBackend::open_in_memory().unwrap();
83        backend
84            .write_nodes(&[
85                Node::new("d1", NodeType::Domain, "example.com"),
86                Node::new("s1", NodeType::Subdomain, "sub.example.com"),
87            ])
88            .unwrap();
89
90        let domains = find_all(&backend, NodeType::Domain).unwrap();
91        assert_eq!(domains.len(), 1);
92        assert_eq!(domains[0].id, "d1");
93    }
94
95    #[test]
96    fn neighbors_returns_only_matching_edges() {
97        let mut backend = SqliteBackend::open_in_memory().unwrap();
98        backend
99            .write_edges(&[
100                Edge::new("a", "b", EdgeType::ResolvesTo),
101                Edge::new("a", "c", EdgeType::Hosts),
102                Edge::new("b", "d", EdgeType::ResolvesTo),
103            ])
104            .unwrap();
105
106        let all = neighbors(&backend, "a", None).unwrap();
107        assert_eq!(all.len(), 2);
108
109        let hosts_only = neighbors(&backend, "a", Some(EdgeType::Hosts)).unwrap();
110        assert_eq!(hosts_only.len(), 1);
111        assert_eq!(hosts_only[0].target_id, "c");
112    }
113
114    #[test]
115    fn path_finds_shortest_route() {
116        let mut backend = SqliteBackend::open_in_memory().unwrap();
117        backend
118            .write_edges(&[
119                Edge::new("a", "b", EdgeType::ResolvesTo),
120                Edge::new("b", "c", EdgeType::Hosts),
121                Edge::new("c", "d", EdgeType::Exposes),
122                // Longer route a -> e -> d
123                Edge::new("a", "e", EdgeType::ResolvesTo),
124                Edge::new("e", "d", EdgeType::Exposes),
125            ])
126            .unwrap();
127
128        let p = path(&backend, "a", "d").unwrap();
129        assert_eq!(
130            p,
131            Some(vec!["a".to_string(), "e".to_string(), "d".to_string()])
132        );
133    }
134
135    #[test]
136    fn path_none_when_disconnected() {
137        let mut backend = SqliteBackend::open_in_memory().unwrap();
138        backend
139            .write_edges(&[Edge::new("a", "b", EdgeType::ResolvesTo)])
140            .unwrap();
141
142        let p = path(&backend, "a", "z").unwrap();
143        assert_eq!(p, None);
144    }
145}
gossan_graph/query.rs

gossan_graph/
query.rs
