gid_core/
query.rs

1use std::collections::{HashMap, HashSet, VecDeque};
2use crate::graph::{Graph, Node};
3
4/// Query engine for graph traversal and analysis.
5pub struct QueryEngine<'a> {
6    graph: &'a Graph,
7}
8
9impl<'a> QueryEngine<'a> {
10    pub fn new(graph: &'a Graph) -> Self {
11        Self { graph }
12    }
13
14    /// Impact analysis: what nodes are affected if `node_id` changes?
15    /// Follows reverse dependency edges (who depends on this node?).
16    pub fn impact(&self, node_id: &str) -> Vec<&'a Node> {
17        let mut visited = HashSet::new();
18        let mut queue = VecDeque::new();
19        queue.push_back(node_id.to_string());
20        visited.insert(node_id.to_string());
21
22        while let Some(current) = queue.pop_front() {
23            // Find nodes that depend_on current (edges where to == current)
24            for edge in &self.graph.edges {
25                if edge.to == current && edge.relation == "depends_on" {
26                    if visited.insert(edge.from.clone()) {
27                        queue.push_back(edge.from.clone());
28                    }
29                }
30            }
31        }
32
33        visited.remove(node_id);
34        self.graph.nodes.iter()
35            .filter(|n| visited.contains(&n.id))
36            .collect()
37    }
38
39    /// Dependencies: what does `node_id` depend on? (transitive)
40    pub fn deps(&self, node_id: &str, transitive: bool) -> Vec<&'a Node> {
41        if !transitive {
42            // Direct deps only
43            let dep_ids: HashSet<&str> = self.graph.edges.iter()
44                .filter(|e| e.from == node_id && e.relation == "depends_on")
45                .map(|e| e.to.as_str())
46                .collect();
47            return self.graph.nodes.iter()
48                .filter(|n| dep_ids.contains(n.id.as_str()))
49                .collect();
50        }
51
52        let mut visited = HashSet::new();
53        let mut queue = VecDeque::new();
54        queue.push_back(node_id.to_string());
55        visited.insert(node_id.to_string());
56
57        while let Some(current) = queue.pop_front() {
58            for edge in &self.graph.edges {
59                if edge.from == current && edge.relation == "depends_on" {
60                    if visited.insert(edge.to.clone()) {
61                        queue.push_back(edge.to.clone());
62                    }
63                }
64            }
65        }
66
67        visited.remove(node_id);
68        self.graph.nodes.iter()
69            .filter(|n| visited.contains(&n.id))
70            .collect()
71    }
72
73    /// Find shortest path between two nodes (any edge direction).
74    pub fn path(&self, from: &str, to: &str) -> Option<Vec<String>> {
75        let mut visited = HashSet::new();
76        let mut queue = VecDeque::new();
77        let mut parent: HashMap<String, String> = HashMap::new();
78
79        queue.push_back(from.to_string());
80        visited.insert(from.to_string());
81
82        while let Some(current) = queue.pop_front() {
83            if current == to {
84                // Reconstruct path
85                let mut path = vec![to.to_string()];
86                let mut cur = to.to_string();
87                while let Some(p) = parent.get(&cur) {
88                    path.push(p.clone());
89                    cur = p.clone();
90                }
91                path.reverse();
92                return Some(path);
93            }
94
95            // Follow edges in both directions
96            for edge in &self.graph.edges {
97                let neighbor = if edge.from == current {
98                    &edge.to
99                } else if edge.to == current {
100                    &edge.from
101                } else {
102                    continue;
103                };
104                if visited.insert(neighbor.clone()) {
105                    parent.insert(neighbor.clone(), current.clone());
106                    queue.push_back(neighbor.clone());
107                }
108            }
109        }
110
111        None
112    }
113
114    /// Common cause: find shared dependencies of two nodes.
115    pub fn common_cause(&self, node_a: &str, node_b: &str) -> Vec<&'a Node> {
116        let deps_a: HashSet<String> = self.deps(node_a, true)
117            .iter().map(|n| n.id.clone()).collect();
118        let deps_b: HashSet<String> = self.deps(node_b, true)
119            .iter().map(|n| n.id.clone()).collect();
120        let common: HashSet<&String> = deps_a.intersection(&deps_b).collect();
121
122        self.graph.nodes.iter()
123            .filter(|n| common.contains(&n.id))
124            .collect()
125    }
126
127    /// Topological sort (returns error if cycle detected).
128    pub fn topological_sort(&self) -> anyhow::Result<Vec<String>> {
129        let mut in_degree: HashMap<&str, usize> = HashMap::new();
130        for node in &self.graph.nodes {
131            in_degree.entry(&node.id).or_insert(0);
132        }
133        for edge in &self.graph.edges {
134            if edge.relation == "depends_on" {
135                *in_degree.entry(&edge.from).or_insert(0) += 1;
136            }
137        }
138
139        let mut queue: VecDeque<&str> = in_degree.iter()
140            .filter(|(_, &deg)| deg == 0)
141            .map(|(&id, _)| id)
142            .collect();
143
144        let mut sorted = Vec::new();
145        while let Some(node) = queue.pop_front() {
146            sorted.push(node.to_string());
147            for edge in &self.graph.edges {
148                if edge.to == node && edge.relation == "depends_on" {
149                    if let Some(deg) = in_degree.get_mut(edge.from.as_str()) {
150                        *deg -= 1;
151                        if *deg == 0 {
152                            queue.push_back(&edge.from);
153                        }
154                    }
155                }
156            }
157        }
158
159        if sorted.len() != self.graph.nodes.len() {
160            anyhow::bail!("Cycle detected in graph");
161        }
162
163        Ok(sorted)
164    }
165}
gid_core/query.rs

gid_core/
query.rs
