rust_igraph/algorithms/paths/
graph_center.rs

1//! Graph center and pseudo-diameter (ALGO-SP-037).
2//!
3//! - `graph_center`: vertices with minimum eccentricity.
4//! - `pseudo_diameter`: lower-bound approximation of the diameter via
5//!   iterative BFS from pseudo-peripheral vertices.
6//!
7//! Counterpart of `igraph_graph_center` and `igraph_pseudo_diameter`
8//! from `references/igraph/src/paths/distances.c`.
9
10use std::collections::VecDeque;
11
12use crate::algorithms::paths::radii::{EccMode, eccentricity_with_mode};
13use crate::core::{Graph, IgraphError, IgraphResult, VertexId};
14
15/// Return the central vertices of a graph — those with minimum eccentricity.
16///
17/// For directed graphs, `mode` controls which direction BFS follows.
18/// For undirected graphs, all modes are equivalent.
19///
20/// Returns an empty vector for an empty graph.
21///
22/// # Examples
23///
24/// ```
25/// use rust_igraph::{Graph, graph_center, EccMode};
26///
27/// // Path 0-1-2-3-4: center is vertex 2
28/// let mut g = Graph::with_vertices(5);
29/// g.add_edge(0, 1).unwrap();
30/// g.add_edge(1, 2).unwrap();
31/// g.add_edge(2, 3).unwrap();
32/// g.add_edge(3, 4).unwrap();
33/// let center = graph_center(&g, EccMode::All).unwrap();
34/// assert_eq!(center, vec![2]);
35/// ```
36pub fn graph_center(graph: &Graph, mode: EccMode) -> IgraphResult<Vec<VertexId>> {
37    let n = graph.vcount();
38    if n == 0 {
39        return Ok(Vec::new());
40    }
41
42    let ecc = eccentricity_with_mode(graph, mode)?;
43
44    let min_ecc = ecc.iter().copied().min().unwrap_or(0);
45
46    let center: Vec<VertexId> = ecc
47        .iter()
48        .enumerate()
49        .filter(|(_, e)| **e == min_ecc)
50        .map(|(i, _)| {
51            #[allow(clippy::cast_possible_truncation)]
52            let v = i as VertexId;
53            v
54        })
55        .collect();
56
57    Ok(center)
58}
59
60/// Result of the pseudo-diameter computation.
61#[derive(Debug, Clone, PartialEq)]
62pub struct PseudoDiameterResult {
63    /// The pseudo-diameter value (lower bound of the true diameter).
64    pub diameter: f64,
65    /// Source vertex of the longest path found.
66    pub from: Option<VertexId>,
67    /// Target vertex of the longest path found.
68    pub to: Option<VertexId>,
69}
70
71/// Approximate the diameter of a graph using pseudo-peripheral vertex search.
72///
73/// Starting from `start`, repeatedly finds the most distant vertex and
74/// switches to it until the eccentricity no longer increases. The result
75/// is a lower bound on the true diameter.
76///
77/// For disconnected graphs, if `unconn` is true, returns the diameter of
78/// the component containing `start`; if false, returns `f64::INFINITY`.
79///
80/// # Arguments
81///
82/// * `graph` — input graph
83/// * `start` — starting vertex (if `None`, uses vertex 0)
84/// * `directed` — whether to respect edge directions (ignored for undirected graphs)
85/// * `unconn` — what to do if graph is disconnected
86///
87/// # Errors
88///
89/// Returns an error if `start` is out of range.
90///
91/// # Examples
92///
93/// ```
94/// use rust_igraph::{Graph, pseudo_diameter};
95///
96/// // Path 0-1-2-3-4: diameter is 4
97/// let mut g = Graph::with_vertices(5);
98/// g.add_edge(0, 1).unwrap();
99/// g.add_edge(1, 2).unwrap();
100/// g.add_edge(2, 3).unwrap();
101/// g.add_edge(3, 4).unwrap();
102/// let result = pseudo_diameter(&g, Some(0), false, true).unwrap();
103/// assert_eq!(result.diameter, 4.0);
104/// ```
105pub fn pseudo_diameter(
106    graph: &Graph,
107    start: Option<VertexId>,
108    directed: bool,
109    unconn: bool,
110) -> IgraphResult<PseudoDiameterResult> {
111    let n = graph.vcount();
112
113    if n == 0 {
114        return Ok(PseudoDiameterResult {
115            diameter: f64::NAN,
116            from: None,
117            to: None,
118        });
119    }
120
121    let vid_start = start.unwrap_or(0);
122    if vid_start >= n {
123        return Err(IgraphError::InvalidArgument(format!(
124            "pseudo_diameter: start vertex {vid_start} out of range (vcount = {n})"
125        )));
126    }
127
128    let mode = if graph.is_directed() && directed {
129        EccMode::Out
130    } else {
131        EccMode::All
132    };
133
134    let mut current = vid_start;
135    let mut current_ecc = 0u32;
136    let mut far_vertex: VertexId = vid_start;
137    let mut from_vertex = vid_start;
138
139    loop {
140        let (ecc, farthest, has_unreachable) = bfs_eccentricity(graph, current, mode)?;
141
142        if has_unreachable && !unconn {
143            return Ok(PseudoDiameterResult {
144                diameter: f64::INFINITY,
145                from: None,
146                to: None,
147            });
148        }
149
150        if ecc > current_ecc {
151            current_ecc = ecc;
152            from_vertex = current;
153            far_vertex = farthest;
154            current = farthest;
155        } else {
156            break;
157        }
158    }
159
160    Ok(PseudoDiameterResult {
161        diameter: f64::from(current_ecc),
162        from: Some(from_vertex),
163        to: Some(far_vertex),
164    })
165}
166
167/// BFS from `source` following `mode` direction. Returns (eccentricity, `farthest_vertex`, `has_unreachable`).
168fn bfs_eccentricity(
169    graph: &Graph,
170    source: VertexId,
171    mode: EccMode,
172) -> IgraphResult<(u32, VertexId, bool)> {
173    let n = graph.vcount() as usize;
174    let mut dist: Vec<Option<u32>> = vec![None; n];
175    let mut queue: VecDeque<VertexId> = VecDeque::new();
176
177    dist[source as usize] = Some(0);
178    queue.push_back(source);
179
180    let mut max_dist: u32 = 0;
181    let mut farthest: VertexId = source;
182
183    while let Some(v) = queue.pop_front() {
184        let d = dist[v as usize].unwrap_or(0);
185
186        let neighbors = match mode {
187            EccMode::Out => graph.incident(v)?,
188            EccMode::In => graph.incident_in(v)?,
189            EccMode::All => {
190                let mut out = graph.incident(v)?;
191                if graph.is_directed() {
192                    let in_edges = graph.incident_in(v)?;
193                    for eid in in_edges {
194                        if !out.contains(&eid) {
195                            out.push(eid);
196                        }
197                    }
198                }
199                out
200            }
201        };
202
203        for eid in neighbors {
204            let (from, to) = graph.edge(eid)?;
205            let nei = if from == v { to } else { from };
206
207            if dist[nei as usize].is_none() {
208                let nd = d.saturating_add(1);
209                dist[nei as usize] = Some(nd);
210                queue.push_back(nei);
211
212                if nd > max_dist {
213                    max_dist = nd;
214                    farthest = nei;
215                }
216            }
217        }
218    }
219
220    let has_unreachable = dist.iter().any(Option::is_none);
221
222    Ok((max_dist, farthest, has_unreachable))
223}
224
225#[cfg(test)]
226#[allow(clippy::float_cmp)]
227mod tests {
228    use super::*;
229
230    #[test]
231    fn center_empty_graph() {
232        let g = Graph::with_vertices(0);
233        let center = graph_center(&g, EccMode::All).unwrap();
234        assert!(center.is_empty());
235    }
236
237    #[test]
238    fn center_single_vertex() {
239        let g = Graph::with_vertices(1);
240        let center = graph_center(&g, EccMode::All).unwrap();
241        assert_eq!(center, vec![0]);
242    }
243
244    #[test]
245    fn center_path_5() {
246        let mut g = Graph::with_vertices(5);
247        g.add_edge(0, 1).unwrap();
248        g.add_edge(1, 2).unwrap();
249        g.add_edge(2, 3).unwrap();
250        g.add_edge(3, 4).unwrap();
251        let center = graph_center(&g, EccMode::All).unwrap();
252        assert_eq!(center, vec![2]);
253    }
254
255    #[test]
256    fn center_path_6() {
257        let mut g = Graph::with_vertices(6);
258        g.add_edge(0, 1).unwrap();
259        g.add_edge(1, 2).unwrap();
260        g.add_edge(2, 3).unwrap();
261        g.add_edge(3, 4).unwrap();
262        g.add_edge(4, 5).unwrap();
263        let center = graph_center(&g, EccMode::All).unwrap();
264        // Even path: center has two vertices
265        assert_eq!(center, vec![2, 3]);
266    }
267
268    #[test]
269    fn center_complete_graph() {
270        let mut g = Graph::with_vertices(4);
271        g.add_edge(0, 1).unwrap();
272        g.add_edge(0, 2).unwrap();
273        g.add_edge(0, 3).unwrap();
274        g.add_edge(1, 2).unwrap();
275        g.add_edge(1, 3).unwrap();
276        g.add_edge(2, 3).unwrap();
277        let center = graph_center(&g, EccMode::All).unwrap();
278        // All vertices have eccentricity 1
279        assert_eq!(center, vec![0, 1, 2, 3]);
280    }
281
282    #[test]
283    fn center_star() {
284        let mut g = Graph::with_vertices(5);
285        g.add_edge(0, 1).unwrap();
286        g.add_edge(0, 2).unwrap();
287        g.add_edge(0, 3).unwrap();
288        g.add_edge(0, 4).unwrap();
289        let center = graph_center(&g, EccMode::All).unwrap();
290        // Center vertex has eccentricity 1, leaves have 2
291        assert_eq!(center, vec![0]);
292    }
293
294    #[test]
295    fn center_cycle() {
296        let mut g = Graph::with_vertices(5);
297        g.add_edge(0, 1).unwrap();
298        g.add_edge(1, 2).unwrap();
299        g.add_edge(2, 3).unwrap();
300        g.add_edge(3, 4).unwrap();
301        g.add_edge(4, 0).unwrap();
302        let center = graph_center(&g, EccMode::All).unwrap();
303        // All vertices in C5 have eccentricity 2
304        assert_eq!(center, vec![0, 1, 2, 3, 4]);
305    }
306
307    #[test]
308    fn pseudo_diameter_empty() {
309        let g = Graph::with_vertices(0);
310        let result = pseudo_diameter(&g, None, false, true).unwrap();
311        assert!(result.diameter.is_nan());
312        assert_eq!(result.from, None);
313        assert_eq!(result.to, None);
314    }
315
316    #[test]
317    fn pseudo_diameter_single_vertex() {
318        let g = Graph::with_vertices(1);
319        let result = pseudo_diameter(&g, Some(0), false, true).unwrap();
320        assert_eq!(result.diameter, 0.0);
321    }
322
323    #[test]
324    fn pseudo_diameter_path_5() {
325        let mut g = Graph::with_vertices(5);
326        g.add_edge(0, 1).unwrap();
327        g.add_edge(1, 2).unwrap();
328        g.add_edge(2, 3).unwrap();
329        g.add_edge(3, 4).unwrap();
330        let result = pseudo_diameter(&g, Some(0), false, true).unwrap();
331        // True diameter is 4; pseudo-diameter should find it
332        assert_eq!(result.diameter, 4.0);
333    }
334
335    #[test]
336    fn pseudo_diameter_cycle() {
337        let mut g = Graph::with_vertices(6);
338        g.add_edge(0, 1).unwrap();
339        g.add_edge(1, 2).unwrap();
340        g.add_edge(2, 3).unwrap();
341        g.add_edge(3, 4).unwrap();
342        g.add_edge(4, 5).unwrap();
343        g.add_edge(5, 0).unwrap();
344        let result = pseudo_diameter(&g, Some(0), false, true).unwrap();
345        // Diameter of C6 is 3
346        assert_eq!(result.diameter, 3.0);
347    }
348
349    #[test]
350    fn pseudo_diameter_complete() {
351        let mut g = Graph::with_vertices(4);
352        g.add_edge(0, 1).unwrap();
353        g.add_edge(0, 2).unwrap();
354        g.add_edge(0, 3).unwrap();
355        g.add_edge(1, 2).unwrap();
356        g.add_edge(1, 3).unwrap();
357        g.add_edge(2, 3).unwrap();
358        let result = pseudo_diameter(&g, Some(0), false, true).unwrap();
359        assert_eq!(result.diameter, 1.0);
360    }
361
362    #[test]
363    fn pseudo_diameter_disconnected_unconn_true() {
364        let mut g = Graph::with_vertices(4);
365        g.add_edge(0, 1).unwrap();
366        g.add_edge(2, 3).unwrap();
367        let result = pseudo_diameter(&g, Some(0), false, true).unwrap();
368        // Only component containing vertex 0: diameter 1
369        assert_eq!(result.diameter, 1.0);
370    }
371
372    #[test]
373    fn pseudo_diameter_disconnected_unconn_false() {
374        let mut g = Graph::with_vertices(4);
375        g.add_edge(0, 1).unwrap();
376        g.add_edge(2, 3).unwrap();
377        let result = pseudo_diameter(&g, Some(0), false, false).unwrap();
378        assert_eq!(result.diameter, f64::INFINITY);
379    }
380
381    #[test]
382    fn pseudo_diameter_start_out_of_range() {
383        let g = Graph::with_vertices(3);
384        assert!(pseudo_diameter(&g, Some(5), false, true).is_err());
385    }
386
387    #[test]
388    fn pseudo_diameter_lower_bound() {
389        // The pseudo-diameter should always be a lower bound of the true diameter
390        let mut g = Graph::with_vertices(7);
391        g.add_edge(0, 1).unwrap();
392        g.add_edge(1, 2).unwrap();
393        g.add_edge(2, 3).unwrap();
394        g.add_edge(3, 4).unwrap();
395        g.add_edge(4, 5).unwrap();
396        g.add_edge(5, 6).unwrap();
397        g.add_edge(0, 3).unwrap(); // shortcut
398        let result = pseudo_diameter(&g, Some(0), false, true).unwrap();
399        // The true diameter is at least result.diameter
400        assert!(result.diameter >= 3.0); // true diameter is 4 (3-4-5-6 path + any start)
401    }
402
403    #[test]
404    fn pseudo_diameter_directed() {
405        let mut g = Graph::new(3, true).unwrap();
406        g.add_edge(0, 1).unwrap();
407        g.add_edge(1, 2).unwrap();
408        let result = pseudo_diameter(&g, Some(0), true, true).unwrap();
409        assert_eq!(result.diameter, 2.0);
410    }
411}
rust_igraph/algorithms/paths/graph_center.rs

rust_igraph/algorithms/paths/
graph_center.rs
