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::path::Path;
75
76    fn make_ctx<'a>(graph: &'a Graph, config: &'a Config) -> AnalysisContext<'a> {
77        AnalysisContext {
78            graph,
79            root: Path::new("."),
80            config,
81            lockfile: None,
82        }
83    }
84
85    #[test]
86    fn empty_graph() {
87        let graph = Graph::new();
88        let config = Config::defaults();
89        let result = Degree.run(&make_ctx(&graph, &config));
90        assert!(result.nodes.is_empty());
91    }
92
93    #[test]
94    fn single_node() {
95        let mut graph = Graph::new();
96        graph.add_node(make_node("a.md"));
97
98        let config = Config::defaults();
99        let result = Degree.run(&make_ctx(&graph, &config));
100        assert_eq!(result.nodes.len(), 1);
101        assert_eq!(result.nodes[0].node, "a.md");
102        assert_eq!(result.nodes[0].in_degree, 0);
103        assert_eq!(result.nodes[0].out_degree, 0);
104    }
105
106    #[test]
107    fn diamond_graph() {
108        let mut graph = Graph::new();
109        graph.add_node(make_node("a.md"));
110        graph.add_node(make_node("b.md"));
111        graph.add_node(make_node("c.md"));
112        graph.add_node(make_node("d.md"));
113        graph.add_edge(make_edge("a.md", "b.md"));
114        graph.add_edge(make_edge("a.md", "c.md"));
115        graph.add_edge(make_edge("b.md", "d.md"));
116        graph.add_edge(make_edge("c.md", "d.md"));
117
118        let config = Config::defaults();
119        let result = Degree.run(&make_ctx(&graph, &config));
120        assert_eq!(result.nodes.len(), 4);
121
122        let a = result.nodes.iter().find(|n| n.node == "a.md").unwrap();
123        assert_eq!(a.in_degree, 0);
124        assert_eq!(a.out_degree, 2);
125
126        let d = result.nodes.iter().find(|n| n.node == "d.md").unwrap();
127        assert_eq!(d.in_degree, 2);
128        assert_eq!(d.out_degree, 0);
129    }
130
131    #[test]
132    fn self_loop() {
133        let mut graph = Graph::new();
134        graph.add_node(make_node("a.md"));
135        graph.add_edge(make_edge("a.md", "a.md"));
136
137        let config = Config::defaults();
138        let result = Degree.run(&make_ctx(&graph, &config));
139        assert_eq!(result.nodes[0].in_degree, 1);
140        assert_eq!(result.nodes[0].out_degree, 1);
141    }
142
143    #[test]
144    fn excludes_synthetic_nodes() {
145        let mut graph = Graph::new();
146        graph.add_node(make_node("a.md"));
147        graph.add_node(Node {
148            path: "https://example.com".into(),
149            node_type: NodeType::External,
150            hash: None,
151            graph: None,
152        });
153        graph.add_edge(make_edge("a.md", "https://example.com"));
154
155        let config = Config::defaults();
156        let result = Degree.run(&make_ctx(&graph, &config));
157        assert_eq!(result.nodes.len(), 1);
158        assert_eq!(result.nodes[0].node, "a.md");
159        assert_eq!(result.nodes[0].out_degree, 0);
160    }
161
162    #[test]
163    fn sorted_by_path() {
164        let mut graph = Graph::new();
165        graph.add_node(make_node("c.md"));
166        graph.add_node(make_node("a.md"));
167        graph.add_node(make_node("b.md"));
168
169        let config = Config::defaults();
170        let result = Degree.run(&make_ctx(&graph, &config));
171        let paths: Vec<&str> = result.nodes.iter().map(|n| n.node.as_str()).collect();
172        assert_eq!(paths, vec!["a.md", "b.md", "c.md"]);
173    }
174}
drft/analyses/degree.rs

drft/analyses/
degree.rs
