open_hypergraphs/lax/
open_hypergraph.rs

1//! Cospans of Hypergraphs.
2use super::hypergraph::*;
3
4/// A lax OpenHypergraph is a cospan of lax hypergraphs:
5/// a hypergraph equipped with two finite maps representing the *interfaces*.
6#[derive(Debug, Clone)]
7pub struct OpenHypergraph<O, A> {
8    pub sources: Vec<NodeId>,
9    pub targets: Vec<NodeId>,
10    pub hypergraph: Hypergraph<O, A>,
11}
12
13// Imperative-specific methods
14impl<O, A> OpenHypergraph<O, A> {
15    /// The empty OpenHypergraph with no nodes and no edges.
16    ///
17    /// In categorical terms, this is the identity map at the unit object.
18    pub fn empty() -> Self {
19        OpenHypergraph {
20            sources: vec![],
21            targets: vec![],
22            hypergraph: Hypergraph::empty(),
23        }
24    }
25
26    /// Create a new node in the hypergraph labeled `w`.
27    pub fn new_node(&mut self, w: O) -> NodeId {
28        self.hypergraph.new_node(w)
29    }
30
31    pub fn new_edge(&mut self, x: A, interface: Hyperedge) -> EdgeId {
32        self.hypergraph.new_edge(x, interface)
33    }
34
35    /// Create a new "operation" in the hypergraph.
36    /// Concretely, `f.new_operation(x, s, t)` mutates `f` by adding:
37    ///
38    /// 1. a new hyperedge labeled `x`
39    /// 2. `len(s)` new nodes, with the `i`th node labeled `s[i]`
40    /// 3. `len(t)` new nodes, with the `i`th node labeled `t[i]`
41    ///
42    /// Returns the new hyperedge ID and the [`NodeId`]s of the source/target nodes.
43    ///
44    /// This is a convenience wrapper for [`Hypergraph::new_operation`]
45    pub fn new_operation(
46        &mut self,
47        x: A,
48        source_type: Vec<O>,
49        target_type: Vec<O>,
50    ) -> (EdgeId, Interface) {
51        self.hypergraph.new_operation(x, source_type, target_type)
52    }
53
54    /// Compute an open hypergraph by calling `to_hypergraph` on the internal `Hypergraph`.
55    pub fn unify(&mut self, v: NodeId, w: NodeId) {
56        self.hypergraph.unify(v, w);
57    }
58
59    pub fn add_edge_source(&mut self, edge_id: EdgeId, w: O) -> NodeId {
60        self.hypergraph.add_edge_source(edge_id, w)
61    }
62
63    pub fn add_edge_target(&mut self, edge_id: EdgeId, w: O) -> NodeId {
64        self.hypergraph.add_edge_target(edge_id, w)
65    }
66}
67
68impl<O: Clone + PartialEq, A: Clone + PartialEq> OpenHypergraph<O, A> {
69    /// Apply the quotient map to identify nodes in the internal [`Hypergraph`].
70    /// This deletes the internal quotient map, resulting in a *strict* [`OpenHypergraph`].
71    pub fn quotient(&mut self) {
72        // mutably quotient self.hypergraph, returning the coequalizer q
73        let q = self.hypergraph.quotient();
74
75        // note: this is composition of finite functions `q >> self.sources`,
76        // but we do it mutably in-place.
77        self.sources
78            .iter_mut()
79            .for_each(|x| *x = NodeId(q.table[x.0]));
80        self.targets
81            .iter_mut()
82            .for_each(|x| *x = NodeId(q.table[x.0]));
83    }
84
85    /// Convert this *lax* [`OpenHypergraph`] to a strict [`crate::prelude::OpenHypergraph`] by
86    /// quotienting.
87    pub fn to_open_hypergraph(mut self) -> crate::prelude::OpenHypergraph<O, A> {
88        use crate::array::vec::VecArray;
89        use crate::finite_function::FiniteFunction;
90        use crate::open_hypergraph::OpenHypergraph;
91
92        self.quotient();
93
94        let target = self.hypergraph.nodes.len();
95
96        let s = {
97            let table = self.sources.iter().map(|x| x.0).collect();
98            FiniteFunction::new(VecArray(table), target).expect("Valid by construction")
99        };
100
101        let t = {
102            let table = self.targets.iter().map(|x| x.0).collect();
103            FiniteFunction::new(VecArray(table), target).expect("Valid by construction")
104        };
105
106        let h = self.hypergraph.to_hypergraph();
107
108        OpenHypergraph::new(s, t, h).expect("any valid lax::Hypergraph must be quotientable!")
109    }
110}
open_hypergraphs/lax/open_hypergraph.rs

open_hypergraphs/lax/
open_hypergraph.rs
