drft/analyses/
transitive_reduction.rs

1use super::{Analysis, AnalysisContext};
2use crate::graph::Graph;
3use std::collections::{HashSet, VecDeque};
4
5#[derive(Debug, Clone, serde::Serialize)]
6pub struct RedundantEdge {
7    pub source: String,
8    pub target: String,
9    pub via: String,
10}
11
12#[derive(Debug, Clone, serde::Serialize)]
13pub struct TransitiveReductionResult {
14    pub redundant_edges: Vec<RedundantEdge>,
15}
16
17pub struct TransitiveReduction;
18
19impl Analysis for TransitiveReduction {
20    type Output = TransitiveReductionResult;
21
22    fn name(&self) -> &str {
23        "transitive-reduction"
24    }
25
26    fn run(&self, ctx: &AnalysisContext) -> TransitiveReductionResult {
27        let graph = ctx.graph;
28        let node_set: HashSet<&str> = graph.included_nodes().map(|(s, _)| s.as_str()).collect();
29        let mut redundant_edges = Vec::new();
30
31        for edge in &graph.edges {
32            // Skip edges to/from nodes not in the graph
33            if !node_set.contains(edge.source.as_str()) || !node_set.contains(edge.target.as_str())
34            {
35                continue;
36            }
37
38            // Skip self-loops
39            if edge.source == edge.target {
40                continue;
41            }
42
43            // BFS from source, skipping the direct edge to target.
44            // If target is still reachable, the edge is redundant.
45            if let Some(via) =
46                reachable_without_direct(graph, &edge.source, &edge.target, &node_set)
47            {
48                redundant_edges.push(RedundantEdge {
49                    source: edge.source.clone(),
50                    target: edge.target.clone(),
51                    via,
52                });
53            }
54        }
55
56        redundant_edges.sort_by(|a, b| {
57            a.source
58                .cmp(&b.source)
59                .then_with(|| a.target.cmp(&b.target))
60        });
61
62        TransitiveReductionResult { redundant_edges }
63    }
64}
65
66/// BFS from `source` following forward edges, but skip any direct edge to `target`.
67/// If `target` is reached, return the first intermediate node on the path (the `via`).
68fn reachable_without_direct(
69    graph: &Graph,
70    source: &str,
71    target: &str,
72    node_set: &HashSet<&str>,
73) -> Option<String> {
74    let mut visited = HashSet::new();
75    // Queue entries: (current_node, first_intermediate_on_this_path)
76    let mut queue: VecDeque<(&str, Option<&str>)> = VecDeque::new();
77
78    visited.insert(source);
79    queue.push_back((source, None));
80
81    while let Some((current, first_hop)) = queue.pop_front() {
82        let Some(edge_indices) = graph.forward.get(current) else {
83            continue;
84        };
85
86        for &idx in edge_indices {
87            let neighbor = graph.edges[idx].target.as_str();
88
89            // Skip the direct source→target edge
90            if current == source && neighbor == target {
91                continue;
92            }
93
94            // Only traverse within known nodes
95            if !node_set.contains(neighbor) {
96                continue;
97            }
98
99            if !visited.insert(neighbor) {
100                continue;
101            }
102
103            // Track the first intermediate node on this path
104            let via = first_hop.unwrap_or(neighbor);
105
106            if neighbor == target {
107                return Some(via.to_string());
108            }
109
110            queue.push_back((neighbor, Some(via)));
111        }
112    }
113
114    None
115}
116
117#[cfg(test)]
118mod tests {
119    use super::*;
120    use crate::analyses::AnalysisContext;
121    use crate::config::Config;
122    use crate::graph::test_helpers::{make_edge, make_node};
123    use std::path::Path;
124
125    fn make_ctx<'a>(graph: &'a Graph, config: &'a Config) -> AnalysisContext<'a> {
126        AnalysisContext {
127            graph,
128            root: Path::new("."),
129            config,
130            lockfile: None,
131        }
132    }
133
134    #[test]
135    fn diamond_redundancy() {
136        let mut graph = Graph::new();
137        graph.add_node(make_node("a.md"));
138        graph.add_node(make_node("b.md"));
139        graph.add_node(make_node("c.md"));
140        graph.add_edge(make_edge("a.md", "b.md"));
141        graph.add_edge(make_edge("b.md", "c.md"));
142        graph.add_edge(make_edge("a.md", "c.md"));
143
144        let config = Config::defaults();
145        let result = TransitiveReduction.run(&make_ctx(&graph, &config));
146
147        assert_eq!(result.redundant_edges.len(), 1);
148        assert_eq!(result.redundant_edges[0].source, "a.md");
149        assert_eq!(result.redundant_edges[0].target, "c.md");
150        assert_eq!(result.redundant_edges[0].via, "b.md");
151    }
152
153    #[test]
154    fn no_redundancy() {
155        let mut graph = Graph::new();
156        graph.add_node(make_node("a.md"));
157        graph.add_node(make_node("b.md"));
158        graph.add_node(make_node("c.md"));
159        graph.add_edge(make_edge("a.md", "b.md"));
160        graph.add_edge(make_edge("b.md", "c.md"));
161
162        let config = Config::defaults();
163        let result = TransitiveReduction.run(&make_ctx(&graph, &config));
164        assert!(result.redundant_edges.is_empty());
165    }
166
167    #[test]
168    fn multiple_redundancies() {
169        let mut graph = Graph::new();
170        graph.add_node(make_node("a.md"));
171        graph.add_node(make_node("b.md"));
172        graph.add_node(make_node("c.md"));
173        graph.add_node(make_node("d.md"));
174        graph.add_edge(make_edge("a.md", "b.md"));
175        graph.add_edge(make_edge("b.md", "c.md"));
176        graph.add_edge(make_edge("b.md", "d.md"));
177        graph.add_edge(make_edge("a.md", "c.md"));
178        graph.add_edge(make_edge("a.md", "d.md"));
179
180        let config = Config::defaults();
181        let result = TransitiveReduction.run(&make_ctx(&graph, &config));
182
183        assert_eq!(result.redundant_edges.len(), 2);
184        let targets: Vec<&str> = result
185            .redundant_edges
186            .iter()
187            .map(|r| r.target.as_str())
188            .collect();
189        assert!(targets.contains(&"c.md"));
190        assert!(targets.contains(&"d.md"));
191    }
192
193    #[test]
194    fn longer_chain() {
195        let mut graph = Graph::new();
196        graph.add_node(make_node("a.md"));
197        graph.add_node(make_node("b.md"));
198        graph.add_node(make_node("c.md"));
199        graph.add_node(make_node("d.md"));
200        graph.add_edge(make_edge("a.md", "b.md"));
201        graph.add_edge(make_edge("b.md", "c.md"));
202        graph.add_edge(make_edge("c.md", "d.md"));
203        graph.add_edge(make_edge("a.md", "d.md"));
204
205        let config = Config::defaults();
206        let result = TransitiveReduction.run(&make_ctx(&graph, &config));
207
208        assert_eq!(result.redundant_edges.len(), 1);
209        assert_eq!(result.redundant_edges[0].source, "a.md");
210        assert_eq!(result.redundant_edges[0].target, "d.md");
211        assert_eq!(result.redundant_edges[0].via, "b.md");
212    }
213
214    #[test]
215    fn self_loop_not_flagged() {
216        let mut graph = Graph::new();
217        graph.add_node(make_node("a.md"));
218        graph.add_edge(make_edge("a.md", "a.md"));
219
220        let config = Config::defaults();
221        let result = TransitiveReduction.run(&make_ctx(&graph, &config));
222        assert!(result.redundant_edges.is_empty());
223    }
224
225    #[test]
226    fn disconnected_components() {
227        let mut graph = Graph::new();
228        graph.add_node(make_node("a.md"));
229        graph.add_node(make_node("b.md"));
230        graph.add_node(make_node("c.md"));
231        graph.add_node(make_node("d.md"));
232        graph.add_edge(make_edge("a.md", "b.md"));
233        graph.add_edge(make_edge("c.md", "d.md"));
234
235        let config = Config::defaults();
236        let result = TransitiveReduction.run(&make_ctx(&graph, &config));
237        assert!(result.redundant_edges.is_empty());
238    }
239
240    #[test]
241    fn edge_to_missing_node_skipped() {
242        let mut graph = Graph::new();
243        graph.add_node(make_node("a.md"));
244        graph.add_node(make_node("b.md"));
245        graph.add_edge(make_edge("a.md", "b.md"));
246        graph.add_edge(make_edge("a.md", "missing.md"));
247
248        let config = Config::defaults();
249        let result = TransitiveReduction.run(&make_ctx(&graph, &config));
250        assert!(result.redundant_edges.is_empty());
251    }
252}
drft/analyses/transitive_reduction.rs

drft/analyses/
transitive_reduction.rs
