open_hypergraphs/lax/
open_hypergraph.rs

1//! Cospans of Hypergraphs.
2use super::hypergraph::*;
3use crate::strict::vec::{FiniteFunction, VecKind};
4
5/// A lax OpenHypergraph is a cospan of lax hypergraphs:
6/// a hypergraph equipped with two finite maps representing the *interfaces*.
7#[derive(Debug, Clone, PartialEq)]
8#[cfg_attr(feature = "serde", derive(serde::Serialize, serde::Deserialize))]
9#[cfg_attr(
10    feature = "serde",
11    serde(
12        bound = "O: serde::Serialize + serde::de::DeserializeOwned, A: serde::Serialize + serde::de::DeserializeOwned"
13    )
14)]
15pub struct OpenHypergraph<O, A> {
16    pub sources: Vec<NodeId>,
17    pub targets: Vec<NodeId>,
18    pub hypergraph: Hypergraph<O, A>,
19}
20
21// Imperative-specific methods
22impl<O, A> OpenHypergraph<O, A> {
23    /// The empty OpenHypergraph with no nodes and no edges.
24    ///
25    /// In categorical terms, this is the identity map at the unit object.
26    pub fn empty() -> Self {
27        OpenHypergraph {
28            sources: vec![],
29            targets: vec![],
30            hypergraph: Hypergraph::empty(),
31        }
32    }
33
34    pub fn from_strict(f: crate::strict::open_hypergraph::OpenHypergraph<VecKind, O, A>) -> Self {
35        let sources = f.s.table.0.into_iter().map(NodeId).collect();
36        let targets = f.t.table.0.into_iter().map(NodeId).collect();
37        let hypergraph = Hypergraph::from_strict(f.h);
38        OpenHypergraph {
39            sources,
40            targets,
41            hypergraph,
42        }
43    }
44
45    /// Create a new node in the hypergraph labeled `w`.
46    pub fn new_node(&mut self, w: O) -> NodeId {
47        self.hypergraph.new_node(w)
48    }
49
50    pub fn new_edge(&mut self, x: A, interface: impl Into<Hyperedge>) -> EdgeId {
51        self.hypergraph.new_edge(x, interface)
52    }
53
54    /// Create a new "operation" in the hypergraph.
55    /// Concretely, `f.new_operation(x, s, t)` mutates `f` by adding:
56    ///
57    /// 1. a new hyperedge labeled `x`
58    /// 2. `len(s)` new nodes, with the `i`th node labeled `s[i]`
59    /// 3. `len(t)` new nodes, with the `i`th node labeled `t[i]`
60    ///
61    /// Returns the new hyperedge ID and the [`NodeId`]s of the source/target nodes.
62    ///
63    /// This is a convenience wrapper for [`Hypergraph::new_operation`]
64    pub fn new_operation(
65        &mut self,
66        x: A,
67        source_type: Vec<O>,
68        target_type: Vec<O>,
69    ) -> (EdgeId, Interface) {
70        self.hypergraph.new_operation(x, source_type, target_type)
71    }
72
73    /// An [`OpenHypergraph`] consisting of a single operation.
74    pub fn singleton(x: A, source_type: Vec<O>, target_type: Vec<O>) -> Self {
75        let mut f = Self::empty();
76        let (_, (s, t)) = f.new_operation(x, source_type, target_type);
77        f.sources = s;
78        f.targets = t;
79        f
80    }
81
82    /// Compute an open hypergraph by calling `to_hypergraph` on the internal `Hypergraph`.
83    pub fn unify(&mut self, v: NodeId, w: NodeId) {
84        self.hypergraph.unify(v, w);
85    }
86
87    pub fn add_edge_source(&mut self, edge_id: EdgeId, w: O) -> NodeId {
88        self.hypergraph.add_edge_source(edge_id, w)
89    }
90
91    pub fn add_edge_target(&mut self, edge_id: EdgeId, w: O) -> NodeId {
92        self.hypergraph.add_edge_target(edge_id, w)
93    }
94
95    /// Set the nodes of the OpenHypergraph, possibly changing types.
96    /// Returns None if new nodes array had different length.
97    pub fn with_nodes<T, F: FnOnce(Vec<O>) -> Vec<T>>(self, f: F) -> Option<OpenHypergraph<T, A>> {
98        self.hypergraph
99            .with_nodes(f)
100            .map(|hypergraph| OpenHypergraph {
101                sources: self.sources,
102                targets: self.targets,
103                hypergraph,
104            })
105    }
106
107    /// Map the node labels of this OpenHypergraph, possibly changing their type
108    pub fn map_nodes<F: Fn(O) -> T, T>(self, f: F) -> OpenHypergraph<T, A> {
109        OpenHypergraph {
110            sources: self.sources,
111            targets: self.targets,
112            hypergraph: self.hypergraph.map_nodes(f),
113        }
114    }
115
116    /// Set the edges of the OpenHypergraph, possibly changing types.
117    /// Returns None if new edges array had different length.
118    pub fn with_edges<T, F: FnOnce(Vec<A>) -> Vec<T>>(self, f: F) -> Option<OpenHypergraph<O, T>> {
119        self.hypergraph
120            .with_edges(f)
121            .map(|hypergraph| OpenHypergraph {
122                sources: self.sources,
123                targets: self.targets,
124                hypergraph,
125            })
126    }
127
128    /// Map the edge labels of this OpenHypergraph, possibly changing their type
129    pub fn map_edges<F: Fn(A) -> T, T>(self, f: F) -> OpenHypergraph<O, T> {
130        OpenHypergraph {
131            sources: self.sources,
132            targets: self.targets,
133            hypergraph: self.hypergraph.map_edges(f),
134        }
135    }
136}
137
138impl<O, A> OpenHypergraph<O, A> {
139    pub fn identity(a: Vec<O>) -> Self {
140        let mut f = OpenHypergraph::empty();
141        f.sources = (0..a.len()).map(NodeId).collect();
142        f.targets = (0..a.len()).map(NodeId).collect();
143        f.hypergraph.nodes = a;
144        f
145    }
146
147    pub fn spider(s: FiniteFunction, t: FiniteFunction, w: Vec<O>) -> Option<Self> {
148        // s and t must have target equal to the number of supplied nodes
149        if s.target != t.target || s.target != w.len() {
150            return None;
151        }
152
153        let mut f = OpenHypergraph::empty();
154        f.hypergraph.nodes = w;
155        f.sources = s.table.0.into_iter().map(NodeId).collect();
156        f.targets = t.table.0.into_iter().map(NodeId).collect();
157        Some(f)
158    }
159}
160
161impl<O: Clone, A: Clone> OpenHypergraph<O, A> {
162    pub fn tensor(&self, other: &Self) -> Self {
163        let hypergraph = Hypergraph::coproduct(&self.hypergraph, &other.hypergraph);
164
165        // renumber all nodes
166        let n = self.hypergraph.nodes.len();
167
168        let sources = self
169            .sources
170            .iter()
171            .cloned()
172            .chain(other.sources.iter().map(|&i| NodeId(i.0 + n)))
173            .collect();
174
175        let targets = self
176            .targets
177            .iter()
178            .cloned()
179            .chain(other.targets.iter().map(|&i| NodeId(i.0 + n)))
180            .collect();
181
182        OpenHypergraph {
183            sources,
184            targets,
185            hypergraph,
186        }
187    }
188}
189
190impl<O: Clone + PartialEq, A: Clone> OpenHypergraph<O, A> {
191    /// Apply the quotient map to identify nodes in the internal [`Hypergraph`].
192    /// This deletes the internal quotient map, resulting in a *strict* [`OpenHypergraph`].
193    pub fn quotient(&mut self) {
194        self.quotient_witness();
195    }
196
197    /// Like [`Self::quotient`], but also returns the coequalizer [`crate::finite_function::FiniteFunction`]
198    /// mapping pre-quotient node indices to post-quotient node indices.
199    pub fn quotient_witness(&mut self) -> crate::finite_function::FiniteFunction<VecKind> {
200        // mutably quotient self.hypergraph, returning the coequalizer q
201        let q = self.hypergraph.quotient();
202
203        // note: this is composition of finite functions `q >> self.sources`,
204        // but we do it mutably in-place.
205        self.sources
206            .iter_mut()
207            .for_each(|x| *x = NodeId(q.table[x.0]));
208        self.targets
209            .iter_mut()
210            .for_each(|x| *x = NodeId(q.table[x.0]));
211
212        q
213    }
214
215    /// Convert this *lax* [`OpenHypergraph`] to a strict [`crate::strict::OpenHypergraph`] by
216    /// quotienting.
217    pub fn to_strict(mut self) -> crate::strict::OpenHypergraph<VecKind, O, A> {
218        use crate::array::vec::VecArray;
219        use crate::finite_function::FiniteFunction;
220        use crate::strict::open_hypergraph::OpenHypergraph;
221
222        self.quotient();
223
224        let target = self.hypergraph.nodes.len();
225
226        let s = {
227            let table = self.sources.iter().map(|x| x.0).collect();
228            FiniteFunction::new(VecArray(table), target).expect("Valid by construction")
229        };
230
231        let t = {
232            let table = self.targets.iter().map(|x| x.0).collect();
233            FiniteFunction::new(VecArray(table), target).expect("Valid by construction")
234        };
235
236        let h = self.hypergraph.to_hypergraph();
237
238        OpenHypergraph::new(s, t, h).expect("any valid lax::Hypergraph must be quotientable!")
239    }
240
241    // Old name for `to_strict`. Provided for backwards compatibility
242    #[deprecated(since = "0.2.4", note = "renamed to_strict")]
243    pub fn to_open_hypergraph(self) -> crate::strict::OpenHypergraph<VecKind, O, A> {
244        self.to_strict()
245    }
246}
open_hypergraphs/lax/open_hypergraph.rs

open_hypergraphs/lax/
open_hypergraph.rs
