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
8use core::fmt::Debug;
9use core::ops::Add;
10use num_traits::Zero;
11
12#[derive(Debug)]
13pub enum InvalidHypergraph<K: ArrayKind> {
14    SourcesCount(K::I, K::I),
15    TargetsCount(K::I, K::I),
16    SourcesSet(K::I, K::I),
17    TargetsSet(K::I, K::I),
18}
19
20pub struct Hypergraph<K: ArrayKind, O, A> {
21    pub s: IndexedCoproduct<K, FiniteFunction<K>>,
22    pub t: IndexedCoproduct<K, FiniteFunction<K>>,
23    pub w: SemifiniteFunction<K, O>,
24    pub x: SemifiniteFunction<K, A>,
25}
26
27impl<K: ArrayKind, O, A> Hypergraph<K, O, A>
28where
29    K::Type<K::I>: AsRef<K::Index>,
30    K::Type<K::I>: NaturalArray<K>,
31    K::Type<O>: Array<K, O>,
32    K::Type<A>: Array<K, A>,
33{
34    /// Safely create a Hypergraph, ensuring its data is valid.
35    pub fn new(
36        s: IndexedCoproduct<K, FiniteFunction<K>>,
37        t: IndexedCoproduct<K, FiniteFunction<K>>,
38        w: SemifiniteFunction<K, O>,
39        x: SemifiniteFunction<K, A>,
40    ) -> Result<Hypergraph<K, O, A>, InvalidHypergraph<K>> {
41        let h = Hypergraph { s, t, w, x };
42        h.validate()
43    }
44
45    /// A hypergraph is valid when for both sources and targets segmented arrays:
46    ///
47    /// 1. Number of segments is equal to number of operations (`x.len()`)
48    /// 2. Values of segmented array are indices in set `w.source()`
49    ///
50    pub fn validate(self) -> Result<Self, InvalidHypergraph<K>> {
51        // num ops, wires
52        let n_x = self.x.len();
53        let n_w = self.w.len();
54
55        // Sources segmented array has as many segments as operations
56        if self.s.len() != self.x.len() {
57            return Err(InvalidHypergraph::SourcesCount(self.s.len(), n_x));
58        }
59
60        // Targets segmented array has as many segments as operations
61        if self.t.len() != self.x.len() {
62            return Err(InvalidHypergraph::TargetsCount(self.t.len(), n_x));
63        }
64
65        // *values* of sources segmented array should index into operations
66        let n_s = self.s.values.target();
67        if n_s != n_w {
68            return Err(InvalidHypergraph::SourcesSet(n_s, n_w));
69        }
70
71        // *values* of targets segmented array should index into operations
72        let n_t = self.t.values.target();
73        if n_t != n_w {
74            return Err(InvalidHypergraph::TargetsSet(n_t, n_w));
75        }
76
77        Ok(self)
78    }
79
80    // TODO: This is the unit object - put inside category interface?
81    /// Construct the empty hypergraph with no nodes and no hyperedges.
82    pub fn empty() -> Hypergraph<K, O, A> {
83        Hypergraph {
84            s: IndexedCoproduct::initial(K::I::zero()),
85            t: IndexedCoproduct::initial(K::I::zero()),
86            w: SemifiniteFunction::zero(),
87            x: SemifiniteFunction::zero(),
88        }
89    }
90
91    /// The discrete hypergraph, consisting of hypernodes labeled in `O`.
92    pub fn discrete(w: SemifiniteFunction<K, O>) -> Hypergraph<K, O, A> {
93        Hypergraph {
94            s: IndexedCoproduct::initial(w.len()),
95            t: IndexedCoproduct::initial(w.len()),
96            w,
97            x: SemifiniteFunction::zero(),
98        }
99    }
100
101    pub fn is_discrete(&self) -> bool {
102        self.s.is_empty() && self.t.is_empty() && self.x.0.is_empty()
103    }
104
105    pub fn coproduct(&self, other: &Self) -> Self {
106        Hypergraph {
107            s: self.s.tensor(&other.s),
108            t: self.t.tensor(&other.t),
109            w: self.w.coproduct(&other.w),
110            x: self.x.coproduct(&other.x),
111        }
112    }
113
114    pub fn tensor_operations(Operations { x, a, b }: Operations<K, O, A>) -> Hypergraph<K, O, A> {
115        // NOTE: the validity of the result assumes validity of `operations`.
116        let inj0 = FiniteFunction::inj0(a.values.len(), b.values.len());
117        let inj1 = FiniteFunction::inj1(a.values.len(), b.values.len());
118        let s = IndexedCoproduct::new(a.sources, inj0).expect("invalid Operations?");
119        let t = IndexedCoproduct::new(b.sources, inj1).expect("invalid Operations?");
120        let w = a.values + b.values;
121        Hypergraph { s, t, w, x }
122    }
123}
124
125impl<K: ArrayKind, O, A> Hypergraph<K, O, A>
126where
127    K::Type<K::I>: AsRef<K::Index>,
128    K::Type<K::I>: NaturalArray<K>,
129    K::Type<O>: Array<K, O> + PartialEq,
130    K::Type<A>: Array<K, A>,
131{
132    pub fn coequalize_vertices(&self, q: &FiniteFunction<K>) -> Option<Hypergraph<K, O, A>> {
133        // TODO: wrap coequalizers in a newtype!
134        let s = self.s.map_values(q)?;
135        let t = self.t.map_values(q)?;
136        let w = SemifiniteFunction(coequalizer_universal(q, &self.w.0)?);
137        let x = self.x.clone();
138        Some(Hypergraph { s, t, w, x })
139    }
140}
141
142impl<K: ArrayKind, O, A> Add<&Hypergraph<K, O, A>> for &Hypergraph<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    type Output = Hypergraph<K, O, A>;
149
150    fn add(self, rhs: &Hypergraph<K, O, A>) -> Self::Output {
151        self.coproduct(rhs)
152    }
153}
154
155impl<K: ArrayKind, O, A> Clone for Hypergraph<K, O, A>
156where
157    K::Type<K::I>: Clone,
158    K::Type<O>: Clone,
159    K::Type<A>: Clone,
160{
161    fn clone(&self) -> Self {
162        Self {
163            s: self.s.clone(),
164            t: self.t.clone(),
165            w: self.w.clone(),
166            x: self.x.clone(),
167        }
168    }
169}
170
171// NOTE: manual Debug required because we need to specify array bounds.
172impl<K: ArrayKind, O: Debug, A: Debug> Debug for Hypergraph<K, O, A>
173where
174    K::Index: Debug,
175    K::Type<K::I>: Debug,
176    K::Type<O>: Debug,
177    K::Type<A>: Debug,
178{
179    fn fmt(&self, f: &mut std::fmt::Formatter<'_>) -> std::fmt::Result {
180        f.debug_struct("Hypergraph")
181            .field("s", &self.s)
182            .field("t", &self.t)
183            .field("w", &self.w)
184            .field("x", &self.x)
185            .finish()
186    }
187}
open_hypergraphs/strict/hypergraph/object.rs

open_hypergraphs/strict/hypergraph/
object.rs
