open_hypergraphs/lax/
open_hypergraph.rs

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

open_hypergraphs/lax/
open_hypergraph.rs
