open_hypergraphs/lax/
hypergraph.rs

1use crate::array::vec::{VecArray, VecKind};
2use crate::finite_function::*;
3
4use core::fmt::Debug;
5
6#[derive(Debug, Clone, Copy, PartialEq, Eq, Hash)]
7#[cfg_attr(feature = "serde", derive(serde::Serialize, serde::Deserialize))]
8pub struct NodeId(pub usize);
9
10#[derive(Debug, Clone, Copy, PartialEq, Eq, Hash)]
11#[cfg_attr(feature = "serde", derive(serde::Serialize, serde::Deserialize))]
12pub struct EdgeId(pub usize);
13
14#[derive(Debug, Clone, PartialEq)]
15#[cfg_attr(feature = "serde", derive(serde::Serialize, serde::Deserialize))]
16pub struct Hyperedge {
17    pub sources: Vec<NodeId>,
18    pub targets: Vec<NodeId>,
19}
20
21pub type Interface = (Vec<NodeId>, Vec<NodeId>);
22
23/// A [`crate::lax::Hypergraph`] represents an "un-quotiented" hypergraph.
24///
25/// It can be thought of as a collection of disconnected operations and wires along with a
26/// *quotient map* which can be used with connected components to produce a `Hypergraph`.
27#[derive(Debug, Clone, PartialEq)]
28#[cfg_attr(feature = "serde", derive(serde::Serialize, serde::Deserialize))]
29#[cfg_attr(
30    feature = "serde",
31    serde(
32        bound = "O: serde::Serialize + serde::de::DeserializeOwned, A: serde::Serialize + serde::de::DeserializeOwned"
33    )
34)]
35pub struct Hypergraph<O, A> {
36    /// Node labels. Defines a finite map from [`NodeId`] to node label
37    pub nodes: Vec<O>,
38
39    /// Edge labels. Defines a finite map from [`EdgeId`] to edge label
40    pub edges: Vec<A>,
41
42    /// Hyperedges map an *ordered list* of source nodes to an ordered list of target nodes.
43    pub adjacency: Vec<Hyperedge>,
44
45    // A finite endofunction on the set of nodes, identifying nodes to be quotiented.
46    // NOTE: this is a *graph* on the set of nodes.
47    pub quotient: (Vec<NodeId>, Vec<NodeId>),
48}
49
50impl<O, A> Hypergraph<O, A> {
51    /// The empty Hypergraph with no nodes or edges.
52    pub fn empty() -> Self {
53        Hypergraph {
54            nodes: vec![],
55            edges: vec![],
56            adjacency: vec![],
57            quotient: (vec![], vec![]),
58        }
59    }
60
61    /// Check if the quotient map is empty: if so, then this is already a strict OpenHypergraph
62    pub fn is_strict(&self) -> bool {
63        self.quotient.0.is_empty()
64    }
65
66    pub fn from_strict(h: crate::strict::hypergraph::Hypergraph<VecKind, O, A>) -> Self {
67        let mut adjacency = Vec::with_capacity(h.x.0.len());
68        for (sources, targets) in h.s.into_iter().zip(h.t.into_iter()) {
69            adjacency.push(Hyperedge {
70                sources: sources.table.iter().map(|i| NodeId(*i)).collect(),
71                targets: targets.table.iter().map(|i| NodeId(*i)).collect(),
72            })
73        }
74
75        Hypergraph {
76            nodes: h.w.0 .0,
77            edges: h.x.0 .0,
78            adjacency,
79            quotient: (vec![], vec![]),
80        }
81    }
82
83    pub fn discrete(nodes: Vec<O>) -> Self {
84        let mut h = Self::empty();
85        h.nodes = nodes;
86        h
87    }
88
89    /// Add a single node labeled `w` to the [`Hypergraph`]
90    pub fn new_node(&mut self, w: O) -> NodeId {
91        let index = self.nodes.len();
92        self.nodes.push(w);
93        NodeId(index)
94    }
95
96    /// Add a single hyperedge labeled `a` to the [`Hypergraph`]
97    /// it has sources and targets specified by `interface`
98    /// return which `EdgeId` corresponds to that new hyperedge
99    pub fn new_edge(&mut self, x: A, interface: Hyperedge) -> EdgeId {
100        let edge_idx = self.edges.len();
101        self.edges.push(x);
102        self.adjacency.push(interface);
103        EdgeId(edge_idx)
104    }
105
106    /// Append a "singleton" operation to the Hypergraph.
107    ///
108    /// 1. For each element t of `source_type` (resp. `target_type`), creates a node labeled t
109    /// 2. creates An edge labeled `x`, and sets its source/target nodes to those from step (1)
110    ///
111    /// Returns the index [`EdgeId`] of the operation in the [`Hypergraph`], and its source and
112    /// target nodes.
113    pub fn new_operation(
114        &mut self,
115        x: A,
116        source_type: Vec<O>,
117        target_type: Vec<O>,
118    ) -> (EdgeId, Interface) {
119        let sources: Vec<NodeId> = source_type.into_iter().map(|t| self.new_node(t)).collect();
120        let targets: Vec<NodeId> = target_type.into_iter().map(|t| self.new_node(t)).collect();
121        let interface = (sources.clone(), targets.clone());
122        let edge_id = self.new_edge(x, Hyperedge { sources, targets });
123        (edge_id, interface)
124    }
125
126    /// Identify a pair of nodes `(v, w)` by adding them to the quotient map.
127    ///
128    /// Note that if the labels of `v` and `w` are not equal, then this will not represent a valid
129    /// `Hypergraph`.
130    /// This is intentional so that typechecking and type inference can be deferred until after
131    /// construction of the `Hypergraph`.
132    pub fn unify(&mut self, v: NodeId, w: NodeId) {
133        // add nodes to the quotient graph
134        self.quotient.0.push(v);
135        self.quotient.1.push(w);
136    }
137
138    /// Add a new *source* node labeled `w` to edge `edge_id`.
139    pub fn add_edge_source(&mut self, edge_id: EdgeId, w: O) -> NodeId {
140        let node_id = self.new_node(w);
141        self.adjacency[edge_id.0].sources.push(node_id);
142        node_id
143    }
144
145    /// Add a new *target* node labeled `w` to edge `edge_id`
146    pub fn add_edge_target(&mut self, edge_id: EdgeId, w: O) -> NodeId {
147        let node_id = self.new_node(w);
148        self.adjacency[edge_id.0].targets.push(node_id);
149        node_id
150    }
151
152    /// Set the nodes of a Hypergraph, possibly changing types.
153    /// Returns None if new nodes array had different length.
154    pub fn with_nodes<T, F: FnOnce(Vec<O>) -> Vec<T>>(self, f: F) -> Option<Hypergraph<T, A>> {
155        let n = self.nodes.len();
156        let nodes = f(self.nodes);
157        if nodes.len() != n {
158            return None;
159        }
160
161        Some(Hypergraph {
162            nodes,
163            edges: self.edges,
164            adjacency: self.adjacency,
165            quotient: self.quotient,
166        })
167    }
168
169    /// Map the node labels of this Hypergraph, possibly changing their type
170    pub fn map_nodes<F: Fn(O) -> T, T>(self, f: F) -> Hypergraph<T, A> {
171        // note: unwrap is safe because length is preserved
172        self.with_nodes(|nodes| nodes.into_iter().map(f).collect())
173            .unwrap()
174    }
175
176    /// Set the edges of a Hypergraph, possibly changing types.
177    /// Returns None if new edges array had different length.
178    pub fn with_edges<T, F: FnOnce(Vec<A>) -> Vec<T>>(self, f: F) -> Option<Hypergraph<O, T>> {
179        let n = self.edges.len();
180        let edges = f(self.edges);
181        if edges.len() != n {
182            return None;
183        }
184
185        Some(Hypergraph {
186            nodes: self.nodes,
187            edges,
188            adjacency: self.adjacency,
189            quotient: self.quotient,
190        })
191    }
192
193    /// Map the edge labels of this Hypergraph, possibly changing their type
194    pub fn map_edges<F: Fn(A) -> T, T>(self, f: F) -> Hypergraph<O, T> {
195        // note: unwrap is safe because length is preserved
196        self.with_edges(|edges| edges.into_iter().map(f).collect())
197            .unwrap()
198    }
199}
200
201impl<O: Clone + PartialEq, A: Clone> Hypergraph<O, A> {
202    /// Construct a [`Hypergraph`] by identifying nodes in the quotient map.
203    /// Mutably quotient this [`Hypergraph`], returning the coequalizer calculated from `self.quotient`.
204    ///
205    /// NOTE: this operation is unchecked; you should verify quotiented nodes have the exact same
206    /// type first, or this operation is undefined.
207    pub fn quotient(&mut self) -> FiniteFunction<VecKind> {
208        use std::mem::take;
209        let q = self.coequalizer();
210
211        self.nodes = coequalizer_universal(&q, &VecArray(take(&mut self.nodes)))
212            .unwrap()
213            .0;
214
215        // map hyperedges
216        for e in &mut self.adjacency {
217            e.sources.iter_mut().for_each(|x| *x = NodeId(q.table[x.0]));
218            e.targets.iter_mut().for_each(|x| *x = NodeId(q.table[x.0]));
219        }
220
221        // clear the quotient map (we just used it)
222        self.quotient = (vec![], vec![]); // empty
223
224        q // return the coequalizer used to quotient the hypergraph
225    }
226}
227
228impl<O: Clone, A: Clone> Hypergraph<O, A> {
229    pub fn to_hypergraph(&self) -> crate::strict::Hypergraph<VecKind, O, A> {
230        make_hypergraph(self)
231    }
232
233    pub fn coequalizer(&self) -> FiniteFunction<VecKind> {
234        // Compute the coequalizer (connected components) of the quotient graph
235        let s: FiniteFunction<VecKind> = FiniteFunction {
236            table: VecArray(self.quotient.0.iter().map(|x| x.0).collect()),
237            target: self.nodes.len(),
238        };
239
240        let t: FiniteFunction<VecKind> = FiniteFunction {
241            table: VecArray(self.quotient.1.iter().map(|x| x.0).collect()),
242            target: self.nodes.len(),
243        };
244
245        s.coequalizer(&t)
246            .expect("coequalizer must exist for any graph")
247    }
248}
249
250pub(crate) fn finite_function_coproduct(
251    v1: &[NodeId],
252    v2: &[NodeId],
253    target: usize,
254) -> Vec<NodeId> {
255    v1.iter()
256        .cloned()
257        .chain(v2.iter().map(|&s| NodeId(s.0 + target)))
258        .collect()
259}
260
261pub(crate) fn concat<T: Clone>(v1: &[T], v2: &[T]) -> Vec<T> {
262    v1.iter().cloned().chain(v2.iter().cloned()).collect()
263}
264
265impl<O: Clone, A: Clone> Hypergraph<O, A> {
266    pub(crate) fn coproduct(&self, other: &Hypergraph<O, A>) -> Hypergraph<O, A> {
267        let n = self.nodes.len();
268
269        let adjacency = self
270            .adjacency
271            .iter()
272            .cloned()
273            .chain(other.adjacency.iter().map(|edge| Hyperedge {
274                sources: edge.sources.iter().map(|&s| NodeId(s.0 + n)).collect(),
275                targets: edge.targets.iter().map(|&t| NodeId(t.0 + n)).collect(),
276            }))
277            .collect();
278
279        let quotient = (
280            finite_function_coproduct(&self.quotient.0, &other.quotient.0, n),
281            finite_function_coproduct(&self.quotient.1, &other.quotient.1, n),
282        );
283
284        Hypergraph {
285            nodes: concat(&self.nodes, &other.nodes),
286            edges: concat(&self.edges, &other.edges),
287            adjacency,
288            quotient,
289        }
290    }
291}
292
293/// Create a [`crate::strict::hypergraph::Hypergraph`] by forgetting about the quotient map.
294fn make_hypergraph<O: Clone, A: Clone>(
295    h: &Hypergraph<O, A>,
296) -> crate::strict::hypergraph::Hypergraph<VecKind, O, A> {
297    use crate::finite_function::*;
298    use crate::indexed_coproduct::*;
299    use crate::semifinite::*;
300
301    let s = {
302        let mut lengths = Vec::<usize>::with_capacity(h.edges.len());
303        let mut values = Vec::<usize>::new();
304        for e in h.adjacency.iter() {
305            lengths.push(e.sources.len());
306            values.extend(e.sources.iter().map(|x| x.0));
307        }
308
309        let sources = SemifiniteFunction(VecArray(lengths));
310        let values =
311            FiniteFunction::new(VecArray(values), h.nodes.len()).expect("invalid lax::Hypergraph!");
312        IndexedCoproduct::from_semifinite(sources, values).expect("valid IndexedCoproduct")
313    };
314
315    let t = {
316        let mut lengths = Vec::<usize>::with_capacity(h.edges.len());
317        let mut values = Vec::<usize>::new();
318        for e in h.adjacency.iter() {
319            lengths.push(e.targets.len());
320            values.extend(e.targets.iter().map(|x| x.0));
321        }
322
323        let sources = SemifiniteFunction(VecArray(lengths));
324        let values =
325            FiniteFunction::new(VecArray(values), h.nodes.len()).expect("invalid lax::Hypergraph!");
326        IndexedCoproduct::from_semifinite(sources, values).expect("valid IndexedCoproduct")
327    };
328
329    let w = SemifiniteFunction(VecArray(h.nodes.clone()));
330    let x = SemifiniteFunction(VecArray(h.edges.clone()));
331
332    crate::strict::hypergraph::Hypergraph { s, t, w, x }
333}
open_hypergraphs/lax/hypergraph.rs

open_hypergraphs/lax/
hypergraph.rs
