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

drft/analyses/
transitive_reduction.rs
