open_hypergraphs/open_hypergraph/
arrow.rs

1use crate::array::*;
2use crate::category::*;
3use crate::finite_function::*;
4use crate::hypergraph::{Hypergraph, InvalidHypergraph};
5use crate::operations::*;
6use crate::semifinite::*;
7
8use core::fmt::Debug;
9use core::ops::{BitOr, Shr};
10use num_traits::Zero;
11
12impl<K: ArrayKind> From<InvalidHypergraph<K>> for InvalidOpenHypergraph<K> {
13    fn from(value: InvalidHypergraph<K>) -> Self {
14        InvalidOpenHypergraph::InvalidHypergraph(value)
15    }
16}
17
18#[derive(Debug)]
19pub enum InvalidOpenHypergraph<K: ArrayKind> {
20    CospanSourceType(K::I, K::I),
21    CospanTargetType(K::I, K::I),
22    InvalidHypergraph(InvalidHypergraph<K>),
23}
24
25/// Open Hypergraphs
26///
27/// # Invariants
28///
29/// We must have the following invariants:
30///
31/// These are checked by the [`OpenHypergraph::validate`] method
32///
33/// # Panics
34///
35/// Most operations assume the invariants hold, and will panic if not.
36pub struct OpenHypergraph<K: ArrayKind, O, A> {
37    pub s: FiniteFunction<K>,
38    pub t: FiniteFunction<K>,
39    pub h: Hypergraph<K, O, A>,
40}
41
42impl<K: ArrayKind, O, A> OpenHypergraph<K, O, A>
43where
44    K::Type<K::I>: NaturalArray<K>,
45    K::Type<O>: Array<K, O>,
46    K::Type<A>: Array<K, A>,
47{
48    pub fn new(
49        s: FiniteFunction<K>,
50        t: FiniteFunction<K>,
51        h: Hypergraph<K, O, A>,
52    ) -> Result<Self, InvalidOpenHypergraph<K>> {
53        let f = OpenHypergraph { s, t, h };
54        f.validate()
55    }
56
57    pub fn validate(self) -> Result<Self, InvalidOpenHypergraph<K>> {
58        let h = self.h.validate()?;
59        let w_source = h.w.0.len();
60        let s_target = self.s.target();
61        let t_target = self.t.target();
62
63        // TODO: validate hypergraph as well
64        if s_target != w_source {
65            Err(InvalidOpenHypergraph::CospanSourceType(s_target, w_source))
66        } else if t_target != w_source {
67            Err(InvalidOpenHypergraph::CospanTargetType(t_target, w_source))
68        } else {
69            Ok(OpenHypergraph {
70                s: self.s,
71                t: self.t,
72                h,
73            })
74        }
75    }
76
77    pub fn singleton(
78        x: A,
79        a: SemifiniteFunction<K, O>,
80        b: SemifiniteFunction<K, O>,
81    ) -> OpenHypergraph<K, O, A> {
82        Self::tensor_operations(Operations::singleton(x, a, b))
83    }
84
85    pub fn tensor_operations(operations: Operations<K, O, A>) -> OpenHypergraph<K, O, A> {
86        let h = Hypergraph::tensor_operations(operations);
87        let t = h.t.values.clone();
88        let s = h.s.values.clone();
89        OpenHypergraph { s, t, h }
90    }
91}
92
93impl<K: ArrayKind, O, A> Arrow for OpenHypergraph<K, O, A>
94where
95    K::Type<K::I>: NaturalArray<K>,
96    K::Type<O>: Array<K, O>,
97    K::Type<A>: Array<K, A>,
98{
99    // TODO: should be SemifiniteFunction?
100    type Object = SemifiniteFunction<K, O>;
101
102    fn source(&self) -> Self::Object {
103        // NOTE: invalid OpenHypergraph will panic!
104        (&self.s >> &self.h.w).expect("invalid open hypergraph: cospan source has invalid codomain")
105    }
106
107    fn target(&self) -> Self::Object {
108        (&self.t >> &self.h.w).expect("invalid open hypergraph: cospan target has invalid codomain")
109    }
110
111    fn identity(w: Self::Object) -> Self {
112        let s = FiniteFunction::<K>::identity(w.0.len());
113        let t = FiniteFunction::<K>::identity(w.0.len());
114        let h = Hypergraph::<K, O, A>::discrete(w);
115        OpenHypergraph { s, t, h }
116    }
117
118    fn compose(&self, other: &Self) -> Option<Self> {
119        if self.target() != other.source() {
120            return None;
121        }
122
123        // compute coequalizer q
124        let q_lhs = self.t.inject0(other.h.w.0.len());
125        let q_rhs = other.s.inject1(self.h.w.0.len());
126        let q = q_lhs.coequalizer(&q_rhs).expect("Invalid OpenHypergraph");
127
128        // Compute cospan legs
129        // NOTE: we don't return None here because composition should only fail on a type mismatch.
130        // If the compositions for s and t give None, it means there's a bug in the library!
131        let s = self.s.inject0(other.h.w.0.len()).compose(&q).unwrap();
132        let t = other.t.inject1(self.h.w.0.len()).compose(&q).unwrap();
133
134        // Tensor self and other, then unify wires on the boundaries.
135        // NOTE: this should never fail for a valid open hypergraph
136        let h = self.tensor(other).h.coequalize_vertices(&q).unwrap();
137
138        Some(OpenHypergraph { s, t, h })
139    }
140}
141
142impl<K: ArrayKind, O, A> Monoidal for OpenHypergraph<K, O, A>
143where
144    K::Type<K::I>: NaturalArray<K>,
145    K::Type<O>: Array<K, O>,
146    K::Type<A>: Array<K, A>,
147{
148    fn unit() -> Self::Object {
149        SemifiniteFunction::<K, O>::zero()
150    }
151
152    fn tensor(&self, other: &Self) -> Self {
153        OpenHypergraph {
154            s: &self.s | &other.s,
155            t: &self.t | &other.t,
156            h: &self.h + &other.h,
157        }
158    }
159}
160
161impl<K: ArrayKind, O, A> SymmetricMonoidal for OpenHypergraph<K, O, A>
162where
163    K::Type<K::I>: NaturalArray<K>,
164    K::Type<O>: Array<K, O>,
165    K::Type<A>: Array<K, A>,
166{
167    fn twist(a: Self::Object, b: Self::Object) -> Self {
168        let s = FiniteFunction::twist(a.len(), b.len());
169        let t = FiniteFunction::identity(a.len() + b.len());
170
171        // NOTE: because the *source* map is twist, the internal labelling of wires
172        // is `b + a` instead of `a + b`. This matters!
173        let h = Hypergraph::discrete(b + a);
174        OpenHypergraph { s, t, h }
175    }
176}
177
178impl<K: ArrayKind, O, A> Spider<K> for OpenHypergraph<K, O, A>
179where
180    K::Type<K::I>: NaturalArray<K>,
181    K::Type<O>: Array<K, O>,
182    K::Type<A>: Array<K, A>,
183{
184    fn dagger(&self) -> Self {
185        OpenHypergraph {
186            s: self.t.clone(),
187            t: self.s.clone(),
188            h: self.h.clone(),
189        }
190    }
191
192    fn spider(s: FiniteFunction<K>, t: FiniteFunction<K>, w: Self::Object) -> Option<Self> {
193        if s.target() != w.len() || t.target() != w.len() {
194            return None;
195        }
196
197        let h = Hypergraph::discrete(w);
198        Some(OpenHypergraph { s, t, h })
199    }
200}
201
202// Syntactic sugar for composition and tensor
203impl<K: ArrayKind, O, A> Shr<&OpenHypergraph<K, O, A>> for &OpenHypergraph<K, O, A>
204where
205    K::Type<K::I>: NaturalArray<K>,
206    K::Type<O>: Array<K, O>,
207    K::Type<A>: Array<K, A>,
208{
209    type Output = Option<OpenHypergraph<K, O, A>>;
210    fn shr(self, rhs: &OpenHypergraph<K, O, A>) -> Option<OpenHypergraph<K, O, A>> {
211        self.compose(rhs)
212    }
213}
214
215// Parallel composition
216impl<K: ArrayKind, O, A> BitOr<&OpenHypergraph<K, O, A>> for &OpenHypergraph<K, O, A>
217where
218    K::Type<K::I>: NaturalArray<K>,
219    K::Type<O>: Array<K, O>,
220    K::Type<A>: Array<K, A>,
221{
222    type Output = OpenHypergraph<K, O, A>;
223    fn bitor(self, rhs: &OpenHypergraph<K, O, A>) -> OpenHypergraph<K, O, A> {
224        self.tensor(rhs)
225    }
226}
227
228impl<K: ArrayKind, O, A> Clone for OpenHypergraph<K, O, A>
229where
230    K::Type<O>: Clone,
231    K::Type<A>: Clone,
232    K::Type<K::I>: Clone,
233{
234    fn clone(&self) -> Self {
235        Self {
236            s: self.s.clone(),
237            t: self.t.clone(),
238            h: self.h.clone(),
239        }
240    }
241}
242
243impl<K: ArrayKind, O: Debug, A: Debug> Debug for OpenHypergraph<K, O, A>
244where
245    K::Index: Debug,
246    K::Type<K::I>: Debug,
247    K::Type<O>: Debug,
248    K::Type<A>: Debug,
249{
250    fn fmt(&self, f: &mut std::fmt::Formatter<'_>) -> std::fmt::Result {
251        f.debug_struct("OpenHypergraph")
252            .field("s", &self.s)
253            .field("t", &self.t)
254            .field("h", &self.h)
255            .finish()
256    }
257}
open_hypergraphs/open_hypergraph/arrow.rs

open_hypergraphs/open_hypergraph/
arrow.rs
