catlog/dbl/
graph.rs

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

catlog/dbl/
graph.rs
