drft/analyses/
degree.rs

1use super::{Analysis, AnalysisContext};
2
3#[derive(Debug, Clone, serde::Serialize)]
4pub struct NodeDegree {
5    pub node: String,
6    pub in_degree: usize,
7    pub out_degree: usize,
8}
9
10#[derive(Debug, Clone, serde::Serialize)]
11pub struct DegreeResult {
12    pub nodes: Vec<NodeDegree>,
13}
14
15pub struct Degree;
16
17impl Analysis for Degree {
18    type Output = DegreeResult;
19
20    fn name(&self) -> &str {
21        "degree"
22    }
23
24    fn run(&self, ctx: &AnalysisContext) -> DegreeResult {
25        let graph = ctx.graph;
26        let mut nodes: Vec<NodeDegree> = graph
27            .nodes
28            .keys()
29            .filter(|path| graph.is_file_node(path))
30            .map(|path| {
31                let in_degree = graph
32                    .reverse
33                    .get(path.as_str())
34                    .map(|indices| {
35                        indices
36                            .iter()
37                            .filter(|&&idx| graph.is_file_node(&graph.edges[idx].source))
38                            .count()
39                    })
40                    .unwrap_or(0);
41
42                let out_degree = graph
43                    .forward
44                    .get(path.as_str())
45                    .map(|indices| {
46                        indices
47                            .iter()
48                            .filter(|&&idx| graph.is_file_node(&graph.edges[idx].target))
49                            .count()
50                    })
51                    .unwrap_or(0);
52
53                NodeDegree {
54                    node: path.clone(),
55                    in_degree,
56                    out_degree,
57                }
58            })
59            .collect();
60
61        nodes.sort_by(|a, b| a.node.cmp(&b.node));
62
63        DegreeResult { nodes }
64    }
65}
66
67#[cfg(test)]
68mod tests {
69    use super::*;
70    use crate::analyses::AnalysisContext;
71    use crate::config::Config;
72    use crate::graph::test_helpers::{make_edge, make_node};
73    use crate::graph::{Graph, Node, NodeType};
74    use std::collections::HashMap;
75    use std::path::Path;
76
77    fn make_ctx<'a>(graph: &'a Graph, config: &'a Config) -> AnalysisContext<'a> {
78        AnalysisContext {
79            graph,
80            root: Path::new("."),
81            config,
82            lockfile: None,
83        }
84    }
85
86    #[test]
87    fn empty_graph() {
88        let graph = Graph::new();
89        let config = Config::defaults();
90        let result = Degree.run(&make_ctx(&graph, &config));
91        assert!(result.nodes.is_empty());
92    }
93
94    #[test]
95    fn single_node() {
96        let mut graph = Graph::new();
97        graph.add_node(make_node("a.md"));
98
99        let config = Config::defaults();
100        let result = Degree.run(&make_ctx(&graph, &config));
101        assert_eq!(result.nodes.len(), 1);
102        assert_eq!(result.nodes[0].node, "a.md");
103        assert_eq!(result.nodes[0].in_degree, 0);
104        assert_eq!(result.nodes[0].out_degree, 0);
105    }
106
107    #[test]
108    fn diamond_graph() {
109        let mut graph = Graph::new();
110        graph.add_node(make_node("a.md"));
111        graph.add_node(make_node("b.md"));
112        graph.add_node(make_node("c.md"));
113        graph.add_node(make_node("d.md"));
114        graph.add_edge(make_edge("a.md", "b.md"));
115        graph.add_edge(make_edge("a.md", "c.md"));
116        graph.add_edge(make_edge("b.md", "d.md"));
117        graph.add_edge(make_edge("c.md", "d.md"));
118
119        let config = Config::defaults();
120        let result = Degree.run(&make_ctx(&graph, &config));
121        assert_eq!(result.nodes.len(), 4);
122
123        let a = result.nodes.iter().find(|n| n.node == "a.md").unwrap();
124        assert_eq!(a.in_degree, 0);
125        assert_eq!(a.out_degree, 2);
126
127        let d = result.nodes.iter().find(|n| n.node == "d.md").unwrap();
128        assert_eq!(d.in_degree, 2);
129        assert_eq!(d.out_degree, 0);
130    }
131
132    #[test]
133    fn self_loop() {
134        let mut graph = Graph::new();
135        graph.add_node(make_node("a.md"));
136        graph.add_edge(make_edge("a.md", "a.md"));
137
138        let config = Config::defaults();
139        let result = Degree.run(&make_ctx(&graph, &config));
140        assert_eq!(result.nodes[0].in_degree, 1);
141        assert_eq!(result.nodes[0].out_degree, 1);
142    }
143
144    #[test]
145    fn excludes_synthetic_nodes() {
146        let mut graph = Graph::new();
147        graph.add_node(make_node("a.md"));
148        graph.add_node(Node {
149            path: "https://example.com".into(),
150            node_type: NodeType::External,
151            hash: None,
152            graph: None,
153            is_graph: false,
154            metadata: HashMap::new(),
155        });
156        graph.add_edge(make_edge("a.md", "https://example.com"));
157
158        let config = Config::defaults();
159        let result = Degree.run(&make_ctx(&graph, &config));
160        assert_eq!(result.nodes.len(), 1);
161        assert_eq!(result.nodes[0].node, "a.md");
162        assert_eq!(result.nodes[0].out_degree, 0);
163    }
164
165    #[test]
166    fn sorted_by_path() {
167        let mut graph = Graph::new();
168        graph.add_node(make_node("c.md"));
169        graph.add_node(make_node("a.md"));
170        graph.add_node(make_node("b.md"));
171
172        let config = Config::defaults();
173        let result = Degree.run(&make_ctx(&graph, &config));
174        let paths: Vec<&str> = result.nodes.iter().map(|n| n.node.as_str()).collect();
175        assert_eq!(paths, vec!["a.md", "b.md", "c.md"]);
176    }
177}
drft/analyses/degree.rs

drft/analyses/
degree.rs
