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
21/// Create a [`Hyperedge`] from a tuple of `(sources, targets)`.
22///
23/// This allows convenient creation of hyperedges from various collection types:
24/// ```
25/// # use open_hypergraphs::lax::{Hyperedge, NodeId};
26/// let edge: Hyperedge = (vec![NodeId(0), NodeId(1)], vec![NodeId(2)]).into();
27/// let edge: Hyperedge = ([NodeId(0), NodeId(1)], [NodeId(2)]).into();
28/// ```
29impl<S, T> From<(S, T)> for Hyperedge
30where
31    S: Into<Vec<NodeId>>,
32    T: Into<Vec<NodeId>>,
33{
34    fn from((sources, targets): (S, T)) -> Self {
35        Hyperedge {
36            sources: sources.into(),
37            targets: targets.into(),
38        }
39    }
40}
41
42pub type Interface = (Vec<NodeId>, Vec<NodeId>);
43
44/// A [`crate::lax::Hypergraph`] represents an "un-quotiented" hypergraph.
45///
46/// It can be thought of as a collection of disconnected operations and wires along with a
47/// *quotient map* which can be used with connected components to produce a `Hypergraph`.
48#[derive(Debug, Clone, PartialEq)]
49#[cfg_attr(feature = "serde", derive(serde::Serialize, serde::Deserialize))]
50#[cfg_attr(
51    feature = "serde",
52    serde(
53        bound = "O: serde::Serialize + serde::de::DeserializeOwned, A: serde::Serialize + serde::de::DeserializeOwned"
54    )
55)]
56pub struct Hypergraph<O, A> {
57    /// Node labels. Defines a finite map from [`NodeId`] to node label
58    pub nodes: Vec<O>,
59
60    /// Edge labels. Defines a finite map from [`EdgeId`] to edge label
61    pub edges: Vec<A>,
62
63    /// Hyperedges map an *ordered list* of source nodes to an ordered list of target nodes.
64    pub adjacency: Vec<Hyperedge>,
65
66    // A finite endofunction on the set of nodes, identifying nodes to be quotiented.
67    // NOTE: this is a *graph* on the set of nodes.
68    pub quotient: (Vec<NodeId>, Vec<NodeId>),
69}
70
71impl<O, A> Hypergraph<O, A> {
72    /// The empty Hypergraph with no nodes or edges.
73    pub fn empty() -> Self {
74        Hypergraph {
75            nodes: vec![],
76            edges: vec![],
77            adjacency: vec![],
78            quotient: (vec![], vec![]),
79        }
80    }
81
82    /// Check if the quotient map is empty: if so, then this is already a strict OpenHypergraph
83    pub fn is_strict(&self) -> bool {
84        self.quotient.0.is_empty()
85    }
86
87    pub fn from_strict(h: crate::strict::hypergraph::Hypergraph<VecKind, O, A>) -> Self {
88        let mut adjacency = Vec::with_capacity(h.x.0.len());
89        for (sources, targets) in h.s.into_iter().zip(h.t.into_iter()) {
90            adjacency.push(Hyperedge {
91                sources: sources.table.iter().map(|i| NodeId(*i)).collect(),
92                targets: targets.table.iter().map(|i| NodeId(*i)).collect(),
93            })
94        }
95
96        Hypergraph {
97            nodes: h.w.0 .0,
98            edges: h.x.0 .0,
99            adjacency,
100            quotient: (vec![], vec![]),
101        }
102    }
103
104    pub fn discrete(nodes: Vec<O>) -> Self {
105        let mut h = Self::empty();
106        h.nodes = nodes;
107        h
108    }
109
110    /// Add a single node labeled `w` to the [`Hypergraph`]
111    pub fn new_node(&mut self, w: O) -> NodeId {
112        let index = self.nodes.len();
113        self.nodes.push(w);
114        NodeId(index)
115    }
116
117    /// Add a single hyperedge labeled `a` to the [`Hypergraph`]
118    /// it has sources and targets specified by `interface`
119    /// return which `EdgeId` corresponds to that new hyperedge
120    pub fn new_edge(&mut self, x: A, interface: impl Into<Hyperedge>) -> EdgeId {
121        let edge_idx = self.edges.len();
122        self.edges.push(x);
123        self.adjacency.push(interface.into());
124        EdgeId(edge_idx)
125    }
126
127    /// Append a "singleton" operation to the Hypergraph.
128    ///
129    /// 1. For each element t of `source_type` (resp. `target_type`), creates a node labeled t
130    /// 2. creates An edge labeled `x`, and sets its source/target nodes to those from step (1)
131    ///
132    /// Returns the index [`EdgeId`] of the operation in the [`Hypergraph`], and its source and
133    /// target nodes.
134    pub fn new_operation(
135        &mut self,
136        x: A,
137        source_type: Vec<O>,
138        target_type: Vec<O>,
139    ) -> (EdgeId, Interface) {
140        let sources: Vec<NodeId> = source_type.into_iter().map(|t| self.new_node(t)).collect();
141        let targets: Vec<NodeId> = target_type.into_iter().map(|t| self.new_node(t)).collect();
142        let interface = (sources.clone(), targets.clone());
143        let edge_id = self.new_edge(x, Hyperedge { sources, targets });
144        (edge_id, interface)
145    }
146
147    /// Identify a pair of nodes `(v, w)` by adding them to the quotient map.
148    ///
149    /// Note that if the labels of `v` and `w` are not equal, then this will not represent a valid
150    /// `Hypergraph`.
151    /// This is intentional so that typechecking and type inference can be deferred until after
152    /// construction of the `Hypergraph`.
153    pub fn unify(&mut self, v: NodeId, w: NodeId) {
154        // add nodes to the quotient graph
155        self.quotient.0.push(v);
156        self.quotient.1.push(w);
157    }
158
159    /// Add a new *source* node labeled `w` to edge `edge_id`.
160    pub fn add_edge_source(&mut self, edge_id: EdgeId, w: O) -> NodeId {
161        let node_id = self.new_node(w);
162        self.adjacency[edge_id.0].sources.push(node_id);
163        node_id
164    }
165
166    /// Add a new *target* node labeled `w` to edge `edge_id`
167    pub fn add_edge_target(&mut self, edge_id: EdgeId, w: O) -> NodeId {
168        let node_id = self.new_node(w);
169        self.adjacency[edge_id.0].targets.push(node_id);
170        node_id
171    }
172
173    /// Set the nodes of a Hypergraph, possibly changing types.
174    /// Returns None if new nodes array had different length.
175    pub fn with_nodes<T, F: FnOnce(Vec<O>) -> Vec<T>>(self, f: F) -> Option<Hypergraph<T, A>> {
176        let n = self.nodes.len();
177        let nodes = f(self.nodes);
178        if nodes.len() != n {
179            return None;
180        }
181
182        Some(Hypergraph {
183            nodes,
184            edges: self.edges,
185            adjacency: self.adjacency,
186            quotient: self.quotient,
187        })
188    }
189
190    /// Map the node labels of this Hypergraph, possibly changing their type
191    pub fn map_nodes<F: Fn(O) -> T, T>(self, f: F) -> Hypergraph<T, A> {
192        // note: unwrap is safe because length is preserved
193        self.with_nodes(|nodes| nodes.into_iter().map(f).collect())
194            .unwrap()
195    }
196
197    /// Set the edges of a Hypergraph, possibly changing types.
198    /// Returns None if new edges array had different length.
199    pub fn with_edges<T, F: FnOnce(Vec<A>) -> Vec<T>>(self, f: F) -> Option<Hypergraph<O, T>> {
200        let n = self.edges.len();
201        let edges = f(self.edges);
202        if edges.len() != n {
203            return None;
204        }
205
206        Some(Hypergraph {
207            nodes: self.nodes,
208            edges,
209            adjacency: self.adjacency,
210            quotient: self.quotient,
211        })
212    }
213
214    /// Map the edge labels of this Hypergraph, possibly changing their type
215    pub fn map_edges<F: Fn(A) -> T, T>(self, f: F) -> Hypergraph<O, T> {
216        // note: unwrap is safe because length is preserved
217        self.with_edges(|edges| edges.into_iter().map(f).collect())
218            .unwrap()
219    }
220
221    /// Delete the specified edges and their adjacency information.
222    ///
223    /// Panics if any edge id is out of bounds.
224    pub fn delete_edge(&mut self, edge_ids: &[EdgeId]) {
225        let edge_count = self.edges.len();
226        assert_eq!(
227            edge_count,
228            self.adjacency.len(),
229            "malformed hypergraph: edges and adjacency lengths differ"
230        );
231
232        if edge_ids.is_empty() {
233            return;
234        }
235
236        let mut remove = vec![false; edge_count];
237        let mut any_removed = false;
238        let mut remove_count = 0usize;
239        for edge_id in edge_ids {
240            assert!(
241                edge_id.0 < edge_count,
242                "edge id {:?} is out of bounds",
243                edge_id
244            );
245            if !remove[edge_id.0] {
246                remove[edge_id.0] = true;
247                any_removed = true;
248                remove_count += 1;
249            }
250        }
251
252        if !any_removed {
253            return;
254        }
255
256        let mut edges = Vec::with_capacity(edge_count - remove_count);
257        let mut adjacency = Vec::with_capacity(edge_count - remove_count);
258        for (i, (edge, adj)) in self
259            .edges
260            .drain(..)
261            .zip(self.adjacency.drain(..))
262            .enumerate()
263        {
264            if !remove[i] {
265                edges.push(edge);
266                adjacency.push(adj);
267            }
268        }
269
270        self.edges = edges;
271        self.adjacency = adjacency;
272    }
273
274    /// Delete the specified nodes, remapping remaining node indices in adjacency and quotient.
275    ///
276    /// Panics if any node id is out of bounds.
277    pub fn delete_nodes(&mut self, node_ids: &[NodeId]) {
278        if node_ids.is_empty() {
279            return;
280        }
281
282        let node_count = self.nodes.len();
283        let mut remove = vec![false; node_count];
284        let mut any_removed = false;
285        let mut remove_count = 0usize;
286        for node_id in node_ids {
287            assert!(
288                node_id.0 < node_count,
289                "node id {:?} is out of bounds",
290                node_id
291            );
292            if !remove[node_id.0] {
293                remove[node_id.0] = true;
294                any_removed = true;
295                remove_count += 1;
296            }
297        }
298
299        if !any_removed {
300            return;
301        }
302
303        let mut new_index = vec![None; node_count];
304        let mut nodes = Vec::with_capacity(node_count - remove_count);
305        for (i, node) in self.nodes.drain(..).enumerate() {
306            if !remove[i] {
307                let next = nodes.len();
308                new_index[i] = Some(next);
309                nodes.push(node);
310            }
311        }
312        self.nodes = nodes;
313
314        for edge in &mut self.adjacency {
315            edge.sources = edge
316                .sources
317                .iter()
318                .filter_map(|node| new_index[node.0].map(NodeId))
319                .collect();
320            edge.targets = edge
321                .targets
322                .iter()
323                .filter_map(|node| new_index[node.0].map(NodeId))
324                .collect();
325        }
326
327        let mut quotient_left = Vec::with_capacity(self.quotient.0.len());
328        let mut quotient_right = Vec::with_capacity(self.quotient.1.len());
329        for (v, w) in self.quotient.0.iter().zip(self.quotient.1.iter()) {
330            if let (Some(v_new), Some(w_new)) = (new_index[v.0], new_index[w.0]) {
331                quotient_left.push(NodeId(v_new));
332                quotient_right.push(NodeId(w_new));
333            }
334        }
335        self.quotient = (quotient_left, quotient_right);
336    }
337}
338
339impl<O: Clone + PartialEq, A: Clone> Hypergraph<O, A> {
340    /// Construct a [`Hypergraph`] by identifying nodes in the quotient map.
341    /// Mutably quotient this [`Hypergraph`], returning the coequalizer calculated from `self.quotient`.
342    ///
343    /// NOTE: this operation is unchecked; you should verify quotiented nodes have the exact same
344    /// type first, or this operation is undefined.
345    pub fn quotient(&mut self) -> FiniteFunction<VecKind> {
346        use std::mem::take;
347        let q = self.coequalizer();
348
349        self.nodes = coequalizer_universal(&q, &VecArray(take(&mut self.nodes)))
350            .unwrap()
351            .0;
352
353        // map hyperedges
354        for e in &mut self.adjacency {
355            e.sources.iter_mut().for_each(|x| *x = NodeId(q.table[x.0]));
356            e.targets.iter_mut().for_each(|x| *x = NodeId(q.table[x.0]));
357        }
358
359        // clear the quotient map (we just used it)
360        self.quotient = (vec![], vec![]); // empty
361
362        q // return the coequalizer used to quotient the hypergraph
363    }
364}
365
366impl<O: Clone, A: Clone> Hypergraph<O, A> {
367    pub fn to_hypergraph(&self) -> crate::strict::Hypergraph<VecKind, O, A> {
368        make_hypergraph(self)
369    }
370
371    pub fn coequalizer(&self) -> FiniteFunction<VecKind> {
372        // Compute the coequalizer (connected components) of the quotient graph
373        let s: FiniteFunction<VecKind> = FiniteFunction {
374            table: VecArray(self.quotient.0.iter().map(|x| x.0).collect()),
375            target: self.nodes.len(),
376        };
377
378        let t: FiniteFunction<VecKind> = FiniteFunction {
379            table: VecArray(self.quotient.1.iter().map(|x| x.0).collect()),
380            target: self.nodes.len(),
381        };
382
383        s.coequalizer(&t)
384            .expect("coequalizer must exist for any graph")
385    }
386}
387
388pub(crate) fn finite_function_coproduct(
389    v1: &[NodeId],
390    v2: &[NodeId],
391    target: usize,
392) -> Vec<NodeId> {
393    v1.iter()
394        .cloned()
395        .chain(v2.iter().map(|&s| NodeId(s.0 + target)))
396        .collect()
397}
398
399pub(crate) fn concat<T: Clone>(v1: &[T], v2: &[T]) -> Vec<T> {
400    v1.iter().cloned().chain(v2.iter().cloned()).collect()
401}
402
403impl<O: Clone, A: Clone> Hypergraph<O, A> {
404    pub(crate) fn coproduct(&self, other: &Hypergraph<O, A>) -> Hypergraph<O, A> {
405        let n = self.nodes.len();
406
407        let adjacency = self
408            .adjacency
409            .iter()
410            .cloned()
411            .chain(other.adjacency.iter().map(|edge| Hyperedge {
412                sources: edge.sources.iter().map(|&s| NodeId(s.0 + n)).collect(),
413                targets: edge.targets.iter().map(|&t| NodeId(t.0 + n)).collect(),
414            }))
415            .collect();
416
417        let quotient = (
418            finite_function_coproduct(&self.quotient.0, &other.quotient.0, n),
419            finite_function_coproduct(&self.quotient.1, &other.quotient.1, n),
420        );
421
422        Hypergraph {
423            nodes: concat(&self.nodes, &other.nodes),
424            edges: concat(&self.edges, &other.edges),
425            adjacency,
426            quotient,
427        }
428    }
429}
430
431/// Create a [`crate::strict::hypergraph::Hypergraph`] by forgetting about the quotient map.
432fn make_hypergraph<O: Clone, A: Clone>(
433    h: &Hypergraph<O, A>,
434) -> crate::strict::hypergraph::Hypergraph<VecKind, O, A> {
435    use crate::finite_function::*;
436    use crate::indexed_coproduct::*;
437    use crate::semifinite::*;
438
439    let s = {
440        let mut lengths = Vec::<usize>::with_capacity(h.edges.len());
441        let mut values = Vec::<usize>::new();
442        for e in h.adjacency.iter() {
443            lengths.push(e.sources.len());
444            values.extend(e.sources.iter().map(|x| x.0));
445        }
446
447        let sources = SemifiniteFunction(VecArray(lengths));
448        let values =
449            FiniteFunction::new(VecArray(values), h.nodes.len()).expect("invalid lax::Hypergraph!");
450        IndexedCoproduct::from_semifinite(sources, values).expect("valid IndexedCoproduct")
451    };
452
453    let t = {
454        let mut lengths = Vec::<usize>::with_capacity(h.edges.len());
455        let mut values = Vec::<usize>::new();
456        for e in h.adjacency.iter() {
457            lengths.push(e.targets.len());
458            values.extend(e.targets.iter().map(|x| x.0));
459        }
460
461        let sources = SemifiniteFunction(VecArray(lengths));
462        let values =
463            FiniteFunction::new(VecArray(values), h.nodes.len()).expect("invalid lax::Hypergraph!");
464        IndexedCoproduct::from_semifinite(sources, values).expect("valid IndexedCoproduct")
465    };
466
467    let w = SemifiniteFunction(VecArray(h.nodes.clone()));
468    let x = SemifiniteFunction(VecArray(h.edges.clone()));
469
470    crate::strict::hypergraph::Hypergraph { s, t, w, x }
471}
open_hypergraphs/lax/hypergraph.rs

open_hypergraphs/lax/
hypergraph.rs
