rust_igraph/algorithms/properties/
is_semicomplete.rs

1//! Semicomplete digraph predicate (ALGO-PR-095).
2//!
3//! A semicomplete digraph is a directed graph where for every pair of
4//! distinct vertices u and v, at least one of the arcs (u,v) or (v,u)
5//! exists (possibly both). Tournaments are the special case where
6//! exactly one arc exists per pair.
7//!
8//! For undirected graphs, the function returns `false` (use
9//! `is_complete` instead).
10
11use crate::core::{Graph, IgraphResult};
12
13/// Check whether a directed graph is semicomplete.
14///
15/// A semicomplete digraph has at least one arc between every pair
16/// of distinct vertices. This generalizes tournaments (which forbid
17/// bidirectional edges).
18///
19/// Returns `false` for undirected graphs.
20///
21/// # Examples
22///
23/// ```
24/// use rust_igraph::{Graph, is_semicomplete};
25///
26/// // Tournament on 3 vertices: 0→1, 1→2, 0→2
27/// let mut g = Graph::new(3, true).unwrap();
28/// g.add_edge(0, 1).unwrap();
29/// g.add_edge(1, 2).unwrap();
30/// g.add_edge(0, 2).unwrap();
31/// assert!(is_semicomplete(&g).unwrap());
32///
33/// // Missing arc between 0 and 2
34/// let mut g = Graph::new(3, true).unwrap();
35/// g.add_edge(0, 1).unwrap();
36/// g.add_edge(1, 2).unwrap();
37/// assert!(!is_semicomplete(&g).unwrap());
38/// ```
39pub fn is_semicomplete(graph: &Graph) -> IgraphResult<bool> {
40    if !graph.is_directed() {
41        return Ok(false);
42    }
43
44    let n = graph.vcount();
45    if n <= 1 {
46        return Ok(true);
47    }
48
49    // Build adjacency matrix for fast pair lookup
50    let n_usize = n as usize;
51    let mut has_arc = vec![vec![false; n_usize]; n_usize];
52
53    for v in 0..n {
54        let nbrs = graph.neighbors(v)?;
55        for &w in &nbrs {
56            has_arc[v as usize][w as usize] = true;
57        }
58    }
59
60    // Check every pair
61    for (u, row_u) in has_arc.iter().enumerate().take(n_usize) {
62        for (v, &u_to_v) in row_u.iter().enumerate().take(n_usize).skip(u + 1) {
63            if !u_to_v && !has_arc[v][u] {
64                return Ok(false);
65            }
66        }
67    }
68
69    Ok(true)
70}
71
72#[cfg(test)]
73mod tests {
74    use super::*;
75
76    #[test]
77    fn empty_graph() {
78        let g = Graph::new(0, true).unwrap();
79        assert!(is_semicomplete(&g).unwrap());
80    }
81
82    #[test]
83    fn single_vertex() {
84        let g = Graph::new(1, true).unwrap();
85        assert!(is_semicomplete(&g).unwrap());
86    }
87
88    #[test]
89    fn tournament_3() {
90        let mut g = Graph::new(3, true).unwrap();
91        g.add_edge(0, 1).unwrap();
92        g.add_edge(1, 2).unwrap();
93        g.add_edge(0, 2).unwrap();
94        assert!(is_semicomplete(&g).unwrap());
95    }
96
97    #[test]
98    fn bidirectional_pair() {
99        let mut g = Graph::new(2, true).unwrap();
100        g.add_edge(0, 1).unwrap();
101        g.add_edge(1, 0).unwrap();
102        assert!(is_semicomplete(&g).unwrap());
103    }
104
105    #[test]
106    fn semicomplete_not_tournament() {
107        // All arcs present (complete digraph = semicomplete)
108        let mut g = Graph::new(3, true).unwrap();
109        g.add_edge(0, 1).unwrap();
110        g.add_edge(1, 0).unwrap();
111        g.add_edge(0, 2).unwrap();
112        g.add_edge(2, 0).unwrap();
113        g.add_edge(1, 2).unwrap();
114        g.add_edge(2, 1).unwrap();
115        assert!(is_semicomplete(&g).unwrap());
116    }
117
118    #[test]
119    fn missing_arc() {
120        let mut g = Graph::new(3, true).unwrap();
121        g.add_edge(0, 1).unwrap();
122        g.add_edge(1, 2).unwrap();
123        // Missing: no arc between 0 and 2
124        assert!(!is_semicomplete(&g).unwrap());
125    }
126
127    #[test]
128    fn undirected_returns_false() {
129        let mut g = Graph::with_vertices(3);
130        g.add_edge(0, 1).unwrap();
131        g.add_edge(1, 2).unwrap();
132        g.add_edge(2, 0).unwrap();
133        assert!(!is_semicomplete(&g).unwrap());
134    }
135
136    #[test]
137    fn single_arc() {
138        let mut g = Graph::new(2, true).unwrap();
139        g.add_edge(0, 1).unwrap();
140        assert!(is_semicomplete(&g).unwrap());
141    }
142
143    #[test]
144    fn four_vertex_tournament() {
145        let mut g = Graph::new(4, true).unwrap();
146        g.add_edge(0, 1).unwrap();
147        g.add_edge(0, 2).unwrap();
148        g.add_edge(0, 3).unwrap();
149        g.add_edge(1, 2).unwrap();
150        g.add_edge(1, 3).unwrap();
151        g.add_edge(2, 3).unwrap();
152        assert!(is_semicomplete(&g).unwrap());
153    }
154
155    #[test]
156    fn four_vertex_not_semicomplete() {
157        let mut g = Graph::new(4, true).unwrap();
158        g.add_edge(0, 1).unwrap();
159        g.add_edge(1, 2).unwrap();
160        g.add_edge(2, 3).unwrap();
161        // Path: missing arcs between non-consecutive vertices
162        assert!(!is_semicomplete(&g).unwrap());
163    }
164
165    #[test]
166    fn no_edges() {
167        let g = Graph::new(3, true).unwrap();
168        assert!(!is_semicomplete(&g).unwrap());
169    }
170
171    #[test]
172    fn self_loops_dont_help() {
173        let mut g = Graph::new(2, true).unwrap();
174        g.add_edge(0, 0).unwrap();
175        g.add_edge(1, 1).unwrap();
176        // Self-loops don't satisfy the pair requirement
177        assert!(!is_semicomplete(&g).unwrap());
178    }
179}
rust_igraph/algorithms/properties/is_semicomplete.rs

rust_igraph/algorithms/properties/
is_semicomplete.rs
