use_graph_metrics/
lib.rs

1#![forbid(unsafe_code)]
2//! Primitive graph metrics.
3//!
4//! The crate provides small helpers for counting nodes and edges, inspecting
5//! degrees, and computing simple directed or undirected densities.
6//!
7//! # Examples
8//!
9//! ```rust
10//! use use_graph_metrics::{average_degree, density_directed, edge_count_directed, max_degree};
11//!
12//! let adjacency = vec![vec![1, 2], vec![2], vec![]];
13//!
14//! assert_eq!(edge_count_directed(&adjacency), 3);
15//! assert_eq!(max_degree(&adjacency), Some(2));
16//! assert_eq!(average_degree(&adjacency), Some(1.0));
17//! assert_eq!(density_directed(&adjacency), Some(0.5));
18//! ```
19
20#[must_use]
21pub fn node_count(adjacency: &[Vec<usize>]) -> usize {
22    adjacency.len()
23}
24
25#[must_use]
26pub fn edge_count_directed(adjacency: &[Vec<usize>]) -> usize {
27    adjacency.iter().map(Vec::len).sum()
28}
29
30#[must_use]
31pub fn edge_count_undirected(adjacency: &[Vec<usize>]) -> usize {
32    let mut self_loops = 0;
33    let mut non_self_edges = 0;
34
35    for (node, neighbors) in adjacency.iter().enumerate() {
36        for &neighbor in neighbors {
37            if neighbor == node {
38                self_loops += 1;
39            } else {
40                non_self_edges += 1;
41            }
42        }
43    }
44
45    self_loops + non_self_edges / 2
46}
47
48#[must_use]
49pub fn degrees(adjacency: &[Vec<usize>]) -> Vec<usize> {
50    adjacency.iter().map(Vec::len).collect()
51}
52
53#[must_use]
54pub fn max_degree(adjacency: &[Vec<usize>]) -> Option<usize> {
55    adjacency.iter().map(Vec::len).max()
56}
57
58#[must_use]
59pub fn min_degree(adjacency: &[Vec<usize>]) -> Option<usize> {
60    adjacency.iter().map(Vec::len).min()
61}
62
63#[must_use]
64pub fn average_degree(adjacency: &[Vec<usize>]) -> Option<f64> {
65    if adjacency.is_empty() {
66        None
67    } else {
68        Some(edge_count_directed(adjacency) as f64 / adjacency.len() as f64)
69    }
70}
71
72#[must_use]
73pub fn density_directed(adjacency: &[Vec<usize>]) -> Option<f64> {
74    match adjacency.len() {
75        0 => None,
76        1 => Some(0.0),
77        node_count => {
78            Some(edge_count_directed(adjacency) as f64 / (node_count * (node_count - 1)) as f64)
79        }
80    }
81}
82
83#[must_use]
84pub fn density_undirected(adjacency: &[Vec<usize>]) -> Option<f64> {
85    match adjacency.len() {
86        0 => None,
87        1 => Some(0.0),
88        node_count => Some(
89            (2 * edge_count_undirected(adjacency)) as f64 / (node_count * (node_count - 1)) as f64,
90        ),
91    }
92}
93
94#[cfg(test)]
95mod tests {
96    use super::{
97        average_degree, degrees, density_directed, density_undirected, edge_count_directed,
98        edge_count_undirected, max_degree, min_degree, node_count,
99    };
100
101    #[test]
102    fn computes_directed_graph_metrics() {
103        let adjacency = vec![vec![1, 2], vec![2], vec![]];
104
105        assert_eq!(node_count(&adjacency), 3);
106        assert_eq!(edge_count_directed(&adjacency), 3);
107        assert_eq!(degrees(&adjacency), vec![2, 1, 0]);
108        assert_eq!(max_degree(&adjacency), Some(2));
109        assert_eq!(min_degree(&adjacency), Some(0));
110        assert_eq!(average_degree(&adjacency), Some(1.0));
111        assert_eq!(density_directed(&adjacency), Some(0.5));
112    }
113
114    #[test]
115    fn computes_undirected_graph_metrics() {
116        let adjacency = vec![vec![1, 2], vec![0], vec![0]];
117
118        assert_eq!(edge_count_undirected(&adjacency), 2);
119        assert_eq!(density_undirected(&adjacency), Some(2.0 / 3.0));
120    }
121
122    #[test]
123    fn handles_empty_and_single_node_graphs() {
124        assert_eq!(node_count(&[]), 0);
125        assert_eq!(average_degree(&[]), None);
126        assert_eq!(density_directed(&[]), None);
127        assert_eq!(density_undirected(&[]), None);
128
129        let single = vec![Vec::new()];
130        assert_eq!(edge_count_directed(&single), 0);
131        assert_eq!(edge_count_undirected(&single), 0);
132        assert_eq!(average_degree(&single), Some(0.0));
133        assert_eq!(density_directed(&single), Some(0.0));
134        assert_eq!(density_undirected(&single), Some(0.0));
135    }
136
137    #[test]
138    fn counts_self_loops_deliberately_in_undirected_graphs() {
139        let adjacency = vec![vec![0, 1], vec![0]];
140
141        assert_eq!(edge_count_undirected(&adjacency), 2);
142    }
143}
use_graph_metrics/lib.rs

use_graph_metrics/
lib.rs
