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

drft/analyses/
transitive_reduction.rs
