scirs2_graph/algorithms/
properties.rs

1//! Graph property algorithms
2//!
3//! This module contains algorithms for computing various properties of graphs.
4
5use crate::algorithms::shortest_path::dijkstra_path;
6use crate::base::{EdgeWeight, Graph, IndexType, Node};
7use std::hash::Hash;
8
9/// Computes the diameter of a graph
10///
11/// The diameter is the maximum shortest path distance between any two nodes in the graph.
12/// Returns None if the graph is disconnected.
13#[allow(dead_code)]
14pub fn diameter<N, E, Ix>(graph: &Graph<N, E, Ix>) -> Option<f64>
15where
16    N: Node + Clone + Hash + Eq + std::fmt::Debug,
17    E: EdgeWeight
18        + Into<f64>
19        + Clone
20        + scirs2_core::numeric::Zero
21        + scirs2_core::numeric::One
22        + std::cmp::PartialOrd
23        + std::fmt::Debug
24        + Copy
25        + Default,
26    Ix: IndexType,
27{
28    let nodes: Vec<N> = graph.nodes().into_iter().cloned().collect();
29    let n = nodes.len();
30
31    if n == 0 {
32        return None;
33    }
34
35    let mut max_distance = 0.0;
36
37    // Compute all-pairs shortest paths
38    for i in 0..n {
39        for j in i + 1..n {
40            match dijkstra_path(graph, &nodes[i], &nodes[j]) {
41                Ok(Some(path)) => {
42                    let distance: f64 = path.total_weight.into();
43                    if distance > max_distance {
44                        max_distance = distance;
45                    }
46                }
47                Ok(None) => return None, // No path exists
48                Err(_) => return None,   // Graph is disconnected
49            }
50        }
51    }
52
53    Some(max_distance)
54}
55
56/// Computes the radius of a graph
57///
58/// The radius is the minimum eccentricity over all nodes, where eccentricity of a node
59/// is the maximum distance from that node to any other node.
60/// Returns None if the graph is disconnected.
61#[allow(dead_code)]
62pub fn radius<N, E, Ix>(graph: &Graph<N, E, Ix>) -> Option<f64>
63where
64    N: Node + Clone + Hash + Eq + std::fmt::Debug,
65    E: EdgeWeight
66        + Into<f64>
67        + Clone
68        + scirs2_core::numeric::Zero
69        + scirs2_core::numeric::One
70        + std::cmp::PartialOrd
71        + std::fmt::Debug
72        + Copy
73        + Default,
74    Ix: IndexType,
75{
76    let nodes: Vec<N> = graph.nodes().into_iter().cloned().collect();
77    let n = nodes.len();
78
79    if n == 0 {
80        return None;
81    }
82
83    let mut min_eccentricity = f64::INFINITY;
84
85    // Compute eccentricity for each node
86    for i in 0..n {
87        let mut max_distance_from_i = 0.0;
88
89        for j in 0..n {
90            if i != j {
91                match dijkstra_path(graph, &nodes[i], &nodes[j]) {
92                    Ok(Some(path)) => {
93                        let distance: f64 = path.total_weight.into();
94                        if distance > max_distance_from_i {
95                            max_distance_from_i = distance;
96                        }
97                    }
98                    Ok(None) => return None, // No path exists
99                    Err(_) => return None,   // Graph is disconnected
100                }
101            }
102        }
103
104        if max_distance_from_i < min_eccentricity {
105            min_eccentricity = max_distance_from_i;
106        }
107    }
108
109    Some(min_eccentricity)
110}
111
112/// Find the center nodes of a graph
113///
114/// Center nodes are those with minimum eccentricity (equal to the radius).
115/// Returns empty vector if the graph is disconnected.
116#[allow(dead_code)]
117pub fn center_nodes<N, E, Ix>(graph: &Graph<N, E, Ix>) -> Vec<N>
118where
119    N: Node + Clone + Hash + Eq + std::fmt::Debug,
120    E: EdgeWeight
121        + Into<f64>
122        + Clone
123        + scirs2_core::numeric::Zero
124        + scirs2_core::numeric::One
125        + std::cmp::PartialOrd
126        + std::fmt::Debug
127        + Copy
128        + Default,
129    Ix: IndexType,
130{
131    let nodes: Vec<N> = graph.nodes().into_iter().cloned().collect();
132    let n = nodes.len();
133
134    if n == 0 {
135        return vec![];
136    }
137
138    let mut eccentricities = vec![0.0; n];
139    let mut min_eccentricity = f64::INFINITY;
140
141    // Compute eccentricity for each node
142    for i in 0..n {
143        let mut max_distance_from_i = 0.0;
144
145        for j in 0..n {
146            if i != j {
147                match dijkstra_path(graph, &nodes[i], &nodes[j]) {
148                    Ok(Some(path)) => {
149                        let distance: f64 = path.total_weight.into();
150                        if distance > max_distance_from_i {
151                            max_distance_from_i = distance;
152                        }
153                    }
154                    Ok(None) => return vec![], // No path exists
155                    Err(_) => return vec![],   // Graph is disconnected
156                }
157            }
158        }
159
160        eccentricities[i] = max_distance_from_i;
161
162        if max_distance_from_i < min_eccentricity {
163            min_eccentricity = max_distance_from_i;
164        }
165    }
166
167    // Collect all nodes with minimum eccentricity
168    nodes
169        .into_iter()
170        .enumerate()
171        .filter(|(i, _)| (eccentricities[*i] - min_eccentricity).abs() < f64::EPSILON)
172        .map(|(_, node)| node)
173        .collect()
174}
175
176#[cfg(test)]
177mod tests {
178    use super::*;
179    use crate::error::Result as GraphResult;
180    use crate::generators::create_graph;
181
182    #[test]
183    fn test_diameter_radius_center() -> GraphResult<()> {
184        // Create a path graph: 0 - 1 - 2 - 3 - 4
185        let mut path = create_graph::<i32, f64>();
186        path.add_edge(0, 1, 1.0)?;
187        path.add_edge(1, 2, 1.0)?;
188        path.add_edge(2, 3, 1.0)?;
189        path.add_edge(3, 4, 1.0)?;
190
191        // Diameter should be 4 (from 0 to 4)
192        assert_eq!(diameter(&path), Some(4.0));
193
194        // Radius should be 2 (from center node 2)
195        assert_eq!(radius(&path), Some(2.0));
196
197        // Center should be node 2
198        let centers = center_nodes(&path);
199        assert_eq!(centers.len(), 1);
200        assert_eq!(centers[0], 2);
201
202        Ok(())
203    }
204
205    #[test]
206    fn test_stargraph() -> GraphResult<()> {
207        // Create a star graph with center 0
208        let mut star = create_graph::<i32, f64>();
209        star.add_edge(0, 1, 1.0)?;
210        star.add_edge(0, 2, 1.0)?;
211        star.add_edge(0, 3, 1.0)?;
212        star.add_edge(0, 4, 1.0)?;
213
214        // Diameter should be 2 (from any leaf to another)
215        assert_eq!(diameter(&star), Some(2.0));
216
217        // Radius should be 1 (from center)
218        assert_eq!(radius(&star), Some(1.0));
219
220        // Center should be node 0
221        let centers = center_nodes(&star);
222        assert_eq!(centers.len(), 1);
223        assert_eq!(centers[0], 0);
224
225        Ok(())
226    }
227
228    #[test]
229    fn test_disconnectedgraph() -> GraphResult<()> {
230        // Create a disconnected graph
231        let mut graph = create_graph::<i32, f64>();
232        graph.add_edge(0, 1, 1.0)?;
233        graph.add_edge(2, 3, 1.0)?;
234
235        // All functions should return None/empty for disconnected graphs
236        assert_eq!(diameter(&graph), None);
237        assert_eq!(radius(&graph), None);
238        assert!(center_nodes(&graph).is_empty());
239
240        Ok(())
241    }
242}
scirs2_graph/algorithms/properties.rs

scirs2_graph/algorithms/
properties.rs
