rust_igraph/algorithms/properties/
is_ptolemaic.rs

1//! Ptolemaic graph predicate (ALGO-PR-081).
2//!
3//! A ptolemaic graph is a graph that is both chordal and
4//! distance-hereditary.  Equivalently, it is a gem-free chordal
5//! graph, or a graph whose every metric subspace satisfies the
6//! Ptolemy inequality.
7//!
8//! Ptolemaic graphs are exactly the block graphs (also known as
9//! clique trees).  Every tree and every complete graph is ptolemaic.
10//!
11//! For directed graphs, the function returns `false`.
12
13use crate::algorithms::chordality::is_chordal;
14use crate::algorithms::properties::is_distance_hereditary::is_distance_hereditary;
15use crate::core::{Graph, IgraphResult};
16
17/// Check whether a graph is ptolemaic.
18///
19/// A ptolemaic graph is both chordal and distance-hereditary.
20///
21/// Returns `false` for directed graphs.
22///
23/// An empty graph (0 vertices) is ptolemaic (vacuously).
24/// A single vertex is ptolemaic.
25/// Any tree is ptolemaic.
26/// Any complete graph is ptolemaic.
27/// Any block graph is ptolemaic.
28///
29/// # Examples
30///
31/// ```
32/// use rust_igraph::{Graph, is_ptolemaic};
33///
34/// // Tree: ptolemaic
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_ptolemaic(&g).unwrap());
40///
41/// // C4 is NOT ptolemaic (not chordal)
42/// let mut g = Graph::with_vertices(4);
43/// g.add_edge(0, 1).unwrap();
44/// g.add_edge(1, 2).unwrap();
45/// g.add_edge(2, 3).unwrap();
46/// g.add_edge(3, 0).unwrap();
47/// assert!(!is_ptolemaic(&g).unwrap());
48/// ```
49pub fn is_ptolemaic(graph: &Graph) -> IgraphResult<bool> {
50    if graph.is_directed() {
51        return Ok(false);
52    }
53
54    let n = graph.vcount();
55    if n <= 3 {
56        return Ok(true);
57    }
58
59    let chordal_result = is_chordal(graph, None)?;
60    if !chordal_result.chordal {
61        return Ok(false);
62    }
63
64    is_distance_hereditary(graph)
65}
66
67#[cfg(test)]
68mod tests {
69    use super::*;
70
71    #[test]
72    fn empty_graph() {
73        let g = Graph::with_vertices(0);
74        assert!(is_ptolemaic(&g).unwrap());
75    }
76
77    #[test]
78    fn single_vertex() {
79        let g = Graph::with_vertices(1);
80        assert!(is_ptolemaic(&g).unwrap());
81    }
82
83    #[test]
84    fn single_edge() {
85        let mut g = Graph::with_vertices(2);
86        g.add_edge(0, 1).unwrap();
87        assert!(is_ptolemaic(&g).unwrap());
88    }
89
90    #[test]
91    fn triangle_is_ptolemaic() {
92        let mut g = Graph::with_vertices(3);
93        g.add_edge(0, 1).unwrap();
94        g.add_edge(1, 2).unwrap();
95        g.add_edge(2, 0).unwrap();
96        assert!(is_ptolemaic(&g).unwrap());
97    }
98
99    #[test]
100    fn path_is_ptolemaic() {
101        let mut g = Graph::with_vertices(5);
102        g.add_edge(0, 1).unwrap();
103        g.add_edge(1, 2).unwrap();
104        g.add_edge(2, 3).unwrap();
105        g.add_edge(3, 4).unwrap();
106        assert!(is_ptolemaic(&g).unwrap());
107    }
108
109    #[test]
110    fn tree_is_ptolemaic() {
111        let mut g = Graph::with_vertices(7);
112        g.add_edge(0, 1).unwrap();
113        g.add_edge(0, 2).unwrap();
114        g.add_edge(1, 3).unwrap();
115        g.add_edge(1, 4).unwrap();
116        g.add_edge(2, 5).unwrap();
117        g.add_edge(2, 6).unwrap();
118        assert!(is_ptolemaic(&g).unwrap());
119    }
120
121    #[test]
122    fn k4_is_ptolemaic() {
123        let mut g = Graph::with_vertices(4);
124        for u in 0..4u32 {
125            for v in (u + 1)..4 {
126                g.add_edge(u, v).unwrap();
127            }
128        }
129        assert!(is_ptolemaic(&g).unwrap());
130    }
131
132    #[test]
133    fn star_is_ptolemaic() {
134        let mut g = Graph::with_vertices(5);
135        for i in 1..5u32 {
136            g.add_edge(0, i).unwrap();
137        }
138        assert!(is_ptolemaic(&g).unwrap());
139    }
140
141    #[test]
142    fn c4_not_ptolemaic() {
143        // C4: distance-hereditary but not chordal
144        let mut g = Graph::with_vertices(4);
145        g.add_edge(0, 1).unwrap();
146        g.add_edge(1, 2).unwrap();
147        g.add_edge(2, 3).unwrap();
148        g.add_edge(3, 0).unwrap();
149        assert!(!is_ptolemaic(&g).unwrap());
150    }
151
152    #[test]
153    fn c5_not_ptolemaic() {
154        // C5: neither chordal nor distance-hereditary
155        let mut g = Graph::with_vertices(5);
156        g.add_edge(0, 1).unwrap();
157        g.add_edge(1, 2).unwrap();
158        g.add_edge(2, 3).unwrap();
159        g.add_edge(3, 4).unwrap();
160        g.add_edge(4, 0).unwrap();
161        assert!(!is_ptolemaic(&g).unwrap());
162    }
163
164    #[test]
165    fn two_triangles_sharing_vertex_is_ptolemaic() {
166        // Block graph: two K3 sharing vertex 2 → ptolemaic
167        let mut g = Graph::with_vertices(5);
168        g.add_edge(0, 1).unwrap();
169        g.add_edge(1, 2).unwrap();
170        g.add_edge(2, 0).unwrap();
171        g.add_edge(2, 3).unwrap();
172        g.add_edge(3, 4).unwrap();
173        g.add_edge(4, 2).unwrap();
174        assert!(is_ptolemaic(&g).unwrap());
175    }
176
177    #[test]
178    fn gem_not_ptolemaic() {
179        // Gem = fan(1,4): chordal but not distance-hereditary
180        let mut g = Graph::with_vertices(5);
181        g.add_edge(0, 1).unwrap();
182        g.add_edge(1, 2).unwrap();
183        g.add_edge(2, 3).unwrap();
184        g.add_edge(4, 0).unwrap();
185        g.add_edge(4, 1).unwrap();
186        g.add_edge(4, 2).unwrap();
187        g.add_edge(4, 3).unwrap();
188        assert!(!is_ptolemaic(&g).unwrap());
189    }
190
191    #[test]
192    fn house_not_ptolemaic() {
193        // House: not chordal (contains C4)
194        let mut g = Graph::with_vertices(5);
195        g.add_edge(0, 1).unwrap();
196        g.add_edge(1, 2).unwrap();
197        g.add_edge(2, 3).unwrap();
198        g.add_edge(3, 0).unwrap();
199        g.add_edge(2, 4).unwrap();
200        g.add_edge(3, 4).unwrap();
201        assert!(!is_ptolemaic(&g).unwrap());
202    }
203
204    #[test]
205    fn edgeless_is_ptolemaic() {
206        let g = Graph::with_vertices(5);
207        assert!(is_ptolemaic(&g).unwrap());
208    }
209
210    #[test]
211    fn disconnected_trees_ptolemaic() {
212        let mut g = Graph::with_vertices(6);
213        g.add_edge(0, 1).unwrap();
214        g.add_edge(1, 2).unwrap();
215        g.add_edge(3, 4).unwrap();
216        g.add_edge(4, 5).unwrap();
217        assert!(is_ptolemaic(&g).unwrap());
218    }
219
220    #[test]
221    fn directed_returns_false() {
222        let mut g = Graph::new(3, true).unwrap();
223        g.add_edge(0, 1).unwrap();
224        g.add_edge(1, 2).unwrap();
225        assert!(!is_ptolemaic(&g).unwrap());
226    }
227
228    #[test]
229    fn diamond_chordal_but_not_dh() {
230        // Diamond (K4 minus one edge): chordal? Let's check.
231        // K4 minus edge (2,3): 0-1, 0-2, 0-3, 1-2, 1-3
232        // Cycles: 0-1-2-0 (triangle), 0-1-3-0 (triangle), 0-2-1-3-0 (C4 with chord 0-1)
233        // Chordal: yes (all cycles of length >= 4 have chord 0-1)
234        // Distance-hereditary: is it? K4-e is house-free...
235        // Actually the diamond IS distance-hereditary (it's a block graph)
236        let mut g = Graph::with_vertices(4);
237        g.add_edge(0, 1).unwrap();
238        g.add_edge(0, 2).unwrap();
239        g.add_edge(0, 3).unwrap();
240        g.add_edge(1, 2).unwrap();
241        g.add_edge(1, 3).unwrap();
242        assert!(is_ptolemaic(&g).unwrap());
243    }
244}
rust_igraph/algorithms/properties/is_ptolemaic.rs

rust_igraph/algorithms/properties/
is_ptolemaic.rs
