rust_igraph/algorithms/properties/
is_spider.rs

1//! Spider graph predicate (ALGO-PR-117).
2//!
3//! A spider graph (also called a subdivided star or caterpillar star)
4//! is a tree with exactly one vertex of degree ≥ 3 (the body), and
5//! all other vertices have degree ≤ 2. Equivalently, a spider is a
6//! tree formed by joining paths at a common endpoint.
7//!
8//! For n ≤ 2, any tree is a spider (including a single edge or vertex).
9//! A star `K_{1,k}` is a spider where all legs have length 1.
10//! A path is a spider with exactly 2 legs (or 1 leg for `P_2`).
11//!
12//! Directed graphs are treated as undirected.
13
14use crate::algorithms::paths::dijkstra::DijkstraMode;
15use crate::algorithms::properties::is_tree::is_tree;
16use crate::core::{Graph, IgraphResult};
17
18/// Check whether a graph is a spider graph.
19///
20/// A spider is a tree with at most one vertex of degree ≥ 3.
21/// Every star and every path is a spider.
22///
23/// Directed graphs are treated as undirected.
24///
25/// # Examples
26///
27/// ```
28/// use rust_igraph::{Graph, is_spider};
29///
30/// // Star `S_3` is a spider
31/// let mut g = Graph::with_vertices(4);
32/// g.add_edge(0, 1).unwrap();
33/// g.add_edge(0, 2).unwrap();
34/// g.add_edge(0, 3).unwrap();
35/// assert!(is_spider(&g).unwrap());
36///
37/// // Two adjacent high-degree vertices → NOT a spider
38/// let mut g = Graph::with_vertices(7);
39/// g.add_edge(0, 1).unwrap();
40/// g.add_edge(0, 2).unwrap();
41/// g.add_edge(0, 3).unwrap();
42/// g.add_edge(3, 4).unwrap();
43/// g.add_edge(3, 5).unwrap();
44/// g.add_edge(3, 6).unwrap();
45/// assert!(!is_spider(&g).unwrap());
46/// ```
47pub fn is_spider(graph: &Graph) -> IgraphResult<bool> {
48    if is_tree(graph, DijkstraMode::All)?.is_none() {
49        return Ok(false);
50    }
51
52    let n = graph.vcount();
53    if n <= 3 {
54        return Ok(true);
55    }
56
57    let mut high_degree_count = 0u32;
58    for v in 0..n {
59        let deg = graph.degree(v)?;
60        if deg >= 3 {
61            high_degree_count = high_degree_count.saturating_add(1);
62            if high_degree_count > 1 {
63                return Ok(false);
64            }
65        }
66    }
67
68    Ok(true)
69}
70
71#[cfg(test)]
72mod tests {
73    use super::*;
74
75    #[test]
76    fn empty_graph() {
77        // Null graph is not a tree → not a spider
78        let g = Graph::with_vertices(0);
79        assert!(!is_spider(&g).unwrap());
80    }
81
82    #[test]
83    fn single_vertex() {
84        let g = Graph::with_vertices(1);
85        assert!(is_spider(&g).unwrap());
86    }
87
88    #[test]
89    fn single_edge() {
90        let mut g = Graph::with_vertices(2);
91        g.add_edge(0, 1).unwrap();
92        assert!(is_spider(&g).unwrap());
93    }
94
95    #[test]
96    fn path_p3() {
97        let mut g = Graph::with_vertices(3);
98        g.add_edge(0, 1).unwrap();
99        g.add_edge(1, 2).unwrap();
100        assert!(is_spider(&g).unwrap());
101    }
102
103    #[test]
104    fn path_p5() {
105        let mut g = Graph::with_vertices(5);
106        g.add_edge(0, 1).unwrap();
107        g.add_edge(1, 2).unwrap();
108        g.add_edge(2, 3).unwrap();
109        g.add_edge(3, 4).unwrap();
110        assert!(is_spider(&g).unwrap());
111    }
112
113    #[test]
114    fn star_s3() {
115        let mut g = Graph::with_vertices(4);
116        g.add_edge(0, 1).unwrap();
117        g.add_edge(0, 2).unwrap();
118        g.add_edge(0, 3).unwrap();
119        assert!(is_spider(&g).unwrap());
120    }
121
122    #[test]
123    fn star_s5() {
124        let mut g = Graph::with_vertices(6);
125        g.add_edge(0, 1).unwrap();
126        g.add_edge(0, 2).unwrap();
127        g.add_edge(0, 3).unwrap();
128        g.add_edge(0, 4).unwrap();
129        g.add_edge(0, 5).unwrap();
130        assert!(is_spider(&g).unwrap());
131    }
132
133    #[test]
134    fn spider_with_legs() {
135        // Body at 0, three legs of lengths 1, 2, 3
136        // 0-1, 0-2-3, 0-4-5-6
137        let mut g = Graph::with_vertices(7);
138        g.add_edge(0, 1).unwrap();
139        g.add_edge(0, 2).unwrap();
140        g.add_edge(2, 3).unwrap();
141        g.add_edge(0, 4).unwrap();
142        g.add_edge(4, 5).unwrap();
143        g.add_edge(5, 6).unwrap();
144        assert!(is_spider(&g).unwrap());
145    }
146
147    #[test]
148    fn two_branching_vertices_not_spider() {
149        // 0-1-2, 1-3, 2-4, 2-5 → both 1 and 2 have degree 3
150        let mut g = Graph::with_vertices(6);
151        g.add_edge(0, 1).unwrap();
152        g.add_edge(1, 2).unwrap();
153        g.add_edge(1, 3).unwrap();
154        g.add_edge(2, 4).unwrap();
155        g.add_edge(2, 5).unwrap();
156        assert!(!is_spider(&g).unwrap());
157    }
158
159    #[test]
160    fn triangle_not_tree() {
161        let mut g = Graph::with_vertices(3);
162        g.add_edge(0, 1).unwrap();
163        g.add_edge(1, 2).unwrap();
164        g.add_edge(2, 0).unwrap();
165        assert!(!is_spider(&g).unwrap());
166    }
167
168    #[test]
169    fn disconnected_not_spider() {
170        let g = Graph::with_vertices(3);
171        // 3 isolated vertices → forest but not tree
172        assert!(!is_spider(&g).unwrap());
173    }
174
175    #[test]
176    fn caterpillar_not_spider() {
177        // 0-1-2-3, 1-4, 2-5 → both 1 and 2 have degree 3 → not spider
178        let mut g = Graph::with_vertices(6);
179        g.add_edge(0, 1).unwrap();
180        g.add_edge(1, 2).unwrap();
181        g.add_edge(2, 3).unwrap();
182        g.add_edge(1, 4).unwrap();
183        g.add_edge(2, 5).unwrap();
184        assert!(!is_spider(&g).unwrap());
185    }
186
187    #[test]
188    fn directed_treated_as_undirected() {
189        // Directed star
190        let mut g = Graph::new(4, true).unwrap();
191        g.add_edge(0, 1).unwrap();
192        g.add_edge(0, 2).unwrap();
193        g.add_edge(0, 3).unwrap();
194        assert!(is_spider(&g).unwrap());
195    }
196
197    #[test]
198    fn two_vertices_no_edge() {
199        // Not connected → not a tree → not a spider
200        let g = Graph::with_vertices(2);
201        assert!(!is_spider(&g).unwrap());
202    }
203}
rust_igraph/algorithms/properties/is_spider.rs

rust_igraph/algorithms/properties/
is_spider.rs
