permutation_rs/group/
mod.rs

1//! The core of working with groups.
2//!
3//! A *group* is a set _G_ with an associated operation _G_ * _G_ -> _G_ such that
4//!
5//! 1. The operation is associative. I.e. (_a_ * _b_) * _c_ = _a_ * (_b_ * _c_)
6//!    for all _a_, _b_, _c_ in _G_.
7//! 2. There exist an identity element. I.e. an _e_ in _G_ with _e_ * _g_ = _g_
8//!    for all _g_ in _G_.
9//! 3. For each element _g_ in _G_ there is an inverse. I.e. an element _h_ in
10//!    _G_ such that _g_ * _h_ = _e_, the identity element in _G_.
11
12pub mod permutation;
13pub mod free;
14pub mod tree;
15pub mod special;
16pub mod calculation;
17
18use std::hash::Hash;
19use std::collections::HashMap;
20use std::collections::VecDeque;
21use std::fmt::{Display, Formatter, Error};
22
23use self::calculation::identity;
24
25/// The contract for a group element.
26pub trait GroupElement {
27    /// Determine if the group element is the identity.
28    fn is_identity(&self) -> bool;
29    /// The associated operation of the Group.
30    fn times(&self, multiplicant: &Self) -> Self;
31    /// Returns the inverse of the group element.
32    fn inverse(&self) -> Self;
33}
34
35/// A group can _act_ on a set. (See [Group Action](https://en.wikipedia.org/wiki/Group_action)).
36pub trait GroupAction {
37    /// The set the group acts on.
38    type Domain;
39
40    /// The action that the group has on the domain.
41    fn act_on(&self, element: &Self::Domain) -> Self::Domain;
42}
43
44/// The actual group.
45pub struct Group<Domain, G>
46    where Domain: Eq + Hash + Clone, G: GroupElement + GroupAction<Domain=Domain> + PartialEq {
47    levels: Vec<BaseStrongGeneratorLevel<Domain, G>>,
48}
49
50impl<Domain, G> Group<Domain, G>
51    where Domain: Eq + Hash + Clone, G: GroupElement + GroupAction<Domain=Domain> + PartialEq {
52    /// Creates a group with a given set of generators on a certain gset.
53    pub fn new(gset: Vec<Domain>, generators: Vec<G>) -> Group<Domain, G> {
54        let mut levels = vec!();
55        let mut gs = generators;
56        while gs.len() > 0 {
57            let base: Domain = find_base(&gset, &gs).expect("generators should move something");
58            let (level, stabilizers) = BaseStrongGeneratorLevel::new(base, gs);
59            levels.push(level);
60            gs = stabilizers;
61        }
62        Group { levels: levels }
63    }
64
65    /// The order of the group, i.e. the number of elements this group has.
66    pub fn size(&self) -> usize {
67        self.levels
68            .iter()
69            .fold(1usize, |acc, ref level| acc * level.length() )
70    }
71
72    /// Determine if a group element is a member of this group.
73    pub fn is_member(&self, element: G) -> bool {
74        let candidate = self.strip(element);
75        candidate.is_identity()
76    }
77
78    /// Strip element with current group
79    pub fn strip(&self, element: G) -> G {
80        let mut candidate = element;
81        for level in &self.levels {
82            if level.has_transversal_for(&candidate) {
83                let transversal = level.transversal_for(&candidate).expect("should have transversal");
84                let inverse = transversal.inverse();
85                candidate = candidate.times(&inverse);
86            } else {
87                break;
88            }
89        }
90        candidate
91    }
92}
93
94fn find_base<Domain, G>(gset: &Vec<Domain>, generators: &Vec<G>) -> Option<Domain>
95    where Domain: Eq + Hash + Clone, G: GroupElement + GroupAction<Domain=Domain> {
96    for original in gset {
97        for generator in generators {
98            let image = generator.act_on(&original);
99            if &image != original {
100                return Some(image.clone())
101            }
102        }
103    }
104    None
105}
106
107impl<Domain, G> Display for Group<Domain, G>
108    where Domain: Eq + Hash + Clone + Display, G: GroupElement + GroupAction<Domain=Domain> + PartialEq + Display {
109    fn fmt(&self, f: &mut Formatter) -> Result<(), Error> {
110        write!(f, "<\n")?;
111        for level in &self.levels {
112            level.fmt(f)?;
113        }
114        write!(f, ">\n")
115    }
116}
117
118/// A level in the Schreier-Sims Base Strong generator algorithm.
119///
120/// It basically is a SchreierVector with some extra book-keeping.
121pub struct BaseStrongGeneratorLevel<Domain, G>
122    where Domain: Eq + Hash + Clone, G: GroupElement + GroupAction<Domain=Domain> + PartialEq {
123    /// The base element for this level.
124    base: Domain,
125    /// Generators that act on the base to form the orbit.
126    generators: Vec<G>,
127    /// A [Schreier vector](https://en.wikipedia.org/wiki/Schreier_vector) for
128    /// this base and generators.
129    indices: HashMap<Domain, isize>,
130}
131
132impl<Domain, G> BaseStrongGeneratorLevel<Domain, G>
133    where Domain: Eq + Hash + Clone, G: GroupElement + GroupAction<Domain=Domain> + PartialEq {
134    /// Create a BaseStrongGeneratorLevel with a known base and generators.
135    pub fn new(base: Domain, generators: Vec<G>) -> (Self, Vec<G>) {
136        let mut to_visit: VecDeque<Domain> = VecDeque::new();
137        let mut indices: HashMap<Domain, isize> = HashMap::new();
138        let mut stabilizers: Vec<G> = vec!();
139        to_visit.push_back(base.clone());
140        indices.insert(base.clone(), -1);
141        while !to_visit.is_empty() {
142            let element = to_visit.pop_front().unwrap();
143            for (index, generator) in generators.iter().enumerate() {
144                let image = generator.act_on(&element);
145                if !indices.contains_key(&image) {
146                    indices.insert(image.clone(), index as isize);
147                    to_visit.push_back(image.clone());
148                } else {
149                    let to = transversal_for(&element, &generators, &indices).unwrap();
150                    let fro = transversal_for(&image, &generators, &indices).unwrap().inverse();
151                    let stabilizer = to.times(&generator).times(&fro);
152                    if add_to_stabilizers(&stabilizer, &stabilizers) {
153                        stabilizers.push(stabilizer);
154                    }
155                }
156            }
157        }
158        (BaseStrongGeneratorLevel { base, generators, indices }, stabilizers)
159    }
160
161    /// Determine if this levels base is acted upon by `g` in a way compatible for this level.
162    pub fn has_transversal_for(&self, g: &G) -> bool {
163        let image = g.act_on(&self.base);
164        self.indices.contains_key(&image)
165    }
166
167    /// The transversal corresponding with `g`.
168    pub fn transversal_for(&self, g: &G) -> Option<G> {
169        let image = g.act_on(&self.base);
170        transversal_for(&image, &self.generators, &self.indices)
171    }
172
173    /// Length of the orbit
174    pub fn length(&self) -> usize {
175        self.indices.len()
176    }
177}
178
179fn add_to_stabilizers<Domain, G>(stabilizer: &G, stabilizers: &Vec<G>) -> bool
180    where Domain: Eq + Hash + Clone, G: GroupElement + GroupAction<Domain=Domain> + PartialEq {
181    !stabilizer.is_identity() && !stabilizers.contains(&stabilizer)
182}
183
184
185impl<Domain, G> Display for BaseStrongGeneratorLevel<Domain, G>
186    where Domain: Eq + Hash + Clone + Display, G: GroupElement + GroupAction<Domain=Domain> + PartialEq + Display {
187    fn fmt(&self, f: &mut Formatter) -> Result<(), Error> {
188        write!(f, "[{};<", self.base)?;
189        for g in &self.generators {
190            write!(f, "{}", g)?;
191        }
192        write!(f, ">;")?;
193        for (domain, index) in &self.indices {
194           write!(f, "({}, {})", domain, index)?; 
195        }
196        write!(f, "]\n")
197    } 
198}
199
200fn transversal_for<Domain, G>(start: &Domain, generators: &Vec<G>, indices: &HashMap<Domain, isize>) -> Option<G>
201    where Domain: Eq + Hash + Clone, G: GroupElement + GroupAction<Domain=Domain> {
202    let mut image = start.clone();
203
204    if indices.contains_key(&image) {
205        let mut transversal = identity(&generators);
206        let mut index = indices.get(&image).unwrap();
207        while *index != (-1 as isize) {
208            let generator = &generators[(*index as usize)];
209            let inverse = generator.inverse();
210            image = inverse.act_on(&image);
211            transversal = transversal.times(&inverse);
212            index = indices.get(&image).unwrap();
213        }
214        Some(transversal.inverse())
215    } else {
216        None
217    }
218
219}
220
221#[macro_export]
222macro_rules! morphism {
223    ( $($from: expr, $to: expr),* ) => {
224        {
225            let mut morphism_images = HashMap::new();
226            $(
227                morphism_images.insert(SLP::Generator($from), Word::generator($to));
228            )*
229            Morphism::new(morphism_images)
230        }
231    }
232}
233
234/// Morphism maps one Group to the other with respect of the group operation.
235pub struct Morphism<G, H>
236    where G: GroupElement + Eq + Hash, H: GroupElement + Eq + Hash {
237    generator_images: HashMap<G, H>
238}
239
240impl<G, H> Morphism<G, H>
241    where G: GroupElement + Eq + Hash, H: GroupElement + Eq + Hash + Clone {
242    /// Create a new morphism with a given set of images
243    pub fn new(generator_images: HashMap<G, H>) -> Morphism<G, H> {
244        Morphism { generator_images: generator_images }
245    }
246
247
248    /// maps an G-element to the corresponding H-element.
249    pub fn transform(&self, element: &G) -> H {
250        self.generator_images.get(element).expect("should have an image").clone()
251    }
252}
253
254#[cfg(test)]
255mod tests {
256    use std::collections::HashMap;
257    use super::permutation::Permutation;
258    use super::*;
259
260    fn d3() -> Group<u64, Permutation> {
261        let mut transposition_images = HashMap::new();
262        transposition_images.insert(0u64, 1u64);
263        transposition_images.insert(1u64, 0u64);
264        transposition_images.insert(2u64, 2u64);
265        let transposition = Permutation::new(transposition_images);
266
267        let mut rotation_images = HashMap::new();
268        rotation_images.insert(0u64, 1u64);
269        rotation_images.insert(1u64, 2u64);
270        rotation_images.insert(2u64, 0u64);
271        let rotation = Permutation::new(rotation_images);
272
273        let gset = vec!(0u64, 1u64, 2u64);
274        let generators = vec!(transposition, rotation);
275
276        Group::new(gset, generators)
277    }
278
279    #[test]
280    fn group_should_have_a_size() {
281        let group = d3();
282        println!("{}", group);
283
284
285        assert_eq!(group.size(), 6);
286    }
287
288    #[test]
289    fn group_should_determine_if_an_element_is_a_member() {
290        let mut transposition_images = HashMap::new();
291        transposition_images.insert(0u64, 2u64);
292        transposition_images.insert(1u64, 1u64);
293        transposition_images.insert(2u64, 0u64);
294        let transposition = Permutation::new(transposition_images);
295
296        let group = d3();
297
298        assert!(group.is_member(transposition));
299    }
300
301    #[test]
302    fn transversal_for_should_correctly_determine_transversal() {
303        let image = 4u64;
304        let mut a_image: HashMap<u64, u64> = HashMap::new();
305        a_image.insert(0u64, 1u64);
306        a_image.insert(1u64, 2u64);
307        a_image.insert(2u64, 0u64);
308        a_image.insert(3u64, 4u64);
309        a_image.insert(4u64, 5u64);
310        a_image.insert(5u64, 3u64);
311        let a = Permutation::new(a_image);
312        let mut b_image: HashMap<u64, u64> = HashMap::new();
313        b_image.insert(0u64, 3u64);
314        b_image.insert(1u64, 1u64);
315        b_image.insert(2u64, 2u64);
316        b_image.insert(3u64, 0u64);
317        b_image.insert(4u64, 4u64);
318        b_image.insert(5u64, 5u64);
319        let b = Permutation::new(b_image);
320        let generators = vec!(a.clone(), b.clone());
321        let mut indices: HashMap<u64, isize> = HashMap::new();
322        indices.insert(0u64, -1isize);
323        indices.insert(1u64, 0isize);
324        indices.insert(2u64, 0isize);
325        indices.insert(3u64, 1isize);
326        indices.insert(4u64, 0isize);
327        indices.insert(5u64, 0isize);
328
329        let transversal = transversal_for(&image, &generators, &indices).unwrap();
330
331        let expected = b.times(&a);
332        assert_eq!(transversal, expected);
333    }
334}
permutation_rs/group/mod.rs

permutation_rs/group/
mod.rs
