rust_igraph/algorithms/properties/
is_star.rs

1//! Star graph predicate (ALGO-PR-091).
2//!
3//! A star graph `K_{1,n-1}` (or `S_n`) has one central vertex of
4//! degree n-1 connected to n-1 leaf vertices, each of degree 1.
5//! Equivalently, it is a complete bipartite graph with one part of
6//! size 1.
7//!
8//! For directed graphs, the function returns `false`.
9
10use crate::algorithms::paths::dijkstra::DijkstraMode;
11use crate::algorithms::properties::is_tree::is_tree;
12use crate::core::{Graph, IgraphResult};
13
14/// Check whether a graph is a star graph.
15///
16/// A star graph has one center vertex connected to all other vertices,
17/// with no other edges. `K_{1,0}` (single vertex) and `K_{1,1}`
18/// (single edge) are considered stars.
19///
20/// Returns `false` for directed graphs and the empty graph (no vertices).
21///
22/// # Examples
23///
24/// ```
25/// use rust_igraph::{Graph, is_star};
26///
27/// // K_{1,4}: center 0 with 4 leaves
28/// let mut g = Graph::with_vertices(5);
29/// for i in 1..5u32 {
30///     g.add_edge(0, i).unwrap();
31/// }
32/// assert!(is_star(&g).unwrap());
33///
34/// // Path P_3 is NOT a star (middle vertex has degree 2, not n-1=2... wait
35/// // P_3 has 3 vertices, center degree should be 2. Actually P_3 IS K_{1,2}!)
36/// // Use P_4 as negative example instead.
37/// let mut g = Graph::with_vertices(4);
38/// g.add_edge(0, 1).unwrap();
39/// g.add_edge(1, 2).unwrap();
40/// g.add_edge(2, 3).unwrap();
41/// assert!(!is_star(&g).unwrap());
42/// ```
43pub fn is_star(graph: &Graph) -> IgraphResult<bool> {
44    if graph.is_directed() {
45        return Ok(false);
46    }
47
48    let n = graph.vcount();
49    if n == 0 {
50        return Ok(false);
51    }
52    if n == 1 {
53        return Ok(true);
54    }
55
56    if is_tree(graph, DijkstraMode::All)?.is_none() {
57        return Ok(false);
58    }
59
60    // A star has exactly one vertex of degree n-1 and all others of degree 1.
61    // Equivalently, a tree with exactly n-1 edges where one vertex has degree n-1.
62    let n_minus_1 = n - 1;
63    let mut found_center = false;
64    for v in 0..n {
65        let d = graph.degree(v)?;
66        if d == n_minus_1 as usize {
67            found_center = true;
68        } else if d != 1 {
69            return Ok(false);
70        }
71    }
72
73    Ok(found_center)
74}
75
76#[cfg(test)]
77mod tests {
78    use super::*;
79
80    #[test]
81    fn empty_graph() {
82        let g = Graph::with_vertices(0);
83        assert!(!is_star(&g).unwrap());
84    }
85
86    #[test]
87    fn single_vertex() {
88        let g = Graph::with_vertices(1);
89        assert!(is_star(&g).unwrap());
90    }
91
92    #[test]
93    fn single_edge() {
94        let mut g = Graph::with_vertices(2);
95        g.add_edge(0, 1).unwrap();
96        assert!(is_star(&g).unwrap());
97    }
98
99    #[test]
100    fn k13() {
101        let mut g = Graph::with_vertices(4);
102        g.add_edge(0, 1).unwrap();
103        g.add_edge(0, 2).unwrap();
104        g.add_edge(0, 3).unwrap();
105        assert!(is_star(&g).unwrap());
106    }
107
108    #[test]
109    fn k14() {
110        let mut g = Graph::with_vertices(5);
111        for i in 1..5u32 {
112            g.add_edge(0, i).unwrap();
113        }
114        assert!(is_star(&g).unwrap());
115    }
116
117    #[test]
118    fn k17_center_not_zero() {
119        // Center is vertex 3, not vertex 0
120        let mut g = Graph::with_vertices(8);
121        for i in 0..8u32 {
122            if i != 3 {
123                g.add_edge(3, i).unwrap();
124            }
125        }
126        assert!(is_star(&g).unwrap());
127    }
128
129    #[test]
130    fn path_p4_not_star() {
131        let mut g = Graph::with_vertices(4);
132        g.add_edge(0, 1).unwrap();
133        g.add_edge(1, 2).unwrap();
134        g.add_edge(2, 3).unwrap();
135        assert!(!is_star(&g).unwrap());
136    }
137
138    #[test]
139    fn triangle_not_star() {
140        let mut g = Graph::with_vertices(3);
141        g.add_edge(0, 1).unwrap();
142        g.add_edge(1, 2).unwrap();
143        g.add_edge(2, 0).unwrap();
144        assert!(!is_star(&g).unwrap());
145    }
146
147    #[test]
148    fn caterpillar_not_star() {
149        let mut g = Graph::with_vertices(5);
150        g.add_edge(0, 1).unwrap();
151        g.add_edge(1, 2).unwrap();
152        g.add_edge(2, 3).unwrap();
153        g.add_edge(1, 4).unwrap();
154        assert!(!is_star(&g).unwrap());
155    }
156
157    #[test]
158    fn directed_returns_false() {
159        let mut g = Graph::new(4, true).unwrap();
160        g.add_edge(0, 1).unwrap();
161        g.add_edge(0, 2).unwrap();
162        g.add_edge(0, 3).unwrap();
163        assert!(!is_star(&g).unwrap());
164    }
165
166    #[test]
167    fn disconnected_not_star() {
168        let mut g = Graph::with_vertices(4);
169        g.add_edge(0, 1).unwrap();
170        assert!(!is_star(&g).unwrap());
171    }
172
173    #[test]
174    fn two_isolated_not_star() {
175        let g = Graph::with_vertices(2);
176        assert!(!is_star(&g).unwrap());
177    }
178}
rust_igraph/algorithms/properties/is_star.rs

rust_igraph/algorithms/properties/
is_star.rs
