vole/vole/refiners/
digraph.rs

1use std::sync::Arc;
2
3use super::Refiner;
4use super::{super::domain_state::DomainState, Side};
5use crate::datastructures::digraph::RawDigraph;
6use crate::perm::Permutation;
7use crate::vole::trace;
8use crate::{datastructures::digraph::Digraph, vole::backtracking::Backtrack};
9
10pub struct DigraphTransporter {
11    digraph_left: Arc<Digraph>,
12    digraph_right: Arc<Digraph>,
13    digraph_raw_left: Arc<RawDigraph>,
14    digraph_raw_right: Arc<RawDigraph>,
15}
16
17impl DigraphTransporter {
18    pub fn new_stabilizer(digraph: Arc<Digraph>) -> Self {
19        let raw = Arc::new(digraph.to_raw_unordered());
20        Self {
21            digraph_left: digraph.clone(),
22            digraph_right: digraph,
23            digraph_raw_left: raw.clone(),
24            digraph_raw_right: raw,
25        }
26    }
27
28    pub fn new_transporter(digraph_left: Arc<Digraph>, digraph_right: Arc<Digraph>) -> Self {
29        let digraph_raw_left = Arc::new(digraph_left.to_raw_unordered());
30        let digraph_raw_right = Arc::new(digraph_right.to_raw_unordered());
31        Self {
32            digraph_left,
33            digraph_right,
34            digraph_raw_left,
35            digraph_raw_right,
36        }
37    }
38
39    fn image(&self, p: &Permutation, side: Side) -> Digraph {
40        let digraph = match side {
41            Side::Left => &self.digraph_left,
42            Side::Right => &self.digraph_right,
43        };
44        &(**digraph) ^ p
45    }
46
47    fn compare(&self, lhs: &Digraph, rhs: &Digraph) -> std::cmp::Ordering {
48        lhs.cmp(rhs)
49    }
50}
51
52impl Refiner for DigraphTransporter {
53    gen_any_image_compare!(Digraph);
54
55    fn name(&self) -> String {
56        if self.is_group() {
57            format!("DigraphTransporter of {:?}", self.digraph_left)
58        } else {
59            format!(
60                "DigraphTransporter of {:?} -> {:?}",
61                self.digraph_left, self.digraph_right
62            )
63        }
64    }
65
66    fn check(&self, p: &Permutation) -> bool {
67        // For problems with many graphs (like finding two-closures), this function can takes >50% of runtime, so it
68        // is stupidly optimised. We:
69        // * Store graphs as vec<vec<>>, for fastest iteration and (binary) searching
70        // * Special-case when we (a) map a graph to itself and (b) map a point to itself.
71        //   In that case we check after applying permutation if we need to point is mapped to itself.
72        for i in 0..self.digraph_left.vertices() {
73            let neighbours = &self.digraph_raw_left[i];
74
75            let i_img = p.apply(i);
76            let img_neighbours = &self.digraph_raw_right[i_img];
77
78            // Special case when many points are fixed in the permutation
79            if std::ptr::eq(img_neighbours, neighbours) {
80                for (target, colour) in neighbours {
81                    let t_img = p.apply(*target);
82                    if t_img != *target {
83                        let equal = match img_neighbours.binary_search_by_key(&t_img, |(a, _)| *a) {
84                            Ok(x) => img_neighbours[x].1 == *colour,
85                            Err(_) => false,
86                        };
87                        if !equal {
88                            return false;
89                        }
90                    }
91                }
92            } else {
93                for (target, colour) in neighbours {
94                    let t_img = p.apply(*target);
95                    let equal = match img_neighbours.binary_search_by_key(&t_img, |(a, _)| *a) {
96                        Ok(x) => img_neighbours[x].1 == *colour,
97                        Err(_) => false,
98                    };
99                    if !equal {
100                        return false;
101                    }
102                }
103            }
104        }
105        true
106    }
107
108    fn refine_begin(&mut self, state: &mut DomainState, side: Side) -> trace::Result<()> {
109        state.add_arc_graph(match side {
110            Side::Left => &self.digraph_left,
111            Side::Right => &self.digraph_right,
112        });
113
114        Ok(())
115    }
116
117    fn is_group(&self) -> bool {
118        Arc::ptr_eq(&self.digraph_left, &self.digraph_right)
119    }
120}
121
122impl Backtrack for DigraphTransporter {
123    fn save_state(&mut self) {}
124    fn restore_state(&mut self) {}
125    fn state_depth(&self) -> usize {
126        0
127    }
128}
vole/vole/refiners/digraph.rs

vole/vole/refiners/
digraph.rs
