drft/analyses/
connected_components.rs

1use super::{Analysis, AnalysisContext};
2use std::collections::{HashMap, HashSet, VecDeque};
3
4#[derive(Debug, Clone, serde::Serialize)]
5pub struct Component {
6    pub id: usize,
7    pub members: Vec<String>,
8}
9
10#[derive(Debug, Clone, serde::Serialize)]
11pub struct ConnectedComponentsResult {
12    pub component_count: usize,
13    pub components: Vec<Component>,
14}
15
16pub struct ConnectedComponents;
17
18impl Analysis for ConnectedComponents {
19    type Output = ConnectedComponentsResult;
20
21    fn name(&self) -> &str {
22        "connected-components"
23    }
24
25    fn run(&self, ctx: &AnalysisContext) -> ConnectedComponentsResult {
26        let graph = ctx.graph;
27        // Build undirected adjacency among real nodes
28        let real_nodes: Vec<&str> = graph
29            .nodes
30            .keys()
31            .filter(|p| graph.is_file_node(p))
32            .map(|s| s.as_str())
33            .collect();
34
35        let mut adj: HashMap<&str, HashSet<&str>> = HashMap::new();
36        for node in &real_nodes {
37            adj.entry(node).or_default();
38        }
39
40        for edge in &graph.edges {
41            if graph.is_file_node(&edge.source) && graph.is_file_node(&edge.target) {
42                adj.entry(edge.source.as_str())
43                    .or_default()
44                    .insert(edge.target.as_str());
45                adj.entry(edge.target.as_str())
46                    .or_default()
47                    .insert(edge.source.as_str());
48            }
49        }
50
51        // BFS to find components
52        let mut visited: HashSet<&str> = HashSet::new();
53        let mut components = Vec::new();
54
55        // Sort real_nodes for deterministic iteration order
56        let mut sorted_nodes = real_nodes;
57        sorted_nodes.sort();
58
59        for &node in &sorted_nodes {
60            if visited.contains(node) {
61                continue;
62            }
63
64            let mut members = Vec::new();
65            let mut queue = VecDeque::new();
66            queue.push_back(node);
67            visited.insert(node);
68
69            while let Some(current) = queue.pop_front() {
70                members.push(current.to_string());
71                if let Some(neighbors) = adj.get(current) {
72                    let mut sorted_neighbors: Vec<&str> = neighbors.iter().copied().collect();
73                    sorted_neighbors.sort();
74                    for neighbor in sorted_neighbors {
75                        if visited.insert(neighbor) {
76                            queue.push_back(neighbor);
77                        }
78                    }
79                }
80            }
81
82            members.sort();
83            components.push(members);
84        }
85
86        // Sort components by size descending, then by first member
87        components.sort_by(|a, b| b.len().cmp(&a.len()).then_with(|| a[0].cmp(&b[0])));
88
89        let component_count = components.len();
90        let components = components
91            .into_iter()
92            .enumerate()
93            .map(|(i, members)| Component { id: i + 1, members })
94            .collect();
95
96        ConnectedComponentsResult {
97            component_count,
98            components,
99        }
100    }
101}
102
103#[cfg(test)]
104mod tests {
105    use super::*;
106    use crate::analyses::AnalysisContext;
107    use crate::config::Config;
108    use crate::graph::Graph;
109    use crate::graph::test_helpers::{make_edge, make_node};
110    use crate::graph::{Node, NodeType};
111    use std::path::Path;
112
113    fn make_ctx<'a>(graph: &'a Graph, config: &'a Config) -> AnalysisContext<'a> {
114        AnalysisContext {
115            graph,
116            root: Path::new("."),
117            config,
118            lockfile: None,
119        }
120    }
121
122    #[test]
123    fn single_component() {
124        let mut graph = Graph::new();
125        graph.add_node(make_node("a.md"));
126        graph.add_node(make_node("b.md"));
127        graph.add_node(make_node("c.md"));
128        graph.add_edge(make_edge("a.md", "b.md"));
129        graph.add_edge(make_edge("b.md", "c.md"));
130
131        let config = Config::defaults();
132        let result = ConnectedComponents.run(&make_ctx(&graph, &config));
133        assert_eq!(result.component_count, 1);
134        assert_eq!(result.components[0].members.len(), 3);
135    }
136
137    #[test]
138    fn two_components() {
139        let mut graph = Graph::new();
140        graph.add_node(make_node("a.md"));
141        graph.add_node(make_node("b.md"));
142        graph.add_node(make_node("c.md"));
143        graph.add_node(make_node("d.md"));
144        graph.add_edge(make_edge("a.md", "b.md"));
145        graph.add_edge(make_edge("c.md", "d.md"));
146
147        let config = Config::defaults();
148        let result = ConnectedComponents.run(&make_ctx(&graph, &config));
149        assert_eq!(result.component_count, 2);
150        assert_eq!(result.components[0].members.len(), 2);
151        assert_eq!(result.components[1].members.len(), 2);
152    }
153
154    #[test]
155    fn isolated_node() {
156        let mut graph = Graph::new();
157        graph.add_node(make_node("a.md"));
158        graph.add_node(make_node("b.md"));
159        graph.add_node(make_node("c.md"));
160        graph.add_edge(make_edge("a.md", "b.md"));
161
162        let config = Config::defaults();
163        let result = ConnectedComponents.run(&make_ctx(&graph, &config));
164        assert_eq!(result.component_count, 2);
165        assert_eq!(result.components[0].members, vec!["a.md", "b.md"]);
166        assert_eq!(result.components[1].members, vec!["c.md"]);
167    }
168
169    #[test]
170    fn excludes_external_nodes() {
171        let mut graph = Graph::new();
172        graph.add_node(make_node("a.md"));
173        graph.add_node(Node {
174            path: "https://example.com".into(),
175            node_type: NodeType::External,
176            hash: None,
177            graph: None,
178        });
179        graph.add_edge(make_edge("a.md", "https://example.com"));
180
181        let config = Config::defaults();
182        let result = ConnectedComponents.run(&make_ctx(&graph, &config));
183        assert_eq!(result.component_count, 1);
184        assert_eq!(result.components[0].members, vec!["a.md"]);
185    }
186
187    #[test]
188    fn empty_graph() {
189        let graph = Graph::new();
190        let config = Config::defaults();
191        let result = ConnectedComponents.run(&make_ctx(&graph, &config));
192        assert_eq!(result.component_count, 0);
193        assert!(result.components.is_empty());
194    }
195
196    #[test]
197    fn undirected_connectivity() {
198        let mut graph = Graph::new();
199        graph.add_node(make_node("a.md"));
200        graph.add_node(make_node("b.md"));
201        graph.add_node(make_node("c.md"));
202        graph.add_edge(make_edge("a.md", "b.md"));
203        graph.add_edge(make_edge("c.md", "b.md"));
204
205        let config = Config::defaults();
206        let result = ConnectedComponents.run(&make_ctx(&graph, &config));
207        assert_eq!(result.component_count, 1);
208        assert_eq!(result.components[0].members.len(), 3);
209    }
210
211    #[test]
212    fn sorted_by_size_descending() {
213        let mut graph = Graph::new();
214        graph.add_node(make_node("a.md"));
215        graph.add_node(make_node("b.md"));
216        graph.add_node(make_node("c.md"));
217        graph.add_node(make_node("d.md"));
218        graph.add_node(make_node("e.md"));
219        graph.add_edge(make_edge("a.md", "b.md"));
220        graph.add_edge(make_edge("a.md", "c.md"));
221
222        let config = Config::defaults();
223        let result = ConnectedComponents.run(&make_ctx(&graph, &config));
224        assert_eq!(result.component_count, 3);
225        assert_eq!(result.components[0].members.len(), 3);
226        assert_eq!(result.components[1].members.len(), 1);
227        assert_eq!(result.components[2].members.len(), 1);
228    }
229}
drft/analyses/connected_components.rs

drft/analyses/
connected_components.rs
