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.nodes.keys().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::{Edge, Node, NodeType};
123    use std::collections::HashMap;
124    use std::path::Path;
125
126    fn make_node(path: &str) -> Node {
127        Node {
128            path: path.into(),
129            node_type: NodeType::File,
130            hash: None,
131            graph: None,
132            metadata: HashMap::new(),
133        }
134    }
135
136    fn make_edge(source: &str, target: &str) -> Edge {
137        Edge {
138            source: source.into(),
139            target: target.into(),
140            link: None,
141            parser: "markdown".into(),
142        }
143    }
144
145    fn make_ctx<'a>(graph: &'a Graph, config: &'a Config) -> AnalysisContext<'a> {
146        AnalysisContext {
147            graph,
148            root: Path::new("."),
149            config,
150            lockfile: None,
151        }
152    }
153
154    #[test]
155    fn diamond_redundancy() {
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        graph.add_edge(make_edge("b.md", "c.md"));
162        graph.add_edge(make_edge("a.md", "c.md"));
163
164        let config = Config::defaults();
165        let result = TransitiveReduction.run(&make_ctx(&graph, &config));
166
167        assert_eq!(result.redundant_edges.len(), 1);
168        assert_eq!(result.redundant_edges[0].source, "a.md");
169        assert_eq!(result.redundant_edges[0].target, "c.md");
170        assert_eq!(result.redundant_edges[0].via, "b.md");
171    }
172
173    #[test]
174    fn no_redundancy() {
175        let mut graph = Graph::new();
176        graph.add_node(make_node("a.md"));
177        graph.add_node(make_node("b.md"));
178        graph.add_node(make_node("c.md"));
179        graph.add_edge(make_edge("a.md", "b.md"));
180        graph.add_edge(make_edge("b.md", "c.md"));
181
182        let config = Config::defaults();
183        let result = TransitiveReduction.run(&make_ctx(&graph, &config));
184        assert!(result.redundant_edges.is_empty());
185    }
186
187    #[test]
188    fn multiple_redundancies() {
189        let mut graph = Graph::new();
190        graph.add_node(make_node("a.md"));
191        graph.add_node(make_node("b.md"));
192        graph.add_node(make_node("c.md"));
193        graph.add_node(make_node("d.md"));
194        graph.add_edge(make_edge("a.md", "b.md"));
195        graph.add_edge(make_edge("b.md", "c.md"));
196        graph.add_edge(make_edge("b.md", "d.md"));
197        graph.add_edge(make_edge("a.md", "c.md"));
198        graph.add_edge(make_edge("a.md", "d.md"));
199
200        let config = Config::defaults();
201        let result = TransitiveReduction.run(&make_ctx(&graph, &config));
202
203        assert_eq!(result.redundant_edges.len(), 2);
204        let targets: Vec<&str> = result
205            .redundant_edges
206            .iter()
207            .map(|r| r.target.as_str())
208            .collect();
209        assert!(targets.contains(&"c.md"));
210        assert!(targets.contains(&"d.md"));
211    }
212
213    #[test]
214    fn longer_chain() {
215        let mut graph = Graph::new();
216        graph.add_node(make_node("a.md"));
217        graph.add_node(make_node("b.md"));
218        graph.add_node(make_node("c.md"));
219        graph.add_node(make_node("d.md"));
220        graph.add_edge(make_edge("a.md", "b.md"));
221        graph.add_edge(make_edge("b.md", "c.md"));
222        graph.add_edge(make_edge("c.md", "d.md"));
223        graph.add_edge(make_edge("a.md", "d.md"));
224
225        let config = Config::defaults();
226        let result = TransitiveReduction.run(&make_ctx(&graph, &config));
227
228        assert_eq!(result.redundant_edges.len(), 1);
229        assert_eq!(result.redundant_edges[0].source, "a.md");
230        assert_eq!(result.redundant_edges[0].target, "d.md");
231        assert_eq!(result.redundant_edges[0].via, "b.md");
232    }
233
234    #[test]
235    fn self_loop_not_flagged() {
236        let mut graph = Graph::new();
237        graph.add_node(make_node("a.md"));
238        graph.add_edge(make_edge("a.md", "a.md"));
239
240        let config = Config::defaults();
241        let result = TransitiveReduction.run(&make_ctx(&graph, &config));
242        assert!(result.redundant_edges.is_empty());
243    }
244
245    #[test]
246    fn disconnected_components() {
247        let mut graph = Graph::new();
248        graph.add_node(make_node("a.md"));
249        graph.add_node(make_node("b.md"));
250        graph.add_node(make_node("c.md"));
251        graph.add_node(make_node("d.md"));
252        graph.add_edge(make_edge("a.md", "b.md"));
253        graph.add_edge(make_edge("c.md", "d.md"));
254
255        let config = Config::defaults();
256        let result = TransitiveReduction.run(&make_ctx(&graph, &config));
257        assert!(result.redundant_edges.is_empty());
258    }
259
260    #[test]
261    fn edge_to_missing_node_skipped() {
262        let mut graph = Graph::new();
263        graph.add_node(make_node("a.md"));
264        graph.add_node(make_node("b.md"));
265        graph.add_edge(make_edge("a.md", "b.md"));
266        graph.add_edge(make_edge("a.md", "missing.md"));
267
268        let config = Config::defaults();
269        let result = TransitiveReduction.run(&make_ctx(&graph, &config));
270        assert!(result.redundant_edges.is_empty());
271    }
272}
drft/analyses/transitive_reduction.rs

drft/analyses/
transitive_reduction.rs
