rust_igraph/algorithms/properties/
is_path.rs

1//! Path graph predicate (ALGO-PR-088).
2//!
3//! A path graph `P_n` is a tree on n vertices where every vertex has
4//! degree at most 2 (equivalently, exactly two vertices have degree 1
5//! and the rest have degree 2, or n ≤ 1).
6//!
7//! For directed graphs, the function returns `false`.
8
9use crate::algorithms::paths::dijkstra::DijkstraMode;
10use crate::algorithms::properties::is_tree::is_tree;
11use crate::core::{Graph, IgraphResult};
12
13/// Check whether a graph is a path graph.
14///
15/// A path graph `P_n` has n vertices connected in a single line:
16/// 0-1-2-..-(n-1). Every vertex has degree ≤ 2, and the graph is a
17/// tree (connected, acyclic).
18///
19/// Returns `false` for directed graphs.
20/// Returns `true` for the empty graph and single vertex (`P_0`, `P_1`).
21///
22/// # Examples
23///
24/// ```
25/// use rust_igraph::{Graph, is_path};
26///
27/// // P_4: 0-1-2-3
28/// let mut g = Graph::with_vertices(4);
29/// g.add_edge(0, 1).unwrap();
30/// g.add_edge(1, 2).unwrap();
31/// g.add_edge(2, 3).unwrap();
32/// assert!(is_path(&g).unwrap());
33///
34/// // Star K_{1,3} is NOT a path (center has degree 3)
35/// let mut g = Graph::with_vertices(4);
36/// for i in 1..4u32 {
37///     g.add_edge(0, i).unwrap();
38/// }
39/// assert!(!is_path(&g).unwrap());
40/// ```
41pub fn is_path(graph: &Graph) -> IgraphResult<bool> {
42    if graph.is_directed() {
43        return Ok(false);
44    }
45
46    let n = graph.vcount();
47    if n == 0 {
48        return Ok(true);
49    }
50
51    if is_tree(graph, DijkstraMode::All)?.is_none() {
52        return Ok(false);
53    }
54
55    for v in 0..n {
56        if graph.degree(v)? > 2 {
57            return Ok(false);
58        }
59    }
60
61    Ok(true)
62}
63
64#[cfg(test)]
65mod tests {
66    use super::*;
67
68    #[test]
69    fn empty_graph() {
70        let g = Graph::with_vertices(0);
71        assert!(is_path(&g).unwrap());
72    }
73
74    #[test]
75    fn single_vertex() {
76        let g = Graph::with_vertices(1);
77        assert!(is_path(&g).unwrap());
78    }
79
80    #[test]
81    fn single_edge() {
82        let mut g = Graph::with_vertices(2);
83        g.add_edge(0, 1).unwrap();
84        assert!(is_path(&g).unwrap());
85    }
86
87    #[test]
88    fn p3() {
89        let mut g = Graph::with_vertices(3);
90        g.add_edge(0, 1).unwrap();
91        g.add_edge(1, 2).unwrap();
92        assert!(is_path(&g).unwrap());
93    }
94
95    #[test]
96    fn p5() {
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        assert!(is_path(&g).unwrap());
103    }
104
105    #[test]
106    fn star_not_path() {
107        let mut g = Graph::with_vertices(4);
108        g.add_edge(0, 1).unwrap();
109        g.add_edge(0, 2).unwrap();
110        g.add_edge(0, 3).unwrap();
111        assert!(!is_path(&g).unwrap());
112    }
113
114    #[test]
115    fn cycle_not_path() {
116        let mut g = Graph::with_vertices(4);
117        g.add_edge(0, 1).unwrap();
118        g.add_edge(1, 2).unwrap();
119        g.add_edge(2, 3).unwrap();
120        g.add_edge(3, 0).unwrap();
121        assert!(!is_path(&g).unwrap());
122    }
123
124    #[test]
125    fn triangle_not_path() {
126        let mut g = Graph::with_vertices(3);
127        g.add_edge(0, 1).unwrap();
128        g.add_edge(1, 2).unwrap();
129        g.add_edge(2, 0).unwrap();
130        assert!(!is_path(&g).unwrap());
131    }
132
133    #[test]
134    fn caterpillar_not_path() {
135        let mut g = Graph::with_vertices(5);
136        g.add_edge(0, 1).unwrap();
137        g.add_edge(1, 2).unwrap();
138        g.add_edge(2, 3).unwrap();
139        g.add_edge(1, 4).unwrap();
140        assert!(!is_path(&g).unwrap());
141    }
142
143    #[test]
144    fn disconnected_not_path() {
145        let mut g = Graph::with_vertices(4);
146        g.add_edge(0, 1).unwrap();
147        g.add_edge(2, 3).unwrap();
148        assert!(!is_path(&g).unwrap());
149    }
150
151    #[test]
152    fn directed_returns_false() {
153        let mut g = Graph::new(3, true).unwrap();
154        g.add_edge(0, 1).unwrap();
155        g.add_edge(1, 2).unwrap();
156        assert!(!is_path(&g).unwrap());
157    }
158
159    #[test]
160    fn two_isolated_vertices_not_path() {
161        let g = Graph::with_vertices(2);
162        assert!(!is_path(&g).unwrap());
163    }
164
165    #[test]
166    fn path_non_sequential_edges() {
167        // Path but edges added in non-order: 3-1, 1-0, 0-2
168        let mut g = Graph::with_vertices(4);
169        g.add_edge(3, 1).unwrap();
170        g.add_edge(1, 0).unwrap();
171        g.add_edge(0, 2).unwrap();
172        assert!(is_path(&g).unwrap());
173    }
174}
rust_igraph/algorithms/properties/is_path.rs

rust_igraph/algorithms/properties/
is_path.rs
