rust_igraph/algorithms/properties/
is_proper_interval.rs

1//! Proper interval graph predicate (ALGO-PR-115).
2//!
3//! A graph is a proper interval graph (equivalently, unit interval
4//! graph) if it can be represented as an intersection graph of
5//! intervals on the real line where no interval properly contains
6//! another. This is equivalent to being both an interval graph and
7//! claw-free, or equivalently chordal + claw-free + AT-free.
8//!
9//! A simpler characterization: a graph is a proper interval graph iff
10//! it is chordal and does not contain an induced claw (`K_{1,3}`) and
11//! admits a vertex ordering where the closed neighborhoods are
12//! consecutive (consecutive-1's property in the augmented adjacency
13//! matrix). We use the characterization: proper interval ⟺ chordal +
14//! claw-free (Roberts 1969 / Wegner 1967).
15//!
16//! Returns `false` for directed graphs.
17
18use crate::algorithms::chordality::is_chordal;
19use crate::algorithms::properties::is_claw_free::is_claw_free;
20use crate::core::{Graph, IgraphResult};
21
22/// Check whether a graph is a proper interval graph.
23///
24/// A proper interval graph is chordal and claw-free. Equivalently,
25/// it can be represented by unit-length intervals on the real line.
26///
27/// Returns `false` for directed graphs.
28///
29/// # Examples
30///
31/// ```
32/// use rust_igraph::{Graph, is_proper_interval};
33///
34/// // Path `P_4` is a proper interval graph
35/// let mut g = Graph::with_vertices(4);
36/// g.add_edge(0, 1).unwrap();
37/// g.add_edge(1, 2).unwrap();
38/// g.add_edge(2, 3).unwrap();
39/// assert!(is_proper_interval(&g).unwrap());
40///
41/// // Star `S_3` is NOT proper interval (has a claw)
42/// let mut g = Graph::with_vertices(4);
43/// g.add_edge(0, 1).unwrap();
44/// g.add_edge(0, 2).unwrap();
45/// g.add_edge(0, 3).unwrap();
46/// assert!(!is_proper_interval(&g).unwrap());
47/// ```
48pub fn is_proper_interval(graph: &Graph) -> IgraphResult<bool> {
49    if graph.is_directed() {
50        return Ok(false);
51    }
52
53    let ch = is_chordal(graph, None)?;
54    if !ch.chordal {
55        return Ok(false);
56    }
57
58    is_claw_free(graph)
59}
60
61#[cfg(test)]
62mod tests {
63    use super::*;
64
65    #[test]
66    fn empty_graph() {
67        let g = Graph::with_vertices(0);
68        assert!(is_proper_interval(&g).unwrap());
69    }
70
71    #[test]
72    fn single_vertex() {
73        let g = Graph::with_vertices(1);
74        assert!(is_proper_interval(&g).unwrap());
75    }
76
77    #[test]
78    fn single_edge() {
79        let mut g = Graph::with_vertices(2);
80        g.add_edge(0, 1).unwrap();
81        assert!(is_proper_interval(&g).unwrap());
82    }
83
84    #[test]
85    fn triangle() {
86        let mut g = Graph::with_vertices(3);
87        g.add_edge(0, 1).unwrap();
88        g.add_edge(1, 2).unwrap();
89        g.add_edge(2, 0).unwrap();
90        assert!(is_proper_interval(&g).unwrap());
91    }
92
93    #[test]
94    fn path_p4() {
95        // P_4: 0-1-2-3. Chordal (no induced C_4+), claw-free (max degree 2).
96        let mut g = Graph::with_vertices(4);
97        g.add_edge(0, 1).unwrap();
98        g.add_edge(1, 2).unwrap();
99        g.add_edge(2, 3).unwrap();
100        assert!(is_proper_interval(&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_proper_interval(&g).unwrap());
111    }
112
113    #[test]
114    fn complete_k4() {
115        let mut g = Graph::with_vertices(4);
116        for i in 0..4u32 {
117            for j in (i + 1)..4 {
118                g.add_edge(i, j).unwrap();
119            }
120        }
121        assert!(is_proper_interval(&g).unwrap());
122    }
123
124    #[test]
125    fn star_not_proper_interval() {
126        // Star S_3: has claw K_{1,3} → NOT proper interval
127        let mut g = Graph::with_vertices(4);
128        g.add_edge(0, 1).unwrap();
129        g.add_edge(0, 2).unwrap();
130        g.add_edge(0, 3).unwrap();
131        assert!(!is_proper_interval(&g).unwrap());
132    }
133
134    #[test]
135    fn c4_not_proper_interval() {
136        // C_4: not chordal → NOT proper interval
137        let mut g = Graph::with_vertices(4);
138        g.add_edge(0, 1).unwrap();
139        g.add_edge(1, 2).unwrap();
140        g.add_edge(2, 3).unwrap();
141        g.add_edge(3, 0).unwrap();
142        assert!(!is_proper_interval(&g).unwrap());
143    }
144
145    #[test]
146    fn c5_not_proper_interval() {
147        // C_5: not chordal → NOT proper interval
148        let mut g = Graph::with_vertices(5);
149        g.add_edge(0, 1).unwrap();
150        g.add_edge(1, 2).unwrap();
151        g.add_edge(2, 3).unwrap();
152        g.add_edge(3, 4).unwrap();
153        g.add_edge(4, 0).unwrap();
154        assert!(!is_proper_interval(&g).unwrap());
155    }
156
157    #[test]
158    fn diamond() {
159        // Diamond: K_4 minus one edge. Chordal, max degree 3 but no
160        // induced claw (the degree-3 vertices have two mutual neighbors).
161        let mut g = Graph::with_vertices(4);
162        g.add_edge(0, 1).unwrap();
163        g.add_edge(0, 2).unwrap();
164        g.add_edge(0, 3).unwrap();
165        g.add_edge(1, 2).unwrap();
166        g.add_edge(1, 3).unwrap();
167        // missing 2-3
168        assert!(is_proper_interval(&g).unwrap());
169    }
170
171    #[test]
172    fn edgeless() {
173        let g = Graph::with_vertices(4);
174        assert!(is_proper_interval(&g).unwrap());
175    }
176
177    #[test]
178    fn sun_3_not_proper_interval() {
179        // Sun S_3: chordal but has a claw (outer vertex + 2 inner nbrs +
180        // another outer vertex). Actually let's check: outer vertex 3 has
181        // neighbors 0,1. Degree 2, can't form claw from 3.
182        // Inner vertex 0 has neighbors 1,2,3,5 (degree 4). Check if 0
183        // has 3 independent neighbors: 3 adj to 1 ✓, 5 adj to 2 ✓,
184        // 3 adj to 5? No edge → 3,2,5 independent? 2 adj 5 ✓ → not independent.
185        // Actually: N(0) = {1, 2, 5, 3}. Are {1,5,3} independent?
186        // 1-5? No. 1-3? Yes (edge). So {1,3} not independent.
187        // {2,5,3}: 2-5? Yes. Not independent.
188        // This might not have a claw. Sun_3 is chordal but not strongly
189        // chordal. It IS interval and proper interval depends on claw-free.
190        // Let me use a different example.
191        // Tree with branching: 0-1, 0-2, 0-3, 1-4 → claw at 0 (leaves 2,3
192        // and 1 independent). Chordal (tree). Has claw → NOT proper interval.
193        let mut g = Graph::with_vertices(5);
194        g.add_edge(0, 1).unwrap();
195        g.add_edge(0, 2).unwrap();
196        g.add_edge(0, 3).unwrap();
197        g.add_edge(1, 4).unwrap();
198        assert!(!is_proper_interval(&g).unwrap());
199    }
200
201    #[test]
202    fn caterpillar_with_claw() {
203        // 0-1-2-3, 1-4, 1-5. Vertex 1 has neighbors {0,2,4,5}.
204        // {0,4,5} pairwise non-adjacent → claw at 1 → NOT proper interval.
205        let mut g = Graph::with_vertices(6);
206        g.add_edge(0, 1).unwrap();
207        g.add_edge(1, 2).unwrap();
208        g.add_edge(2, 3).unwrap();
209        g.add_edge(1, 4).unwrap();
210        g.add_edge(1, 5).unwrap();
211        assert!(!is_proper_interval(&g).unwrap());
212    }
213
214    #[test]
215    fn directed_returns_false() {
216        let mut g = Graph::new(3, true).unwrap();
217        g.add_edge(0, 1).unwrap();
218        g.add_edge(1, 2).unwrap();
219        g.add_edge(2, 0).unwrap();
220        assert!(!is_proper_interval(&g).unwrap());
221    }
222}
rust_igraph/algorithms/properties/is_proper_interval.rs

rust_igraph/algorithms/properties/
is_proper_interval.rs
