open_hypergraphs/strict/open_hypergraph/
arrow.rs

1use crate::array::*;
2use crate::category::*;
3use crate::finite_function::*;
4use crate::operations::*;
5use crate::semifinite::*;
6use crate::strict::hypergraph::{Hypergraph, InvalidHypergraph};
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    ////////////////////////////////////////
93    // Category methods
94
95    pub fn source(&self) -> SemifiniteFunction<K, O> {
96        // NOTE: invalid OpenHypergraph will panic!
97        (&self.s >> &self.h.w).expect("invalid open hypergraph: cospan source has invalid codomain")
98    }
99
100    pub fn target(&self) -> SemifiniteFunction<K, O> {
101        (&self.t >> &self.h.w).expect("invalid open hypergraph: cospan target has invalid codomain")
102    }
103
104    pub fn identity(w: SemifiniteFunction<K, O>) -> OpenHypergraph<K, O, A> {
105        let s = FiniteFunction::<K>::identity(w.0.len());
106        let t = FiniteFunction::<K>::identity(w.0.len());
107        let h = Hypergraph::<K, O, A>::discrete(w);
108        OpenHypergraph { s, t, h }
109    }
110
111    pub fn spider(
112        s: FiniteFunction<K>,
113        t: FiniteFunction<K>,
114        w: SemifiniteFunction<K, O>,
115    ) -> Option<Self> {
116        if s.target() != w.len() || t.target() != w.len() {
117            return None;
118        }
119
120        let h = Hypergraph::discrete(w);
121        Some(OpenHypergraph { s, t, h })
122    }
123}
124
125impl<K: ArrayKind, O, A> OpenHypergraph<K, O, A>
126where
127    K::Type<K::I>: NaturalArray<K>,
128    K::Type<O>: Array<K, O> + PartialEq,
129    K::Type<A>: Array<K, A>,
130{
131    fn compose(&self, other: &Self) -> Option<Self> {
132        if self.target() != other.source() {
133            return None;
134        }
135
136        // compute coequalizer q
137        let q_lhs = self.t.inject0(other.h.w.0.len());
138        let q_rhs = other.s.inject1(self.h.w.0.len());
139        let q = q_lhs.coequalizer(&q_rhs).expect("Invalid OpenHypergraph");
140
141        // Compute cospan legs
142        // NOTE: we don't return None here because composition should only fail on a type mismatch.
143        // If the compositions for s and t give None, it means there's a bug in the library!
144        let s = self.s.inject0(other.h.w.0.len()).compose(&q).unwrap();
145        let t = other.t.inject1(self.h.w.0.len()).compose(&q).unwrap();
146
147        // Tensor self and other, then unify wires on the boundaries.
148        // NOTE: this should never fail for a valid open hypergraph
149        let h = self.tensor(other).h.coequalize_vertices(&q).unwrap();
150
151        Some(OpenHypergraph { s, t, h })
152    }
153}
154
155impl<K: ArrayKind, O, A> Arrow for OpenHypergraph<K, O, A>
156where
157    K::Type<K::I>: NaturalArray<K>,
158    K::Type<O>: Array<K, O> + PartialEq,
159    K::Type<A>: Array<K, A>,
160{
161    // TODO: should be SemifiniteFunction?
162    type Object = SemifiniteFunction<K, O>;
163
164    fn source(&self) -> Self::Object {
165        self.source()
166    }
167
168    fn target(&self) -> Self::Object {
169        self.target()
170    }
171
172    fn identity(w: Self::Object) -> Self {
173        Self::identity(w)
174    }
175
176    fn compose(&self, other: &Self) -> Option<Self> {
177        self.compose(other)
178    }
179}
180
181impl<K: ArrayKind, O, A> Monoidal for OpenHypergraph<K, O, A>
182where
183    K::Type<K::I>: NaturalArray<K>,
184    K::Type<O>: Array<K, O> + PartialEq,
185    K::Type<A>: Array<K, A>,
186{
187    fn unit() -> Self::Object {
188        SemifiniteFunction::<K, O>::zero()
189    }
190
191    fn tensor(&self, other: &Self) -> Self {
192        OpenHypergraph {
193            s: &self.s | &other.s,
194            t: &self.t | &other.t,
195            h: &self.h + &other.h,
196        }
197    }
198}
199
200impl<K: ArrayKind, O, A> SymmetricMonoidal for OpenHypergraph<K, O, A>
201where
202    K::Type<K::I>: NaturalArray<K>,
203    K::Type<O>: Array<K, O> + PartialEq,
204    K::Type<A>: Array<K, A>,
205{
206    fn twist(a: Self::Object, b: Self::Object) -> Self {
207        let s = FiniteFunction::twist(a.len(), b.len());
208        let t = FiniteFunction::identity(a.len() + b.len());
209
210        // NOTE: because the *source* map is twist, the internal labelling of wires
211        // is `b + a` instead of `a + b`. This matters!
212        let h = Hypergraph::discrete(b + a);
213        OpenHypergraph { s, t, h }
214    }
215}
216
217impl<K: ArrayKind, O, A> Spider<K> for OpenHypergraph<K, O, A>
218where
219    K::Type<K::I>: NaturalArray<K>,
220    K::Type<O>: Array<K, O> + PartialEq,
221    K::Type<A>: Array<K, A>,
222{
223    fn dagger(&self) -> Self {
224        OpenHypergraph {
225            s: self.t.clone(),
226            t: self.s.clone(),
227            h: self.h.clone(),
228        }
229    }
230
231    fn spider(s: FiniteFunction<K>, t: FiniteFunction<K>, w: Self::Object) -> Option<Self> {
232        OpenHypergraph::spider(s, t, w)
233    }
234}
235
236// Syntactic sugar for composition and tensor
237impl<K: ArrayKind, O, A> Shr<&OpenHypergraph<K, O, A>> for &OpenHypergraph<K, O, A>
238where
239    K::Type<K::I>: NaturalArray<K>,
240    K::Type<O>: Array<K, O> + PartialEq,
241    K::Type<A>: Array<K, A>,
242{
243    type Output = Option<OpenHypergraph<K, O, A>>;
244    fn shr(self, rhs: &OpenHypergraph<K, O, A>) -> Option<OpenHypergraph<K, O, A>> {
245        self.compose(rhs)
246    }
247}
248
249// Parallel composition
250impl<K: ArrayKind, O, A> BitOr<&OpenHypergraph<K, O, A>> for &OpenHypergraph<K, O, A>
251where
252    K::Type<K::I>: NaturalArray<K>,
253    K::Type<O>: Array<K, O> + PartialEq,
254    K::Type<A>: Array<K, A>,
255{
256    type Output = OpenHypergraph<K, O, A>;
257    fn bitor(self, rhs: &OpenHypergraph<K, O, A>) -> OpenHypergraph<K, O, A> {
258        self.tensor(rhs)
259    }
260}
261
262impl<K: ArrayKind, O, A> Clone for OpenHypergraph<K, O, A>
263where
264    K::Type<O>: Clone,
265    K::Type<A>: Clone,
266    K::Type<K::I>: Clone,
267{
268    fn clone(&self) -> Self {
269        Self {
270            s: self.s.clone(),
271            t: self.t.clone(),
272            h: self.h.clone(),
273        }
274    }
275}
276
277impl<K: ArrayKind, O: Debug, A: Debug> Debug for OpenHypergraph<K, O, A>
278where
279    K::Index: Debug,
280    K::Type<K::I>: Debug,
281    K::Type<O>: Debug,
282    K::Type<A>: Debug,
283{
284    fn fmt(&self, f: &mut std::fmt::Formatter<'_>) -> std::fmt::Result {
285        f.debug_struct("OpenHypergraph")
286            .field("s", &self.s)
287            .field("t", &self.t)
288            .field("h", &self.h)
289            .finish()
290    }
291}
open_hypergraphs/strict/open_hypergraph/arrow.rs

open_hypergraphs/strict/open_hypergraph/
arrow.rs
