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        // Degree counts ALL edges (internal + outbound) for included nodes.
27        // A file linking to a URL or a non-included file has out_degree > 0.
28        // This differs from connectivity analyses which scope to internal edges.
29        let mut nodes: Vec<NodeDegree> = graph
30            .nodes
31            .keys()
32            .filter(|path| graph.is_included_node(path))
33            .map(|path| {
34                let in_degree = graph
35                    .reverse
36                    .get(path.as_str())
37                    .map(|indices| indices.len())
38                    .unwrap_or(0);
39
40                let out_degree = graph
41                    .forward
42                    .get(path.as_str())
43                    .map(|indices| indices.len())
44                    .unwrap_or(0);
45
46                NodeDegree {
47                    node: path.clone(),
48                    in_degree,
49                    out_degree,
50                }
51            })
52            .collect();
53
54        nodes.sort_by(|a, b| a.node.cmp(&b.node));
55
56        DegreeResult { nodes }
57    }
58}
59
60#[cfg(test)]
61mod tests {
62    use super::*;
63    use crate::analyses::AnalysisContext;
64    use crate::config::Config;
65    use crate::graph::test_helpers::{make_edge, make_node};
66    use crate::graph::{Graph, Node, NodeType};
67    use std::collections::HashMap;
68    use std::path::Path;
69
70    fn make_ctx<'a>(graph: &'a Graph, config: &'a Config) -> AnalysisContext<'a> {
71        AnalysisContext {
72            graph,
73            root: Path::new("."),
74            config,
75            lockfile: None,
76        }
77    }
78
79    #[test]
80    fn empty_graph() {
81        let graph = Graph::new();
82        let config = Config::defaults();
83        let result = Degree.run(&make_ctx(&graph, &config));
84        assert!(result.nodes.is_empty());
85    }
86
87    #[test]
88    fn single_node() {
89        let mut graph = Graph::new();
90        graph.add_node(make_node("a.md"));
91
92        let config = Config::defaults();
93        let result = Degree.run(&make_ctx(&graph, &config));
94        assert_eq!(result.nodes.len(), 1);
95        assert_eq!(result.nodes[0].node, "a.md");
96        assert_eq!(result.nodes[0].in_degree, 0);
97        assert_eq!(result.nodes[0].out_degree, 0);
98    }
99
100    #[test]
101    fn diamond_graph() {
102        let mut graph = Graph::new();
103        graph.add_node(make_node("a.md"));
104        graph.add_node(make_node("b.md"));
105        graph.add_node(make_node("c.md"));
106        graph.add_node(make_node("d.md"));
107        graph.add_edge(make_edge("a.md", "b.md"));
108        graph.add_edge(make_edge("a.md", "c.md"));
109        graph.add_edge(make_edge("b.md", "d.md"));
110        graph.add_edge(make_edge("c.md", "d.md"));
111
112        let config = Config::defaults();
113        let result = Degree.run(&make_ctx(&graph, &config));
114        assert_eq!(result.nodes.len(), 4);
115
116        let a = result.nodes.iter().find(|n| n.node == "a.md").unwrap();
117        assert_eq!(a.in_degree, 0);
118        assert_eq!(a.out_degree, 2);
119
120        let d = result.nodes.iter().find(|n| n.node == "d.md").unwrap();
121        assert_eq!(d.in_degree, 2);
122        assert_eq!(d.out_degree, 0);
123    }
124
125    #[test]
126    fn self_loop() {
127        let mut graph = Graph::new();
128        graph.add_node(make_node("a.md"));
129        graph.add_edge(make_edge("a.md", "a.md"));
130
131        let config = Config::defaults();
132        let result = Degree.run(&make_ctx(&graph, &config));
133        assert_eq!(result.nodes[0].in_degree, 1);
134        assert_eq!(result.nodes[0].out_degree, 1);
135    }
136
137    #[test]
138    fn counts_edges_to_external_nodes() {
139        let mut graph = Graph::new();
140        graph.add_node(make_node("a.md"));
141        graph.add_node(Node {
142            path: "https://example.com".into(),
143            node_type: NodeType::External,
144            hash: None,
145            graph: None,
146            is_graph: false,
147            metadata: HashMap::new(),
148            included: false,
149        });
150        graph.add_edge(make_edge("a.md", "https://example.com"));
151
152        let config = Config::defaults();
153        let result = Degree.run(&make_ctx(&graph, &config));
154        assert_eq!(result.nodes.len(), 1);
155        assert_eq!(result.nodes[0].node, "a.md");
156        assert_eq!(result.nodes[0].out_degree, 1);
157    }
158
159    #[test]
160    fn sorted_by_path() {
161        let mut graph = Graph::new();
162        graph.add_node(make_node("c.md"));
163        graph.add_node(make_node("a.md"));
164        graph.add_node(make_node("b.md"));
165
166        let config = Config::defaults();
167        let result = Degree.run(&make_ctx(&graph, &config));
168        let paths: Vec<&str> = result.nodes.iter().map(|n| n.node.as_str()).collect();
169        assert_eq!(paths, vec!["a.md", "b.md", "c.md"]);
170    }
171}
drft/analyses/degree.rs

drft/analyses/
degree.rs
