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
190#[cfg(test)]
191mod tests {
192
193    use crate::{cff::orientations::GraphOrientation, utils::GS};
194    use linnet::half_edge::involution::{EdgeIndex, EdgeVec, Orientation};
195
196    fn orientation(value: i8) -> Orientation {
197        match value {
198            1 => Orientation::Default,
199            -1 => Orientation::Reversed,
200            0 => Orientation::Undirected,
201            _ => panic!("invalid orientation encoding"),
202        }
203    }
204
205    fn edgevec(values: impl IntoIterator<Item = i8>) -> EdgeVec<Orientation> {
206        EdgeVec::from_iter(values.into_iter().map(orientation))
207    }
208
209    fn edges(values: impl IntoIterator<Item = usize>) -> Vec<EdgeIndex> {
210        values.into_iter().map(EdgeIndex).collect()
211    }
212
213    #[test]
214    fn picks_first_valid_internal_representatives_per_external_class() {
215        let valid = vec![
216            edgevec([1, -1, 1, -1, 1]),
217            edgevec([1, 1, -1, -1, 1]),
218            edgevec([1, 1, -1, -1, -1]),
219            edgevec([-1, 1, 1, 1, -1]),
220        ];
221        let internal = edges([2, 3, 4]);
222
223        let reduced_pm = edgevec([1, -1, 0, 0, 0]);
224        let reduced_pp = edgevec([1, 1, 0, 0, 0]);
225        let reduced_mp = edgevec([-1, 1, 0, 0, 0]);
226
227        assert_eq!(
228            reduced_pm
229                .select_representative_orientation(&valid, &internal)
230                .unwrap(),
231            &valid[0]
232        );
233        assert_eq!(
234            reduced_pp
235                .select_representative_orientation(&valid, &internal)
236                .unwrap(),
237            &valid[1]
238        );
239        assert_eq!(
240            reduced_mp
241                .select_representative_orientation(&valid, &internal)
242                .unwrap(),
243            &valid[3]
244        );
245    }
246
247    #[test]
248    fn prefers_more_undirected_internal_edges_first() {
249        let valid = vec![edgevec([1, 0, 1]), edgevec([1, 1, 1]), edgevec([1, -1, 1])];
250        let reduced = edgevec([1, 0, 1]);
251        let internal = edges([1]);
252
253        assert_eq!(
254            reduced
255                .select_representative_orientation(&valid, &internal)
256                .unwrap(),
257            &valid[0]
258        );
259    }
260
261    #[test]
262    fn prefers_more_default_internal_edges_when_undirected_counts_tie() {
263        let valid = vec![
264            edgevec([1, 1, -1]),
265            edgevec([1, -1, -1]),
266            edgevec([1, -1, 1]),
267        ];
268        let reduced = edgevec([1, 0, 0]);
269        let internal = edges([1, 2]);
270
271        assert_eq!(
272            reduced
273                .select_representative_orientation(&valid, &internal)
274                .unwrap(),
275            &valid[0]
276        );
277    }
278
279    #[test]
280    fn breaks_default_ties_by_lexicographically_maximal_leading_defaults() {
281        let valid = vec![
282            edgevec([1, 1, -1, 1]),
283            edgevec([1, -1, 1, 1]),
284            edgevec([1, 1, 1, -1]),
285        ];
286        let reduced = edgevec([1, 0, 0, 0]);
287        let internal = edges([1, 2, 3]);
288
289        assert_eq!(
290            reduced
291                .select_representative_orientation(&valid, &internal)
292                .unwrap(),
293            &valid[2]
294        );
295    }
296
297    #[test]
298    fn errors_for_missing_external_orientation_class() {
299        let valid = vec![edgevec([1, 1, 1]), edgevec([1, -1, 1])];
300        let reduced = edgevec([-1, 0, 1]);
301        let internal = edges([1]);
302
303        assert!(
304            reduced
305                .select_representative_orientation(&valid, &internal)
306                .is_err()
307        );
308    }
309
310    #[test]
311    fn selector_only_depends_on_internal_edges() {
312        let representative = edgevec([1, -1, 1, -1]);
313        let selector = representative.internal_orientation_selector(&edges([1, 3]));
314
315        let expected =
316            GS.sign_theta(-GS.sign(EdgeIndex(1))) * GS.sign_theta(-GS.sign(EdgeIndex(3)));
317        assert_eq!(selector, expected);
318    }
319}
gammalooprs/cff/orientations.rs

gammalooprs/cff/
orientations.rs
