open_hypergraphs/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 coequalize_vertices(&self, q: &FiniteFunction<K>) -> Option<Hypergraph<K, O, A>> {
106        // TODO: wrap coequalizers in a newtype!
107        let s = self.s.map_values(q)?;
108        let t = self.t.map_values(q)?;
109        let w = SemifiniteFunction(coequalizer_universal(q, &self.w.0)?);
110        let x = self.x.clone();
111        Some(Hypergraph { s, t, w, x })
112    }
113
114    pub fn coproduct(&self, other: &Self) -> Self {
115        Hypergraph {
116            s: self.s.tensor(&other.s),
117            t: self.t.tensor(&other.t),
118            w: self.w.coproduct(&other.w),
119            x: self.x.coproduct(&other.x),
120        }
121    }
122
123    pub fn tensor_operations(Operations { x, a, b }: Operations<K, O, A>) -> Hypergraph<K, O, A> {
124        // NOTE: the validity of the result assumes validity of `operations`.
125        let inj0 = FiniteFunction::inj0(a.values.len(), b.values.len());
126        let inj1 = FiniteFunction::inj1(a.values.len(), b.values.len());
127        let s = IndexedCoproduct::new(a.sources, inj0).expect("invalid Operations?");
128        let t = IndexedCoproduct::new(b.sources, inj1).expect("invalid Operations?");
129        let w = a.values + b.values;
130        Hypergraph { s, t, w, x }
131    }
132}
133
134impl<K: ArrayKind, O, A> Add<&Hypergraph<K, O, A>> for &Hypergraph<K, O, A>
135where
136    K::Type<K::I>: NaturalArray<K>,
137    K::Type<O>: Array<K, O>,
138    K::Type<A>: Array<K, A>,
139{
140    type Output = Hypergraph<K, O, A>;
141
142    fn add(self, rhs: &Hypergraph<K, O, A>) -> Self::Output {
143        self.coproduct(rhs)
144    }
145}
146
147impl<K: ArrayKind, O, A> Clone for Hypergraph<K, O, A>
148where
149    K::Type<K::I>: Clone,
150    K::Type<O>: Clone,
151    K::Type<A>: Clone,
152{
153    fn clone(&self) -> Self {
154        Self {
155            s: self.s.clone(),
156            t: self.t.clone(),
157            w: self.w.clone(),
158            x: self.x.clone(),
159        }
160    }
161}
162
163// NOTE: manual Debug required because we need to specify array bounds.
164impl<K: ArrayKind, O: Debug, A: Debug> Debug for Hypergraph<K, O, A>
165where
166    K::Index: Debug,
167    K::Type<K::I>: Debug,
168    K::Type<O>: Debug,
169    K::Type<A>: Debug,
170{
171    fn fmt(&self, f: &mut std::fmt::Formatter<'_>) -> std::fmt::Result {
172        f.debug_struct("Hypergraph")
173            .field("s", &self.s)
174            .field("t", &self.t)
175            .field("w", &self.w)
176            .field("x", &self.x)
177            .finish()
178    }
179}
open_hypergraphs/hypergraph/object.rs

open_hypergraphs/hypergraph/
object.rs
