flag_algebra/flags/
graph.rs

1//! Undirected graphs and their implementation of `Flag`.
2
3use crate::combinatorics;
4use crate::flag::{Flag, SubFlag};
5use crate::flags::common::*;
6use crate::iterators;
7use crate::iterators::StreamingIterator;
8use canonical_form::Canonize;
9use std::fmt;
10
11/// Undirected graphs.
12///
13/// Implementation of graphs by upper triangular adjacency matrix,
14/// reprensented as a boolean vector of length `n` choose `2`.
15#[derive(PartialEq, Eq, PartialOrd, Ord, Debug, Clone, Serialize, Deserialize)]
16pub struct Graph {
17    size: usize,
18    edge: SymNonRefl<bool>,
19}
20
21#[derive(Debug, Clone)]
22struct EdgeIterator<'a> {
23    g: &'a Graph,
24    u: usize,
25    v: usize,
26}
27
28impl<'a> Iterator for EdgeIterator<'a> {
29    type Item = (usize, usize);
30
31    fn next(&mut self) -> Option<Self::Item> {
32        self.u += 1;
33        if self.u >= self.v {
34            self.u = 0;
35            self.v += 1;
36        }
37        debug_assert!(self.u < self.v);
38        if self.v >= self.g.size {
39            None
40        } else if self.g.edge(self.u, self.v) {
41            Some((self.u, self.v))
42        } else {
43            self.next()
44        }
45    }
46}
47
48impl Graph {
49    /// Create a graph on `n` vertices with edge set `edge`.
50    /// The vertices of this graph are `0,...,n-1`.
51    pub fn new(n: usize, edge: &[(usize, usize)]) -> Self {
52        let mut new_edge = SymNonRefl::new(false, n);
53        for &(u, v) in edge {
54            assert!(u < n);
55            assert!(v < n);
56            new_edge[(u, v)] = true;
57        }
58        Self {
59            size: n,
60            edge: new_edge,
61        }
62    }
63    /// Return the number of vertices in the graph
64    pub fn size(&self) -> usize {
65        self.size
66    }
67
68    /// Return the vector of vertices adjacent to `v`.
69    pub fn nbrs(&self, v: usize) -> Vec<usize> {
70        let mut res = Vec::new();
71        for u in 0..self.size {
72            if u != v && self.edge.get(u, v) {
73                res.push(u);
74            }
75        }
76        res
77    }
78
79    /// Create the graph on `n` vertices with no edge.  
80    pub fn empty(n: usize) -> Self {
81        Self {
82            size: n,
83            edge: SymNonRefl::new(false, n),
84        }
85    }
86
87    /// Returns `true` id `uv` is an edge.
88    #[inline]
89    pub fn edge(&self, u: usize, v: usize) -> bool {
90        u != v && self.edge[(u, v)]
91    }
92    /// Returns an iterator on edges.
93    /// The edges are represented as couples `(u, v)` with `u < v`.
94    pub fn edges(&self) -> impl Iterator<Item = (usize, usize)> + '_ {
95        EdgeIterator {
96            g: self,
97            u: 0,
98            v: 0,
99        }
100    }
101
102    /// Returns `true` if the graph is connected.
103    pub fn connected(&self) -> bool {
104        let mut visited = vec![false; self.size];
105        let mut stack = vec![0];
106        while let Some(v) = stack.pop() {
107            if !visited[v] {
108                visited[v] = true;
109                stack.append(&mut self.nbrs(v))
110            }
111        }
112        visited.into_iter().all(|b| b)
113    }
114}
115
116impl fmt::Display for Graph {
117    fn fmt(&self, f: &mut fmt::Formatter) -> fmt::Result {
118        write!(f, "(V=[{}], E={{", self.size)?;
119        for u in 0..self.size {
120            for v in 0..u {
121                if self.edge[(u, v)] {
122                    if self.size < 10 {
123                        write!(f, " {v}{u}")?
124                    } else {
125                        write!(f, " {v}-{u}")?
126                    }
127                }
128            }
129        }
130        write!(f, " }})")
131    }
132}
133
134impl Canonize for Graph {
135    fn size(&self) -> usize {
136        self.size
137    }
138    fn invariant_neighborhood(&self, v: usize) -> Vec<Vec<usize>> {
139        assert!(v < self.size);
140        vec![self.nbrs(v)]
141    }
142    fn apply_morphism(&self, p: &[usize]) -> Self {
143        self.induce(&combinatorics::invert(p))
144    }
145}
146
147impl Flag for Graph {
148    fn induce(&self, p: &[usize]) -> Self {
149        debug_assert!(p.iter().all(|&i| { i < self.size }));
150        let k = p.len();
151        let mut res = Self::empty(k);
152        for u1 in 0..k {
153            for u2 in 0..u1 {
154                res.edge[(u1, u2)] = self.edge[(p[u1], p[u2])];
155            }
156        }
157        res
158    }
159
160    const NAME: &'static str = "Graph";
161
162    fn size_zero_flags() -> Vec<Self> {
163        vec![Self::empty(0)]
164    }
165
166    fn superflags(&self) -> Vec<Self> {
167        let n = self.size;
168        let mut res = Vec::new();
169        let mut iter = iterators::Subsets::new(n);
170        while let Some(subset) = iter.next() {
171            let mut edge = self.edge.clone();
172            edge.resize(n + 1, false);
173            for &v in subset {
174                edge[(v, n)] = true;
175            }
176            res.push(Self { edge, size: n + 1 });
177        }
178        res
179    }
180}
181
182// particular graphs
183impl Graph {
184    pub fn petersen() -> Self {
185        Self::new(
186            10,
187            &[
188                (0, 1),
189                (1, 2),
190                (2, 3),
191                (3, 4),
192                (4, 0),
193                (5, 7),
194                (6, 8),
195                (7, 9),
196                (8, 5),
197                (9, 6),
198                (0, 5),
199                (1, 6),
200                (2, 7),
201                (3, 8),
202                (4, 9),
203            ],
204        )
205    }
206    pub fn clique(n: usize) -> Self {
207        let mut edges = Vec::new();
208        for i in 0..n {
209            for j in 0..i {
210                edges.push((i, j))
211            }
212        }
213        Self::new(n, &edges)
214    }
215    pub fn cycle(n: usize) -> Self {
216        let mut edges: Vec<_> = (0..n - 1).map(|i| (i, i + 1)).collect();
217        edges.push((n - 1, 0));
218        Self::new(n, &edges)
219    }
220}
221
222/// Connected graphs
223#[derive(Debug, Clone, Copy)]
224pub enum Connected {}
225
226impl SubFlag<Graph> for Connected {
227    const SUBCLASS_NAME: &'static str = "Connected graph";
228
229    const HEREDITARY: bool = false;
230
231    fn is_in_subclass(flag: &Graph) -> bool {
232        flag.connected()
233    }
234}
235
236/// Tests
237#[cfg(test)]
238mod tests {
239    use super::*;
240
241    #[test]
242    fn new_unit() {
243        let g = Graph::new(5, &[(0, 1), (1, 2), (2, 3), (3, 4), (4, 0)]);
244        let h = Graph::new(5, &[(3, 2), (1, 2), (3, 4), (0, 4), (1, 0)]);
245        assert_eq!(g, h);
246    }
247    #[test]
248    fn edge_iterator() {
249        let g = Graph::new(5, &[(0, 1), (1, 2), (0, 4), (2, 3), (3, 4)]);
250        assert_eq!(g.edges().count(), 5);
251        let k3 = Graph::new(5, &[(0, 1), (1, 2), (2, 3)]);
252        assert_eq!(k3.edges().count(), 3);
253        let e6 = Graph::new(6, &[]);
254        assert_eq!(e6.edges().count(), 0);
255    }
256}
flag_algebra/flags/graph.rs

flag_algebra/flags/
graph.rs
