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

drft/analyses/
transitive_reduction.rs
