gammalooprs/cff/
orientations.rs

1use color_eyre::Result;
2use eyre::eyre;
3use itertools::{EitherOrBoth, Itertools};
4use linnet::half_edge::involution::{EdgeIndex, EdgeVec, EdgeVecIter, Orientation};
5use symbolica::prelude::*;
6
7use crate::utils::GS;
8
9#[derive(Clone, Debug, PartialEq, Eq, PartialOrd, Ord)]
10pub struct RepresentativeScore {
11    undirected_count: usize,
12    default_count: usize,
13    leading_defaults: Vec<bool>,
14}
15
16pub trait GraphOrientation: Sized {
17    fn orientation(&self) -> &EdgeVec<Orientation>;
18
19    fn orientation_thetas(&self) -> Atom {
20        let mut thetas = Atom::num(1);
21
22        for (e, h) in self.orientation() {
23            match h {
24                Orientation::Default => {
25                    thetas *= GS.sign_theta(GS.sign(e));
26                }
27                Orientation::Reversed => {
28                    thetas *= GS.sign_theta(-GS.sign(e));
29                }
30                _ => {}
31            }
32        }
33        thetas
34    }
35
36    fn orientation_delta(&self) -> Atom
37    where
38        Self: Sized,
39    {
40        GS.orientation_delta(self)
41    }
42
43    fn select<'a>(&self, atom: impl Into<AtomOrView<'a>>) -> Atom {
44        let theta_reps = vec![
45            Replacement::new(GS.sign_theta(1).to_pattern(), Atom::num(1)),
46            Replacement::new(GS.sign_theta(-1).to_pattern(), Atom::Zero),
47        ];
48
49        let mut reps = Vec::new();
50
51        for (e, h) in self.orientation() {
52            match h {
53                Orientation::Default => {
54                    reps.push(Replacement::new(GS.sign(e).to_pattern(), Atom::num(1)));
55                }
56                Orientation::Reversed => {
57                    reps.push(Replacement::new(GS.sign(e).to_pattern(), Atom::num(-1)));
58                }
59                _ => {}
60            }
61        }
62
63        let orientation = self.orientation();
64        atom.into()
65            .replace_multiple(&reps)
66            .replace_multiple(&theta_reps)
67            .replace_map(|term, _ctx, out| {
68                if let AtomView::Fun(f) = term
69                    && f.get_symbol() == GS.orientation_delta
70                {
71                    if f.iter()
72                        .zip_longest(orientation)
73                        .all(|either| match either {
74                            EitherOrBoth::Both(a, (_, o)) => {
75                                if let Ok(a) = i64::try_from(a) {
76                                    match o {
77                                        Orientation::Default => a >= 0,
78                                        Orientation::Reversed => a <= 0,
79                                        Orientation::Undirected => true,
80                                    }
81                                } else {
82                                    false
83                                }
84                            }
85                            EitherOrBoth::Left(_) | EitherOrBoth::Right(_) => false,
86                        })
87                    {
88                        **out = Atom::num(1);
89                    } else {
90                        **out = Atom::Zero;
91                    }
92                }
93            })
94    }
95
96    fn iterate<'a>(&'a self) -> EdgeVecIter<'a, Orientation> {
97        self.orientation().iter()
98    }
99
100    fn get(&self, index: EdgeIndex) -> Orientation {
101        self.orientation()[index]
102    }
103
104    /// Returns `true` if the orientation matches the reference, ignoring `Undirected` edges of the reference.
105    fn is_compatible_with(&self, reference: &Self) -> bool {
106        self.iterate()
107            .zip_eq(reference.orientation())
108            .all(|((_, l), (_, r))| matches!(r, Orientation::Undirected) || l == r)
109    }
110
111    fn score(&self, internal_edges: &[EdgeIndex]) -> RepresentativeScore {
112        let mut undirected_count = 0;
113        let mut default_count = 0;
114        let mut leading_defaults = Vec::with_capacity(internal_edges.len());
115
116        for edge in internal_edges {
117            let is_default = match self.get(*edge) {
118                Orientation::Undirected => {
119                    undirected_count += 1;
120                    false
121                }
122                Orientation::Default => {
123                    default_count += 1;
124                    true
125                }
126                Orientation::Reversed => false,
127            };
128            leading_defaults.push(is_default);
129        }
130
131        RepresentativeScore {
132            undirected_count,
133            default_count,
134            leading_defaults,
135        }
136    }
137
138    /// Select the deterministic full-graph representative used to host the integrated UV term.
139    ///
140    /// The reduced orientation already fixes all edges that remain explicit after contracting the
141    /// integrated subgraph. Any contracted edge appears as `Undirected` and is therefore ignored when
142    /// matching compatible full orientations.
143    ///
144    /// Among the compatible candidates, the representative is chosen by maximizing:
145    /// 1. the number of `Undirected` internal edges
146    /// 2. then the number of `Default` internal edges
147    /// 3. then the lexicographically maximal `is_default` pattern in ascending internal-edge order
148    ///
149    /// The first criterion is currently future-proof only: the canonical full-graph acyclic basis is
150    /// built from `Default` / `Reversed` assignments on paired internal edges, so `Undirected`
151    /// internal entries are not expected there unless the global orientation-generation step changes.
152    fn select_representative_orientation<'b>(
153        self,
154        valid_global_orientations: &'b [Self],
155        internal_edges: &[EdgeIndex],
156    ) -> Result<&'b Self> {
157        valid_global_orientations
158            .iter()
159            .filter(|candidate| candidate.is_compatible_with(&self))
160            .max_by_key(|candidate| candidate.score(internal_edges))
161            .ok_or_else(|| {
162                eyre!(
163                    "no valid global orientation matches reduced orientation {}",
164                    self.orientation_delta()
165                )
166            })
167    }
168
169    /// Build only the selector factors for the internal edges of the integrated subgraph.
170    ///
171    /// This intentionally does **not** use `orientation_thetas()` on the whole representative
172    /// orientation. The reduced-graph CFF term already carries selectors for the edges that remain
173    /// explicit after contraction, so re-applying them here would duplicate selectors on external
174    /// edges.
175    fn internal_orientation_selector(&self, internal_edges: &[EdgeIndex]) -> Atom {
176        let mut selector = Atom::num(1);
177
178        for edge in internal_edges {
179            match self.get(*edge) {
180                Orientation::Default => selector *= GS.sign_theta(GS.sign(*edge)),
181                Orientation::Reversed => selector *= GS.sign_theta(-GS.sign(*edge)),
182                Orientation::Undirected => {}
183            }
184        }
185
186        selector
187    }
188}
189
190impl<T> GraphOrientation for T
191where
192    T: three_dimensional_reps::GraphOrientation,
193{
194    fn orientation(&self) -> &EdgeVec<Orientation> {
195        three_dimensional_reps::GraphOrientation::orientation(self)
196    }
197}
198
199#[cfg(test)]
200mod tests {
201
202    use crate::{cff::orientations::GraphOrientation, utils::GS};
203    use linnet::half_edge::involution::{EdgeIndex, EdgeVec, Orientation};
204
205    fn orientation(value: i8) -> Orientation {
206        match value {
207            1 => Orientation::Default,
208            -1 => Orientation::Reversed,
209            0 => Orientation::Undirected,
210            _ => panic!("invalid orientation encoding"),
211        }
212    }
213
214    fn edgevec(values: impl IntoIterator<Item = i8>) -> EdgeVec<Orientation> {
215        EdgeVec::from_iter(values.into_iter().map(orientation))
216    }
217
218    fn edges(values: impl IntoIterator<Item = usize>) -> Vec<EdgeIndex> {
219        values.into_iter().map(EdgeIndex).collect()
220    }
221
222    #[test]
223    fn picks_first_valid_internal_representatives_per_external_class() {
224        let valid = vec![
225            edgevec([1, -1, 1, -1, 1]),
226            edgevec([1, 1, -1, -1, 1]),
227            edgevec([1, 1, -1, -1, -1]),
228            edgevec([-1, 1, 1, 1, -1]),
229        ];
230        let internal = edges([2, 3, 4]);
231
232        let reduced_pm = edgevec([1, -1, 0, 0, 0]);
233        let reduced_pp = edgevec([1, 1, 0, 0, 0]);
234        let reduced_mp = edgevec([-1, 1, 0, 0, 0]);
235
236        assert_eq!(
237            reduced_pm
238                .select_representative_orientation(&valid, &internal)
239                .unwrap(),
240            &valid[0]
241        );
242        assert_eq!(
243            reduced_pp
244                .select_representative_orientation(&valid, &internal)
245                .unwrap(),
246            &valid[1]
247        );
248        assert_eq!(
249            reduced_mp
250                .select_representative_orientation(&valid, &internal)
251                .unwrap(),
252            &valid[3]
253        );
254    }
255
256    #[test]
257    fn prefers_more_undirected_internal_edges_first() {
258        let valid = vec![edgevec([1, 0, 1]), edgevec([1, 1, 1]), edgevec([1, -1, 1])];
259        let reduced = edgevec([1, 0, 1]);
260        let internal = edges([1]);
261
262        assert_eq!(
263            reduced
264                .select_representative_orientation(&valid, &internal)
265                .unwrap(),
266            &valid[0]
267        );
268    }
269
270    #[test]
271    fn prefers_more_default_internal_edges_when_undirected_counts_tie() {
272        let valid = vec![
273            edgevec([1, 1, -1]),
274            edgevec([1, -1, -1]),
275            edgevec([1, -1, 1]),
276        ];
277        let reduced = edgevec([1, 0, 0]);
278        let internal = edges([1, 2]);
279
280        assert_eq!(
281            reduced
282                .select_representative_orientation(&valid, &internal)
283                .unwrap(),
284            &valid[0]
285        );
286    }
287
288    #[test]
289    fn breaks_default_ties_by_lexicographically_maximal_leading_defaults() {
290        let valid = vec![
291            edgevec([1, 1, -1, 1]),
292            edgevec([1, -1, 1, 1]),
293            edgevec([1, 1, 1, -1]),
294        ];
295        let reduced = edgevec([1, 0, 0, 0]);
296        let internal = edges([1, 2, 3]);
297
298        assert_eq!(
299            reduced
300                .select_representative_orientation(&valid, &internal)
301                .unwrap(),
302            &valid[2]
303        );
304    }
305
306    #[test]
307    fn errors_for_missing_external_orientation_class() {
308        let valid = vec![edgevec([1, 1, 1]), edgevec([1, -1, 1])];
309        let reduced = edgevec([-1, 0, 1]);
310        let internal = edges([1]);
311
312        assert!(
313            reduced
314                .select_representative_orientation(&valid, &internal)
315                .is_err()
316        );
317    }
318
319    #[test]
320    fn selector_only_depends_on_internal_edges() {
321        let representative = edgevec([1, -1, 1, -1]);
322        let selector = representative.internal_orientation_selector(&edges([1, 3]));
323
324        let expected =
325            GS.sign_theta(-GS.sign(EdgeIndex(1))) * GS.sign_theta(-GS.sign(EdgeIndex(3)));
326        assert_eq!(selector, expected);
327    }
328}
gammalooprs/cff/orientations.rs

gammalooprs/cff/
orientations.rs
