flag_algebra/flags/
colored.rs

1use crate::flag::Flag;
2use canonical_form::Canonize;
3use std::cmp::*;
4use std::fmt;
5use std::fmt::{Debug, Display};
6
7/// A type for colored flags
8#[derive(Clone, PartialOrd, PartialEq, Ord, Eq, Debug, Hash, Serialize, Deserialize)]
9pub struct Colored<F, const N: u8> {
10    pub content: F,
11    pub color: Vec<u8>,
12}
13
14impl<F, const N: u8> Colored<F, N>
15where
16    F: Canonize,
17{
18    pub fn new(content: F, color: Vec<u8>) -> Self {
19        assert_eq!(content.size(), color.len());
20        for &c in &color {
21            assert!(c < N)
22        }
23        Self { content, color }
24    }
25}
26
27impl<F: Flag, const N: u8> Display for Colored<F, N> {
28    fn fmt(&self, f: &mut fmt::Formatter) -> fmt::Result {
29        Display::fmt(&self.content, f)?;
30        Debug::fmt(&self.color, f)
31    }
32}
33
34impl<F, const N: u8> Flag for Colored<F, N>
35where
36    F: Flag,
37{
38    /// Returns the subflag induced by the vertices in the slice `set`.
39    fn induce(&self, set: &[usize]) -> Self {
40        Self {
41            content: self.content.induce(set),
42            color: set.iter().map(|u| self.color[*u]).collect(),
43        }
44    }
45    fn size_zero_flags() -> Vec<Self> {
46        F::size_zero_flags()
47            .into_iter()
48            .map(|flag: F| Self {
49                content: flag,
50                color: Vec::new(),
51            })
52            .collect()
53    }
54    fn superflags(&self) -> Vec<Self> {
55        let mut res = Vec::new();
56        for flag in self.content.superflags() {
57            for c in 0..N {
58                let mut color = self.color.clone();
59                color.push(c);
60                res.push(Self {
61                    content: flag.clone(),
62                    color,
63                })
64            }
65        }
66        res
67    }
68
69    // FIXME: Incorrect name because of limitation of consts in Rusts
70    // Should be 'fmt("{}-colored {}", N, F::NAME'
71    const NAME: &'static str = "FIXME";
72    const HEREDITARY: bool = F::HEREDITARY;
73}
74
75impl<F, const N: u8> Canonize for Colored<F, N>
76where
77    F: Flag,
78{
79    #[inline]
80    fn size(&self) -> usize {
81        self.content.size()
82    }
83    fn invariant_neighborhood(&self, v: usize) -> Vec<Vec<usize>> {
84        self.content.invariant_neighborhood(v)
85    }
86    fn invariant_coloring(&self) -> Option<Vec<u64>> {
87        match self.content.invariant_coloring() {
88            None => Some(self.color.iter().map(|&c| c as u64).collect()),
89            Some(mut col) => {
90                for (i, c) in self.color.iter().enumerate() {
91                    col[i] = col[i] * (N as u64) + (*c as u64);
92                }
93                Some(col)
94            }
95        }
96    }
97    fn apply_morphism(&self, p: &[usize]) -> Self {
98        let mut color: Vec<u8> = vec![N; p.len()];
99        for (i, &pi) in p.iter().enumerate() {
100            color[pi] = self.color[i]
101        }
102        Self {
103            content: self.content.apply_morphism(p),
104            color,
105        }
106    }
107}
108
109#[cfg(test)]
110mod tests {
111    use super::*;
112    use crate::flags::Graph;
113    use canonical_form::Canonize;
114    #[test]
115    fn test_colored() {
116        type G2 = Colored<Graph, 2>;
117        let p3 = Graph::new(3, &[(0, 1), (1, 2)]);
118        let g: G2 = Colored {
119            content: p3.clone(),
120            color: vec![0, 0, 1],
121        };
122        let h: G2 = Colored {
123            content: p3,
124            color: vec![1, 0, 0],
125        };
126        assert_eq!(g.canonical(), h.canonical());
127        type G1 = Colored<Graph, 1>;
128        assert_eq!(G1::generate(5).len(), 34);
129        type G5 = Colored<Graph, 5>;
130        assert_eq!(G5::generate(2).len(), 30);
131        assert_eq!(G2::generate(3).len(), 20);
132    }
133}
flag_algebra/flags/colored.rs

flag_algebra/flags/
colored.rs
