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)]
7#[repr(transparent)]
8pub struct NodeId(pub usize);
9
10#[derive(Debug, Clone, Copy, PartialEq)]
11#[repr(transparent)]
12pub struct EdgeId(pub usize);
13
14#[derive(Debug, Clone)]
15pub struct Hyperedge {
16    pub sources: Vec<NodeId>,
17    pub targets: Vec<NodeId>,
18}
19
20pub type Interface = (Vec<NodeId>, Vec<NodeId>);
21
22/// A [`crate::lax::Hypergraph`] represents an "un-quotiented" hypergraph.
23///
24/// It can be thought of as a collection of disconnected operations and wires along with a
25/// *quotient map* which can be used with connected components to produce a `Hypergraph`.
26#[derive(Debug, Clone)]
27pub struct Hypergraph<O, A> {
28    /// Node labels. Defines a finite map from [`NodeId`] to node label
29    pub nodes: Vec<O>,
30
31    /// Edge labels. Defines a finite map from [`EdgeId`] to edge label
32    pub edges: Vec<A>,
33
34    /// Hyperedges map an *ordered list* of source nodes to an ordered list of target nodes.
35    pub adjacency: Vec<Hyperedge>,
36
37    // A finite endofunction on the set of nodes, identifying nodes to be quotiented.
38    // NOTE: this is a *graph* on the set of nodes.
39    pub quotient: (Vec<NodeId>, Vec<NodeId>),
40}
41
42impl<O, A> Hypergraph<O, A> {
43    /// The empty Hypergraph with no nodes or edges.
44    pub fn empty() -> Self {
45        Hypergraph {
46            nodes: vec![],
47            edges: vec![],
48            adjacency: vec![],
49            quotient: (vec![], vec![]),
50        }
51    }
52
53    /// Add a single node labeled `w` to the [`Hypergraph`]
54    pub fn new_node(&mut self, w: O) -> NodeId {
55        let index = self.nodes.len();
56        self.nodes.push(w);
57        NodeId(index)
58    }
59
60    /// Add a single hyperedge labeled `a` to the [`Hypergraph`]
61    /// it has sources and targets specified by `interface`
62    /// return which `EdgeId` corresponds to that new hyperedge
63    pub fn new_edge(&mut self, x: A, interface: Hyperedge) -> EdgeId {
64        let edge_idx = self.edges.len();
65        self.edges.push(x);
66        self.adjacency.push(interface);
67        EdgeId(edge_idx)
68    }
69
70    /// Append a "singleton" operation to the Hypergraph.
71    ///
72    /// 1. For each element t of `source_type` (resp. `target_type`), creates a node labeled t
73    /// 2. creates An edge labeled `x`, and sets its source/target nodes to those from step (1)
74    ///
75    /// Returns the index [`EdgeId`] of the operation in the [`Hypergraph`], and its source and
76    /// target nodes.
77    pub fn new_operation(
78        &mut self,
79        x: A,
80        source_type: Vec<O>,
81        target_type: Vec<O>,
82    ) -> (EdgeId, Interface) {
83        let sources: Vec<NodeId> = source_type.into_iter().map(|t| self.new_node(t)).collect();
84        let targets: Vec<NodeId> = target_type.into_iter().map(|t| self.new_node(t)).collect();
85        let interface = (sources.clone(), targets.clone());
86        let edge_id = self.new_edge(x, Hyperedge { sources, targets });
87        (edge_id, interface)
88    }
89
90    /// Identify a pair of nodes `(v, w)` by adding them to the quotient map.
91    ///
92    /// Note that if the labels of `v` and `w` are not equal, then this will not represent a valid
93    /// `Hypergraph`.
94    /// This is intentional so that typechecking and type inference can be deferred until after
95    /// construction of the `Hypergraph`.
96    pub fn unify(&mut self, v: NodeId, w: NodeId) {
97        // add nodes to the quotient graph
98        self.quotient.0.push(v);
99        self.quotient.1.push(w);
100    }
101
102    /// Add a new *source* node labeled `w` to edge `edge_id`.
103    pub fn add_edge_source(&mut self, edge_id: EdgeId, w: O) -> NodeId {
104        let node_id = self.new_node(w);
105        self.adjacency[edge_id.0].sources.push(node_id);
106        node_id
107    }
108
109    /// Add a new *target* node labeled `w` to edge `edge_id`
110    pub fn add_edge_target(&mut self, edge_id: EdgeId, w: O) -> NodeId {
111        let node_id = self.new_node(w);
112        self.adjacency[edge_id.0].targets.push(node_id);
113        node_id
114    }
115}
116
117impl<O: Clone + PartialEq, A: Clone + PartialEq> Hypergraph<O, A> {
118    /// Construct a [`Hypergraph`] by identifying nodes in the quotient map.
119    /// Mutably quotient this [`Hypergraph`], returning the coequalizer calculated from `self.quotient`.
120    ///
121    /// NOTE: this operation is unchecked; you should verify quotiented nodes have the exact same
122    /// type first, or this operation is undefined.
123    pub fn quotient(&mut self) -> FiniteFunction<VecKind> {
124        use std::mem::take;
125        let q = self.coequalizer();
126
127        self.nodes = coequalizer_universal(&q, &VecArray(take(&mut self.nodes)))
128            .unwrap()
129            .0;
130
131        // map hyperedges
132        for e in &mut self.adjacency {
133            e.sources.iter_mut().for_each(|x| *x = NodeId(q.table[x.0]));
134            e.targets.iter_mut().for_each(|x| *x = NodeId(q.table[x.0]));
135        }
136
137        // clear the quotient map (we just used it)
138        self.quotient = (vec![], vec![]); // empty
139
140        q // return the coequalizer used to quotient the hypergraph
141    }
142
143    pub fn to_hypergraph(&self) -> crate::prelude::Hypergraph<O, A> {
144        make_hypergraph(self)
145    }
146
147    fn coequalizer(&self) -> FiniteFunction<VecKind> {
148        // Compute the coequalizer (connected components) of the quotient graph
149        let s: FiniteFunction<VecKind> = FiniteFunction {
150            table: VecArray(self.quotient.0.iter().map(|x| x.0).collect()),
151            target: self.nodes.len(),
152        };
153
154        let t: FiniteFunction<VecKind> = FiniteFunction {
155            table: VecArray(self.quotient.1.iter().map(|x| x.0).collect()),
156            target: self.nodes.len(),
157        };
158
159        s.coequalizer(&t)
160            .expect("coequalizer must exist for any graph")
161    }
162}
163
164/// Create a [`crate::hypergraph::Hypergraph`] by forgetting about the quotient map.
165fn make_hypergraph<O: Clone, A: Clone>(
166    h: &Hypergraph<O, A>,
167) -> crate::hypergraph::Hypergraph<VecKind, O, A> {
168    use crate::finite_function::*;
169    use crate::indexed_coproduct::*;
170    use crate::semifinite::*;
171
172    let s = {
173        let mut lengths = Vec::<usize>::with_capacity(h.edges.len());
174        let mut values = Vec::<usize>::new();
175        for e in h.adjacency.iter() {
176            lengths.push(e.sources.len());
177            values.extend(e.sources.iter().map(|x| x.0));
178        }
179
180        let sources = SemifiniteFunction(VecArray(lengths));
181        let values =
182            FiniteFunction::new(VecArray(values), h.nodes.len()).expect("invalid lax::Hypergraph!");
183        IndexedCoproduct::from_semifinite(sources, values).expect("valid IndexedCoproduct")
184    };
185
186    let t = {
187        let mut lengths = Vec::<usize>::with_capacity(h.edges.len());
188        let mut values = Vec::<usize>::new();
189        for e in h.adjacency.iter() {
190            lengths.push(e.targets.len());
191            values.extend(e.targets.iter().map(|x| x.0));
192        }
193
194        let sources = SemifiniteFunction(VecArray(lengths));
195        let values =
196            FiniteFunction::new(VecArray(values), h.nodes.len()).expect("invalid lax::Hypergraph!");
197        IndexedCoproduct::from_semifinite(sources, values).expect("valid IndexedCoproduct")
198    };
199
200    let w = SemifiniteFunction(VecArray(h.nodes.clone()));
201    let x = SemifiniteFunction(VecArray(h.edges.clone()));
202
203    crate::hypergraph::Hypergraph { s, t, w, x }
204}
open_hypergraphs/lax/hypergraph.rs

open_hypergraphs/lax/
hypergraph.rs
