catlog/dbl/
graph.rs

1//! Virtual double graphs.
2//!
3//! Analogous to how a graph is the combinatorial data that underlies a category, a
4//! virtual double graph* (nonstandard term) is the combinatorial data that
5//! underlies a virtual double category.
6//!
7//! In Leinster's terminology, a virtual double graph is called an *fc-graph*
8//! ([Leinster 2004](crate::refs::HigherOperads), Section 5.1). A virtual double
9//! graph is similar to a *double graph*, or two-dimensional semi-cubical set,
10//! except that the top boundary is a directed path of proedges rather than a single
11//! proedge.
12
13use derive_more::From;
14use ref_cast::RefCast;
15use thiserror::Error;
16
17use crate::one::{Graph, path::Path};
18
19/// A virtual double graph, the data underlying a virtual double category.
20///
21/// Following our nomenclature for double categories, we say that an edge in a
22/// double graph has a *domain* and *codomain*, whereas a proedge has a *source* and
23/// a *target*. A square has all four of those.
24pub trait VDblGraph {
25    /// Type of vertices.
26    type V: Eq + Clone;
27
28    /// Type of edges, in tight direction.
29    type E: Eq + Clone;
30
31    /// Type of "pro-edges", or edges in the loose direction.
32    type ProE: Eq + Clone;
33
34    /// Type of squares with multi-ary domain.
35    type Sq: Eq + Clone;
36
37    /// Does the vertex belong to the double graph?
38    fn has_vertex(&self, v: &Self::V) -> bool;
39
40    /// Does the edge belong to the double graph?
41    fn has_edge(&self, e: &Self::E) -> bool;
42
43    /// Does the proedge belong to the double graph?
44    fn has_proedge(&self, p: &Self::ProE) -> bool;
45
46    /// Does the square belong to the double graph?
47    fn has_square(&self, sq: &Self::Sq) -> bool;
48
49    /// Gets the domain of an edge.
50    fn dom(&self, e: &Self::E) -> Self::V;
51
52    /// Gets the codomain of an edge.
53    fn cod(&self, e: &Self::E) -> Self::V;
54
55    /// Gets the source of a proedge.
56    fn src(&self, p: &Self::ProE) -> Self::V;
57
58    /// Gets the target of a proedge.
59    fn tgt(&self, p: &Self::ProE) -> Self::V;
60
61    /// Gets the domain of a square, a path of proedges.
62    fn square_dom(&self, sq: &Self::Sq) -> Path<Self::V, Self::ProE>;
63
64    /// Gets the codomain of a square, a single proedge.
65    fn square_cod(&self, sq: &Self::Sq) -> Self::ProE;
66
67    /// Gets the source of a square, an edge.
68    fn square_src(&self, sq: &Self::Sq) -> Self::E;
69
70    /// Gets the target of a square, an edge.
71    fn square_tgt(&self, sq: &Self::Sq) -> Self::E;
72
73    /// Gets the arity of a square.
74    ///
75    /// The default implementation returns the length of the square's domain.
76    fn arity(&self, sq: &Self::Sq) -> usize {
77        self.square_dom(sq).len()
78    }
79}
80
81/// The underlying graph of vertices and edges in a virtual double graph.
82///
83/// Compare with [`ProedgeGraph`].
84#[derive(From, RefCast)]
85#[repr(transparent)]
86pub struct EdgeGraph<VDG: VDblGraph>(VDG);
87
88impl<VDG: VDblGraph> Graph for EdgeGraph<VDG> {
89    type V = VDG::V;
90    type E = VDG::E;
91
92    fn has_vertex(&self, v: &Self::V) -> bool {
93        self.0.has_vertex(v)
94    }
95    fn has_edge(&self, e: &Self::E) -> bool {
96        self.0.has_edge(e)
97    }
98    fn src(&self, e: &Self::E) -> Self::V {
99        self.0.dom(e)
100    }
101    fn tgt(&self, e: &Self::E) -> Self::V {
102        self.0.cod(e)
103    }
104}
105
106/// The underlying graph of vertices and pro-edges in a virtual double graph.
107///
108/// Compare with [`EdgeGraph`].
109#[derive(From, RefCast)]
110#[repr(transparent)]
111pub struct ProedgeGraph<VDG: VDblGraph>(VDG);
112
113impl<VDG: VDblGraph> Graph for ProedgeGraph<VDG> {
114    type V = VDG::V;
115    type E = VDG::ProE;
116
117    fn has_vertex(&self, v: &Self::V) -> bool {
118        self.0.has_vertex(v)
119    }
120    fn has_edge(&self, e: &Self::E) -> bool {
121        self.0.has_proedge(e)
122    }
123    fn src(&self, e: &Self::E) -> Self::V {
124        self.0.src(e)
125    }
126    fn tgt(&self, e: &Self::E) -> Self::V {
127        self.0.tgt(e)
128    }
129}
130
131/// An invalid assignment in a virtual double graph.
132#[derive(Debug, Error)]
133pub enum InvalidVDblGraph<E, ProE, Sq> {
134    /// Edge with an invalid domain.
135    #[error("Domain of edge `{0}` is not a vertex in the double graph")]
136    Dom(E),
137
138    /// Edge with an invalid codomain.
139    #[error("Codomain of edge `{0}` is not a vertex in the double graph")]
140    Cod(E),
141
142    /// Proedge with an invalid source.
143    #[error("Source of proedge `{0}` is not a vertex in the double graph")]
144    Src(ProE),
145
146    /// Proedge with an invalid target.
147    #[error("Target of proedge `{0}` is not a vertex in the double graph")]
148    Tgt(ProE),
149
150    /// Square with an invalid domain.
151    #[error("Domain of square `{0}` is not a proedge in the double graph")]
152    SquareDom(Sq),
153
154    /// Square with an invalid codomain.
155    #[error("Codomain of square `{0}` is not a proedge in the double graph")]
156    SquareCod(Sq),
157
158    /// Square with an invalid source.
159    #[error("Source of square `{0}` is not an edge in the double graph")]
160    SquareSrc(Sq),
161
162    /// Square with an invalid target.
163    #[error("Target of cell `{0}` is not an edge in the double graph")]
164    SquareTgt(Sq),
165
166    /// Square with incompatible sides.
167    #[error("Square `{0}` has sides with incompatible endpoints")]
168    NotSquare(Sq),
169}
catlog/dbl/graph.rs

catlog/dbl/
graph.rs
