open_hypergraphs/strict/hypergraph/
object.rs

1use crate::array::{Array, ArrayKind, NaturalArray};
2use crate::category::*;
3use crate::finite_function::{coequalizer_universal, FiniteFunction};
4use crate::indexed_coproduct::*;
5use crate::operations::Operations;
6use crate::semifinite::*;
7#[cfg(feature = "experimental")]
8use crate::strict::hypergraph::arrow::HypergraphArrow;
9
10use core::fmt::Debug;
11use core::ops::Add;
12use num_traits::Zero;
13
14#[derive(Debug)]
15pub enum InvalidHypergraph<K: ArrayKind> {
16    SourcesCount(K::I, K::I),
17    TargetsCount(K::I, K::I),
18    SourcesSet(K::I, K::I),
19    TargetsSet(K::I, K::I),
20}
21
22pub struct Hypergraph<K: ArrayKind, O, A> {
23    pub s: IndexedCoproduct<K, FiniteFunction<K>>,
24    pub t: IndexedCoproduct<K, FiniteFunction<K>>,
25    pub w: SemifiniteFunction<K, O>,
26    pub x: SemifiniteFunction<K, A>,
27}
28
29impl<K: ArrayKind, O, A> Hypergraph<K, O, A>
30where
31    K::Type<K::I>: AsRef<K::Index>,
32    K::Type<K::I>: NaturalArray<K>,
33    K::Type<O>: Array<K, O>,
34    K::Type<A>: Array<K, A>,
35{
36    /// Safely create a Hypergraph, ensuring its data is valid.
37    pub fn new(
38        s: IndexedCoproduct<K, FiniteFunction<K>>,
39        t: IndexedCoproduct<K, FiniteFunction<K>>,
40        w: SemifiniteFunction<K, O>,
41        x: SemifiniteFunction<K, A>,
42    ) -> Result<Hypergraph<K, O, A>, InvalidHypergraph<K>> {
43        let h = Hypergraph { s, t, w, x };
44        h.validate()
45    }
46
47    /// A hypergraph is valid when for both sources and targets segmented arrays:
48    ///
49    /// 1. Number of segments is equal to number of operations (`x.len()`)
50    /// 2. Values of segmented array are indices in set `w.source()`
51    ///
52    pub fn validate(self) -> Result<Self, InvalidHypergraph<K>> {
53        // num ops, wires
54        let n_x = self.x.len();
55        let n_w = self.w.len();
56
57        // Sources segmented array has as many segments as operations
58        if self.s.len() != self.x.len() {
59            return Err(InvalidHypergraph::SourcesCount(self.s.len(), n_x));
60        }
61
62        // Targets segmented array has as many segments as operations
63        if self.t.len() != self.x.len() {
64            return Err(InvalidHypergraph::TargetsCount(self.t.len(), n_x));
65        }
66
67        // *values* of sources segmented array should index into operations
68        let n_s = self.s.values.target();
69        if n_s != n_w {
70            return Err(InvalidHypergraph::SourcesSet(n_s, n_w));
71        }
72
73        // *values* of targets segmented array should index into operations
74        let n_t = self.t.values.target();
75        if n_t != n_w {
76            return Err(InvalidHypergraph::TargetsSet(n_t, n_w));
77        }
78
79        Ok(self)
80    }
81
82    // TODO: This is the unit object - put inside category interface?
83    /// Construct the empty hypergraph with no nodes and no hyperedges.
84    pub fn empty() -> Hypergraph<K, O, A> {
85        Hypergraph {
86            s: IndexedCoproduct::initial(K::I::zero()),
87            t: IndexedCoproduct::initial(K::I::zero()),
88            w: SemifiniteFunction::zero(),
89            x: SemifiniteFunction::zero(),
90        }
91    }
92
93    /// The discrete hypergraph, consisting of hypernodes labeled in `O`.
94    pub fn discrete(w: SemifiniteFunction<K, O>) -> Hypergraph<K, O, A> {
95        Hypergraph {
96            s: IndexedCoproduct::initial(w.len()),
97            t: IndexedCoproduct::initial(w.len()),
98            w,
99            x: SemifiniteFunction::zero(),
100        }
101    }
102
103    pub fn is_discrete(&self) -> bool {
104        self.s.is_empty() && self.t.is_empty() && self.x.0.is_empty()
105    }
106
107    pub fn coproduct(&self, other: &Self) -> Self {
108        Hypergraph {
109            s: self.s.tensor(&other.s),
110            t: self.t.tensor(&other.t),
111            w: self.w.coproduct(&other.w),
112            x: self.x.coproduct(&other.x),
113        }
114    }
115
116    pub fn tensor_operations(Operations { x, a, b }: Operations<K, O, A>) -> Hypergraph<K, O, A> {
117        // NOTE: the validity of the result assumes validity of `operations`.
118        let inj0 = FiniteFunction::inj0(a.values.len(), b.values.len());
119        let inj1 = FiniteFunction::inj1(a.values.len(), b.values.len());
120        let s = IndexedCoproduct::new(a.sources, inj0).expect("invalid Operations?");
121        let t = IndexedCoproduct::new(b.sources, inj1).expect("invalid Operations?");
122        let w = a.values + b.values;
123        Hypergraph { s, t, w, x }
124    }
125}
126
127impl<K: ArrayKind, O, A> Hypergraph<K, O, A>
128where
129    K::Type<K::I>: NaturalArray<K>,
130    K::Type<O>: Array<K, O>,
131{
132    /// The number of occurrences of `node` as a target across all hyperedges.
133    pub fn in_degree(&self, node: K::I) -> K::I {
134        let node = node.clone();
135        assert!(node < self.w.len(), "node id {:?} is out of bounds", node);
136        let counts = (self.t.values.table.as_ref() as &K::Type<K::I>).bincount(self.w.len());
137        counts.get(node)
138    }
139
140    /// The number of occurrences of `node` as a source across all hyperedges.
141    pub fn out_degree(&self, node: K::I) -> K::I {
142        let node = node.clone();
143        assert!(node < self.w.len(), "node id {:?} is out of bounds", node);
144        let counts = (self.s.values.table.as_ref() as &K::Type<K::I>).bincount(self.w.len());
145        counts.get(node)
146    }
147}
148
149impl<K: ArrayKind, O, A> Hypergraph<K, O, A>
150where
151    K::Type<K::I>: AsRef<K::Index>,
152    K::Type<K::I>: NaturalArray<K>,
153    K::Type<O>: Array<K, O> + PartialEq,
154    K::Type<A>: Array<K, A>,
155{
156    pub fn coequalize_vertices(&self, q: &FiniteFunction<K>) -> Option<Hypergraph<K, O, A>> {
157        // TODO: wrap coequalizers in a newtype!
158        let s = self.s.map_values(q)?;
159        let t = self.t.map_values(q)?;
160        let w = SemifiniteFunction(coequalizer_universal(q, &self.w.0)?);
161        let x = self.x.clone();
162        Some(Hypergraph { s, t, w, x })
163    }
164
165    // Compute the pushout of a span of wire maps into hypergraphs.
166    #[cfg(feature = "experimental")]
167    pub(crate) fn pushout_along_span(
168        left: &Hypergraph<K, O, A>,
169        right: &Hypergraph<K, O, A>,
170        f: &FiniteFunction<K>,
171        g: &FiniteFunction<K>,
172    ) -> Option<(
173        Hypergraph<K, O, A>,
174        HypergraphArrow<K, O, A>,
175        HypergraphArrow<K, O, A>,
176    )>
177    where
178        K::Type<K::I>: NaturalArray<K>,
179        K::Type<O>: Array<K, O> + PartialEq,
180        K::Type<A>: Array<K, A> + PartialEq,
181    {
182        if f.target() != left.w.len() || g.target() != right.w.len() {
183            return None;
184        }
185
186        // Lift span legs into the shared coproduct codomain left.w + right.w
187        // and coequalize to obtain the wire identifications.
188        let f_lift = f.inject0(right.w.len());
189        let g_lift = g.inject1(left.w.len());
190        let q = f_lift.coequalizer(&g_lift)?;
191        // Form the coproduct hypergraph and quotient its vertices by the coequalizer.
192        let coproduct = left + right;
193        let target = coproduct.coequalize_vertices(&q)?;
194
195        // Build the induced arrows from each side of the span into the pushout.
196        let w_left = FiniteFunction::inj0(left.w.len(), right.w.len()).compose(&q)?;
197        let w_right = FiniteFunction::inj1(left.w.len(), right.w.len()).compose(&q)?;
198        let x_left = FiniteFunction::inj0(left.x.len(), right.x.len());
199        let x_right = FiniteFunction::inj1(left.x.len(), right.x.len());
200
201        let left_arrow = HypergraphArrow::new(left.clone(), target.clone(), w_left, x_left).ok()?;
202        let right_arrow =
203            HypergraphArrow::new(right.clone(), target.clone(), w_right, x_right).ok()?;
204
205        Some((target, left_arrow, right_arrow))
206    }
207}
208
209impl<K: ArrayKind, O, A> Add<&Hypergraph<K, O, A>> for &Hypergraph<K, O, A>
210where
211    K::Type<K::I>: NaturalArray<K>,
212    K::Type<O>: Array<K, O>,
213    K::Type<A>: Array<K, A>,
214{
215    type Output = Hypergraph<K, O, A>;
216
217    fn add(self, rhs: &Hypergraph<K, O, A>) -> Self::Output {
218        self.coproduct(rhs)
219    }
220}
221
222impl<K: ArrayKind, O, A> Clone for Hypergraph<K, O, A>
223where
224    K::Type<K::I>: Clone,
225    K::Type<O>: Clone,
226    K::Type<A>: Clone,
227{
228    fn clone(&self) -> Self {
229        Self {
230            s: self.s.clone(),
231            t: self.t.clone(),
232            w: self.w.clone(),
233            x: self.x.clone(),
234        }
235    }
236}
237
238// NOTE: manual Debug required because we need to specify array bounds.
239impl<K: ArrayKind, O: Debug, A: Debug> Debug for Hypergraph<K, O, A>
240where
241    K::Index: Debug,
242    K::Type<K::I>: Debug,
243    K::Type<O>: Debug,
244    K::Type<A>: Debug,
245{
246    fn fmt(&self, f: &mut std::fmt::Formatter<'_>) -> std::fmt::Result {
247        f.debug_struct("Hypergraph")
248            .field("s", &self.s)
249            .field("t", &self.t)
250            .field("w", &self.w)
251            .field("x", &self.x)
252            .finish()
253    }
254}
open_hypergraphs/strict/hypergraph/object.rs

open_hypergraphs/strict/hypergraph/
object.rs
