flag_algebra/flags/
digraph.rs

1//! `[OrientedGraph]`s and their flag implementation.
2use crate::combinatorics;
3use crate::flag::{Flag, SubClass, SubFlag};
4use crate::flags::common::*;
5use crate::iterators::{Functions, StreamingIterator};
6use canonical_form::Canonize;
7use std::fmt;
8use std::ops::Neg;
9
10#[derive(PartialEq, Eq, PartialOrd, Ord, Debug, Clone, Copy, Serialize, Deserialize)]
11/// The arc between two nodes of a directed graphs.
12#[derive(Default)]
13pub enum Arc {
14    /// No arc.
15    #[default]
16    None,
17    /// Arc from the first to the second vertex considered.
18    Edge,
19    /// Arc from the second to the first vertex considered.
20    BackEdge,
21    /// Arcs in both directions
22    Reciprocal,
23}
24
25impl Neg for Arc {
26    type Output = Self;
27
28    fn neg(self) -> Self {
29        match self {
30            Edge => BackEdge,
31            BackEdge => Edge,
32            e => e,
33        }
34    }
35}
36
37use Arc::*;
38
39#[derive(PartialEq, Eq, PartialOrd, Ord, Debug, Clone, Serialize, Deserialize)]
40/// Loopless directed graphs.
41///
42/// The possible relations between two vertices is described by the type [`Arc`].
43pub struct DirectedGraph {
44    /// Number of vertices.
45    size: usize,
46    /// Flat matrix of arcs.
47    edge: AntiSym<Arc>,
48}
49
50impl DirectedGraph {
51    /// Create a directed graph with `n` vertices and arcs in `arcs`.
52    ///
53    /// # Panics
54    /// * If `arcs` contains vertices not in `{0, ..., n-1}`
55    /// * If a loop `(u, u)` is provided
56    /// * If some arc is provided twice
57    /// ```
58    /// use flag_algebra::flags::OrientedGraph;
59    ///
60    /// // Oriented path with 3 vertices `0 -> 1 -> 2`
61    /// let p3 = OrientedGraph::new(3, [(0, 1), (1, 2)]);
62    /// ```
63    pub fn new<I>(n: usize, arcs: I) -> Self
64    where
65        I: IntoIterator<Item = (usize, usize)>,
66    {
67        let mut new_edge = AntiSym::new(None, n);
68        for (u, v) in arcs {
69            check_arc((u, v), n);
70            let new_arc = match new_edge.get(u, v) {
71                None => Edge,
72                BackEdge => Reciprocal,
73                _ => panic!("Arc ({u}, {v}) specified twice"),
74            };
75            new_edge.set((u, v), new_arc);
76        }
77        Self {
78            size: n,
79            edge: new_edge,
80        }
81    }
82    /// Number of vertices
83    pub fn size(&self) -> usize {
84        self.size
85    }
86    /// Out-neigborhood of `v`.
87    /// ```
88    /// use flag_algebra::flags::OrientedGraph;
89    /// let p3 = OrientedGraph::new(3, [(0,1), (1,2)]);
90    /// assert_eq!(p3.out_nbrs(1), vec![2]);
91    /// ```
92    pub fn out_nbrs(&self, v: usize) -> Vec<usize> {
93        let mut res = Vec::new();
94        for u in 0..self.size {
95            if u != v && matches!(self.edge.get(u, v), BackEdge | Reciprocal) {
96                res.push(u);
97            }
98        }
99        res
100    }
101    /// In-neigborhood of `v`.
102    /// ```
103    /// use flag_algebra::flags::OrientedGraph;
104    /// let p3 = OrientedGraph::new(3, [(0, 1), (1, 2)]);
105    /// assert_eq!(p3.in_nbrs(1), vec![0]);
106    /// ```
107    pub fn in_nbrs(&self, v: usize) -> Vec<usize> {
108        let mut res = Vec::new();
109        for u in 0..self.size {
110            if u != v && matches!(self.edge.get(u, v), Edge | Reciprocal) {
111                res.push(u);
112            }
113        }
114        res
115    }
116    /// Oriented relation between `u` to `v`.
117    /// ```
118    /// use flag_algebra::flags::{DirectedGraph, Arc};
119    /// let g = DirectedGraph::new(3, [(0, 1), (1, 2), (2, 1)]);
120    /// assert_eq!(g.arc(0, 1), Arc::Edge);
121    /// assert_eq!(g.arc(1, 0), Arc::BackEdge);
122    /// assert_eq!(g.arc(0, 2), Arc::None);
123    /// assert_eq!(g.arc(1, 2), Arc::Reciprocal);
124    /// ```
125    pub fn arc(&self, u: usize, v: usize) -> Arc {
126        check_arc((u, v), self.size);
127        self.edge.get(u, v)
128    }
129}
130
131#[derive(PartialEq, Eq, PartialOrd, Ord, Debug, Clone, Serialize, Deserialize)]
132/// Loopless oriented graphs.
133///
134/// Every pair of vertices has at most one edge.
135pub struct OrientedGraph(DirectedGraph);
136
137impl OrientedGraph {
138    pub fn as_directed(&self) -> &DirectedGraph {
139        &self.0
140    }
141    /// Create an oriented graph with `n` vertices and arcs in `arcs`.
142    ///
143    /// # Panics
144    /// * If `arcs` contains vertices not in `{0, ..., n-1}`
145    /// * If a loop `(u, u)` is provided
146    /// * If some arc is provided twice
147    /// * If both arcs `(u, v)` and `(v, u)` are provided
148    /// ```
149    /// use flag_algebra::flags::OrientedGraph;
150    ///
151    /// // Oriented path with 3 vertices `0 -> 1 -> 2`
152    /// let p3 = OrientedGraph::new(3, [(0, 1), (1, 2)]);
153    /// ```
154    pub fn new<I>(n: usize, arcs: I) -> Self
155    where
156        I: IntoIterator<Item = (usize, usize)>,
157    {
158        let mut new_edge = AntiSym::new(None, n);
159        for (u, v) in arcs {
160            check_arc((u, v), n);
161            assert!(
162                new_edge.get(u, v) == None,
163                "Pair {{{u}, {v}}} specified twice"
164            );
165            new_edge.set((u, v), Edge);
166        }
167        Self(DirectedGraph {
168            size: n,
169            edge: new_edge,
170        })
171    }
172    /// Oriented graph with `n` vertices and no edge.
173    /// ```
174    /// use flag_algebra::flags::OrientedGraph;
175    /// assert_eq!(OrientedGraph::empty(4), OrientedGraph::new(4, []));
176    /// ```
177    pub fn empty(n: usize) -> Self {
178        Self::new(n, [])
179    }
180    /// Number of vertices
181    pub fn size(&self) -> usize {
182        self.0.size()
183    }
184    /// Out-neigborhood of `v`.
185    /// ```
186    /// use flag_algebra::flags::OrientedGraph;
187    /// let p3 = OrientedGraph::new(3, [(0,1), (1,2)]);
188    /// assert_eq!(p3.out_nbrs(1), vec![2]);
189    /// ```
190    pub fn out_nbrs(&self, v: usize) -> Vec<usize> {
191        self.0.out_nbrs(v)
192    }
193    /// In-neigborhood of `v`.
194    /// ```
195    /// use flag_algebra::flags::OrientedGraph;
196    /// let p3 = OrientedGraph::new(3, [(0,1), (1,2)]);
197    /// assert_eq!(p3.in_nbrs(1), vec![0]);
198    /// ```
199    pub fn in_nbrs(&self, v: usize) -> Vec<usize> {
200        self.0.in_nbrs(v)
201    }
202    /// Oriented relation between `u` to `v`.
203    /// ```
204    /// use flag_algebra::flags::{OrientedGraph, Arc};
205    /// let p3 = OrientedGraph::new(3, [(0,1), (1,2)]);
206    /// assert_eq!(p3.arc(0, 1), Arc::Edge);
207    /// assert_eq!(p3.arc(1, 0), Arc::BackEdge);
208    /// assert_eq!(p3.arc(0, 2), Arc::None);
209    /// ```
210    pub fn arc(&self, u: usize, v: usize) -> Arc {
211        self.0.arc(u, v)
212    }
213    fn is_triangle_free(&self) -> bool {
214        for u in 0..self.size() {
215            // Assume u is the largest vertex
216            for v in 0..u {
217                if self.arc(v, u) == Edge {
218                    for w in 0..u {
219                        if self.arc(u, w) == Edge && self.arc(w, v) == Edge {
220                            return false;
221                        }
222                    }
223                }
224            }
225        }
226        true
227    }
228
229    /// Oriented graph obtained from `self` by adding a vertex and every edge
230    /// from the rest of the graph to that vertex.
231    pub fn add_sink(&self) -> Self {
232        let n = self.size();
233        let mut edge = self.0.edge.clone();
234        edge.resize(n + 1, None);
235        for v in 0..n {
236            edge.set((v, n), Edge);
237        }
238        Self(DirectedGraph { edge, size: n + 1 })
239    }
240}
241
242impl fmt::Display for DirectedGraph {
243    fn fmt(&self, f: &mut fmt::Formatter) -> fmt::Result {
244        write!(f, "(V=[{}], E={{", self.size)?;
245        for u in 0..self.size {
246            for v in 0..self.size {
247                if v != u {
248                    match self.edge.get(u, v) {
249                        Edge => write!(f, " {u}->{v}")?,
250                        Reciprocal if u < v => write!(f, " {u}<->{v}")?,
251                        _ => (),
252                    }
253                }
254            }
255        }
256        write!(f, " }})")
257    }
258}
259
260impl fmt::Display for OrientedGraph {
261    fn fmt(&self, f: &mut fmt::Formatter) -> fmt::Result {
262        self.0.fmt(f)
263    }
264}
265
266fn check_vertex(u: usize, graph_size: usize) {
267    assert!(
268        u < graph_size,
269        "Invalid vertex {u}: the vertex set is {{0, ..., {}}}",
270        graph_size - 1
271    );
272}
273
274fn check_arc((u, v): (usize, usize), graph_size: usize) {
275    check_vertex(u, graph_size);
276    check_vertex(v, graph_size);
277    assert!(
278        u != v,
279        "Invalid arc ({u}, {v}): OrientedGraphs have no loop"
280    );
281}
282
283impl Canonize for DirectedGraph {
284    fn size(&self) -> usize {
285        self.size
286    }
287    fn invariant_neighborhood(&self, v: usize) -> Vec<Vec<usize>> {
288        assert!(v < self.size);
289        vec![self.out_nbrs(v), self.in_nbrs(v)]
290    }
291    fn apply_morphism(&self, p: &[usize]) -> Self {
292        self.induce(&combinatorics::invert(p))
293    }
294}
295
296impl Canonize for OrientedGraph {
297    fn size(&self) -> usize {
298        self.size()
299    }
300    fn invariant_neighborhood(&self, v: usize) -> Vec<Vec<usize>> {
301        self.0.invariant_neighborhood(v)
302    }
303    fn apply_morphism(&self, p: &[usize]) -> Self {
304        Self(self.0.apply_morphism(p))
305    }
306}
307
308impl Flag for DirectedGraph {
309    fn induce(&self, p: &[usize]) -> Self {
310        let k = p.len();
311        let mut res = Self::new(k, []);
312        for u1 in 0..k {
313            for u2 in 0..u1 {
314                res.edge.set((u1, u2), self.edge.get(p[u1], p[u2]));
315            }
316        }
317        res
318    }
319
320    const NAME: &'static str = "DirectedGraph";
321
322    fn size_zero_flags() -> Vec<Self> {
323        vec![Self::new(0, [])]
324    }
325
326    fn superflags(&self) -> Vec<Self> {
327        let mut res = Vec::new();
328        let mut iter = Functions::new(self.size, 4);
329        let arcs = [Edge, BackEdge, None, Reciprocal];
330        while let Some(f) = iter.next() {
331            res.push(extend(self, |v| arcs[f[v]]));
332        }
333        res
334    }
335}
336
337fn extend<F: Fn(usize) -> Arc>(g: &DirectedGraph, f: F) -> DirectedGraph {
338    let mut edge = g.edge.clone();
339    let n = g.size;
340    edge.resize(n + 1, None);
341    for v in 0..n {
342        edge.set((v, n), f(v));
343    }
344    DirectedGraph { size: n + 1, edge }
345}
346
347impl Flag for OrientedGraph {
348    fn induce(&self, p: &[usize]) -> Self {
349        Self(self.0.induce(p))
350    }
351
352    const NAME: &'static str = "OrientedGraph";
353
354    fn size_zero_flags() -> Vec<Self> {
355        vec![Self::empty(0)]
356    }
357
358    fn superflags(&self) -> Vec<Self> {
359        let mut res = Vec::new();
360        let mut iter = Functions::new(self.size(), 3);
361        let arcs = [Edge, BackEdge, None];
362        while let Some(f) = iter.next() {
363            res.push(Self(extend(&self.0, |v| arcs[f[v]])));
364        }
365        res
366    }
367}
368
369/// Indicator for oriented graph without directed triangle.
370///
371/// Makes `SubClass<OrientedGraph, TriangleFree>` usable as flags.
372#[derive(Debug, Clone, Copy)]
373pub enum TriangleFree {}
374
375impl SubFlag<OrientedGraph> for TriangleFree {
376    const SUBCLASS_NAME: &'static str = "Triangle-free oriented graph";
377
378    fn is_in_subclass(flag: &OrientedGraph) -> bool {
379        flag.is_triangle_free()
380    }
381}
382
383impl<A> SubClass<OrientedGraph, A> {
384    pub fn size(&self) -> usize {
385        self.content.size()
386    }
387}
388
389#[cfg(test)]
390mod tests {
391    use super::*;
392
393    #[test]
394    fn test_display() {
395        let g = DirectedGraph::new(3, [(0, 1), (1, 2), (2, 1)]);
396        assert_eq!(format!("{g}"), "(V=[3], E={ 0->1 1<->2 })");
397    }
398
399    #[test]
400    fn test_display_oriented() {
401        let g = OrientedGraph::new(2, [(0, 1)]);
402        assert_eq!(format!("{g}"), "(V=[2], E={ 0->1 })");
403    }
404}
flag_algebra/flags/digraph.rs

flag_algebra/flags/
digraph.rs
