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

drft/analyses/
degree.rs
