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

open_hypergraphs/lax/
hypergraph.rs
