catlog/one/
graph.rs

1//! Graphs, finite and infinite.
2//!
3//! Graphs are the fundamental combinatorial structure in category theory and a
4//! basic building block for higher dimensional categories. We thus aim to provide a
5//! flexible set of traits and structs for graphs as they are used in category
6//! theory.
7
8use std::hash::Hash;
9
10use derivative::Derivative;
11use derive_more::{Constructor, From};
12use nonempty::NonEmpty;
13use ref_cast::RefCast;
14use thiserror::Error;
15use ustr::Ustr;
16
17use crate::validate::{self, Validate};
18use crate::zero::*;
19
20/// A graph.
21///
22/// This is a graph in the category theorist's sense, i.e., it is directed and
23/// admits multiple edges and self loops. Moreover, a graph is not assumed to be
24/// finite, even locally.
25pub trait Graph {
26    /// Type of vertices in graph.
27    type V: Eq + Clone;
28
29    /// Type of edges in graph.
30    type E: Eq + Clone;
31
32    /// Does the graph contain the value as a vertex?
33    fn has_vertex(&self, v: &Self::V) -> bool;
34
35    /// Does the graph contain the value as an edge?
36    fn has_edge(&self, e: &Self::E) -> bool;
37
38    /// Gets the source of an edge, assumed to be contained in the graph.
39    fn src(&self, e: &Self::E) -> Self::V;
40
41    /// Gets the target of an edge, assumed to be contained in the graph.
42    fn tgt(&self, e: &Self::E) -> Self::V;
43}
44
45/// A graph with finitely many vertices and edges.
46pub trait FinGraph: Graph {
47    /// Iterates over the vertices in the graph.
48    fn vertices(&self) -> impl Iterator<Item = Self::V>;
49
50    /// Iterates over the edges in the graph.
51    fn edges(&self) -> impl Iterator<Item = Self::E>;
52
53    /// Iterates over the edges incoming to a vertex.
54    ///
55    /// Depending on whether the target map is indexed, this method can be cheap or
56    /// expensive.
57    fn in_edges(&self, v: &Self::V) -> impl Iterator<Item = Self::E> {
58        self.edges().filter(|e| self.tgt(e) == *v)
59    }
60
61    /// Iterates over the edges outgoing from a vertex.
62    ///
63    /// Depending on whether the source map is indexed, this method can be cheap or
64    /// expensive.
65    fn out_edges(&self, v: &Self::V) -> impl Iterator<Item = Self::E> {
66        self.edges().filter(|e| self.src(e) == *v)
67    }
68
69    /// Iterates over neighbors of a vertex connected by an outgoing edge.
70    ///
71    /// When multiple edges are present, neighboring vertices are repeated.
72    fn out_neighbors(&self, v: &Self::V) -> impl Iterator<Item = Self::V> {
73        self.out_edges(v).map(|e| self.tgt(&e))
74    }
75
76    /// Iterates over neighbors of a vertex connected by an incoming edge.
77    ///
78    /// When multiple edges are present, neighboring vertices are repeated.
79    fn in_neighbors(&self, v: &Self::V) -> impl Iterator<Item = Self::V> {
80        self.in_edges(v).map(|e| self.src(&e))
81    }
82
83    /// Number of vertices in the graph.
84    fn vertex_count(&self) -> usize {
85        self.vertices().count()
86    }
87
88    /// Number of edges in the graph.
89    fn edge_count(&self) -> usize {
90        self.edges().count()
91    }
92
93    /// Number of edges incoming to a vertex.
94    fn in_degree(&self, v: &Self::V) -> usize {
95        self.in_edges(v).count()
96    }
97
98    /// Number of edges outgoing from a vertex.
99    fn out_degree(&self, v: &Self::V) -> usize {
100        self.out_edges(v).count()
101    }
102
103    /// Number of edges incoming to or outgoing from a vertex.
104    ///
105    /// Self-loops are counted twice.
106    fn degree(&self, v: &Self::V) -> usize {
107        self.in_degree(v) + self.out_degree(v)
108    }
109}
110
111/// A reflexive graph.
112///
113/// A **reflexive graph** is a graph equipped with a distinguished self-loop on each vertex.
114pub trait ReflexiveGraph: Graph {
115    /// Gets the reflexive loop at a vertex.
116    fn refl(&self, v: Self::V) -> Self::E;
117}
118
119/// The set of vertices of a graph.
120#[derive(From, RefCast)]
121#[repr(transparent)]
122pub struct VertexSet<G>(G);
123
124impl<G: Graph> Set for VertexSet<G> {
125    type Elem = G::V;
126
127    fn contains(&self, v: &Self::Elem) -> bool {
128        self.0.has_vertex(v)
129    }
130}
131
132impl<G: FinGraph> FinSet for VertexSet<G> {
133    fn iter(&self) -> impl Iterator<Item = Self::Elem> {
134        self.0.vertices()
135    }
136    fn len(&self) -> usize {
137        self.0.vertex_count()
138    }
139}
140
141/// A graph backed by sets and mappings.
142///
143/// Such a graph is defined in copresheaf style by two [sets](Set) and two
144/// [mappings](Mapping). Implementing this trait provides a *blanket implementation*
145/// of [`Graph`]. This is the easiest way to define a new graph type.
146///
147/// This trait does not assume that the graph is mutable; for that, you must also
148/// implement the trait [`MutColumnarGraph`].
149pub trait ColumnarGraph {
150    /// Type of vertices in the graph.
151    type V: Eq + Clone;
152
153    /// Type of edges in the graph.
154    type E: Eq + Clone;
155
156    /// The set of vertices.
157    type Vertices: Set<Elem = Self::V>;
158
159    /// The set of edges.
160    type Edges: Set<Elem = Self::E>;
161
162    /// The map assigning each edge its source vertex.
163    type Src: Mapping<Dom = Self::E, Cod = Self::V>;
164
165    /// The map assigning each edge its target vertex.
166    type Tgt: Mapping<Dom = Self::E, Cod = Self::V>;
167
168    /// Gets the set of vertices.
169    fn vertex_set(&self) -> &Self::Vertices;
170
171    /// Gets the set of edges.
172    fn edge_set(&self) -> &Self::Edges;
173
174    /// Gets the mapping assigning a source vertex to each edge.
175    fn src_map(&self) -> &Self::Src;
176
177    /// Gets the mapping assignment a target vertex to each edge.
178    fn tgt_map(&self) -> &Self::Tgt;
179
180    /// Iterates over failures to be a valid graph.
181    fn iter_invalid(&self) -> impl Iterator<Item = InvalidGraph<Self::E>>
182    where
183        Self::Edges: FinSet<Elem = Self::E>,
184    {
185        let (dom, cod) = (self.edge_set(), self.vertex_set());
186        let srcs = Function(self.src_map(), dom, cod)
187            .iter_invalid()
188            .map(|e| InvalidGraph::Src(e.take()));
189        let tgts = Function(self.tgt_map(), dom, cod)
190            .iter_invalid()
191            .map(|e| InvalidGraph::Tgt(e.take()));
192        srcs.chain(tgts)
193    }
194}
195
196/// A finite graph backed by columns.
197///
198/// Such a graph is defined in copresheaf style by two [finite sets](FinSet) and two
199/// [columns](Column). Implementing this trait provides a *blanket implementation*
200/// of [`FinGraph`].
201pub trait ColumnarFinGraph:
202    ColumnarGraph<
203        Vertices: FinSet<Elem = Self::V>,
204        Edges: FinSet<Elem = Self::E>,
205        Src: Column<Dom = Self::E, Cod = Self::V>,
206        Tgt: Column<Dom = Self::E, Cod = Self::V>,
207    >
208{
209}
210
211/// A columnar graph with mutable columns.
212pub trait MutColumnarGraph:
213    ColumnarGraph<
214        Src: MutMapping<Dom = Self::E, Cod = Self::V>,
215        Tgt: MutMapping<Dom = Self::E, Cod = Self::V>,
216    >
217{
218    /// Variant of [`src_map`](ColumnarGraph::src_map) that returns a mutable
219    /// reference.
220    fn src_map_mut(&mut self) -> &mut Self::Src;
221
222    /// Variant of [`tgt_map`](ColumnarGraph::tgt_map) that returns a mutable
223    /// reference.
224    fn tgt_map_mut(&mut self) -> &mut Self::Tgt;
225
226    /// Gets the source of an edge, possibly undefined.
227    fn get_src(&self, e: &Self::E) -> Option<&Self::V> {
228        self.src_map().get(e)
229    }
230
231    /// Gets the target of an edge, possibly undefined.
232    fn get_tgt(&self, e: &Self::E) -> Option<&Self::V> {
233        self.tgt_map().get(e)
234    }
235
236    /// Sets the source of an edge.
237    fn set_src(&mut self, e: Self::E, v: Self::V) -> Option<Self::V> {
238        self.src_map_mut().set(e, v)
239    }
240
241    /// Sets the target of an edge.
242    fn set_tgt(&mut self, e: Self::E, v: Self::V) -> Option<Self::V> {
243        self.tgt_map_mut().set(e, v)
244    }
245}
246
247impl<G: ColumnarGraph> Graph for G {
248    type V = G::V;
249    type E = G::E;
250
251    fn has_vertex(&self, v: &Self::V) -> bool {
252        self.vertex_set().contains(v)
253    }
254    fn has_edge(&self, e: &Self::E) -> bool {
255        self.edge_set().contains(e)
256    }
257    fn src(&self, e: &Self::E) -> Self::V {
258        self.src_map().apply_to_ref(e).expect("Source of edge should be set")
259    }
260    fn tgt(&self, e: &Self::E) -> Self::V {
261        self.tgt_map().apply_to_ref(e).expect("Target of edge should be set")
262    }
263}
264
265impl<G: ColumnarFinGraph> FinGraph for G {
266    fn vertices(&self) -> impl Iterator<Item = Self::V> {
267        self.vertex_set().iter()
268    }
269    fn edges(&self) -> impl Iterator<Item = Self::E> {
270        self.edge_set().iter()
271    }
272    fn in_edges(&self, v: &Self::V) -> impl Iterator<Item = Self::E> {
273        self.tgt_map().preimage(v)
274    }
275    fn out_edges(&self, v: &Self::V) -> impl Iterator<Item = Self::E> {
276        self.src_map().preimage(v)
277    }
278    fn vertex_count(&self) -> usize {
279        self.vertex_set().len()
280    }
281    fn edge_count(&self) -> usize {
282        self.edge_set().len()
283    }
284}
285
286/// An invalid assignment in a graph.
287///
288/// For [columnar graphs](ColumnarGraph) and other graphs defined explicitly by
289/// data, it is possible that the data is incomplete or inconsistent.
290#[derive(Debug, Error)]
291pub enum InvalidGraph<E> {
292    /// Edge assigned a source that is not a vertex contained in the graph.
293    #[error("Source of edge `{0}` is not a vertex in the graph")]
294    Src(E),
295
296    /// Edge assigned a target that is not a vertex contained in the graph.
297    #[error("Target of edge `{0}` is not a vertex in the graph")]
298    Tgt(E),
299}
300
301/// A skeletal finite graph with indexed source and target maps.
302///
303/// The data structure is the same as the standard `Graph` type in
304/// [Catlab.jl](https://github.com/AlgebraicJulia/Catlab.jl).
305#[derive(Clone, Default, PartialEq, Eq)]
306pub struct SkelGraph {
307    nv: usize,
308    ne: usize,
309    src_map: SkelIndexedColumn,
310    tgt_map: SkelIndexedColumn,
311}
312
313impl ColumnarGraph for SkelGraph {
314    type V = usize;
315    type E = usize;
316
317    type Vertices = SkelFinSet;
318    type Edges = SkelFinSet;
319    type Src = SkelIndexedColumn;
320    type Tgt = SkelIndexedColumn;
321
322    fn vertex_set(&self) -> &Self::Vertices {
323        SkelFinSet::ref_cast(&self.nv)
324    }
325    fn edge_set(&self) -> &Self::Edges {
326        SkelFinSet::ref_cast(&self.ne)
327    }
328    fn src_map(&self) -> &Self::Src {
329        &self.src_map
330    }
331    fn tgt_map(&self) -> &Self::Tgt {
332        &self.tgt_map
333    }
334}
335
336impl MutColumnarGraph for SkelGraph {
337    fn src_map_mut(&mut self) -> &mut Self::Src {
338        &mut self.src_map
339    }
340    fn tgt_map_mut(&mut self) -> &mut Self::Tgt {
341        &mut self.tgt_map
342    }
343}
344
345impl ColumnarFinGraph for SkelGraph {}
346
347impl SkelGraph {
348    /// Adds a new vertex to the graph and returns it.
349    pub fn add_vertex(&mut self) -> usize {
350        let v = self.nv;
351        self.nv += 1;
352        v
353    }
354
355    /// Adds `n` new vertices to the graphs and returns them.
356    pub fn add_vertices(&mut self, n: usize) -> std::ops::Range<usize> {
357        let start = self.nv;
358        self.nv += n;
359        start..(self.nv)
360    }
361
362    /// Adds a new edge to the graph and returns it.
363    pub fn add_edge(&mut self, src: usize, tgt: usize) -> usize {
364        let e = self.make_edge();
365        self.src_map.set(e, src);
366        self.tgt_map.set(e, tgt);
367        e
368    }
369
370    /// Adds a new edge without initializing its source or target.
371    pub fn make_edge(&mut self) -> usize {
372        let e = self.ne;
373        self.ne += 1;
374        e
375    }
376
377    /// Makes a path graph with `n` vertices.
378    #[cfg(test)]
379    pub fn path(n: usize) -> Self {
380        let mut g: Self = Default::default();
381        g.add_vertices(n);
382        for (i, j) in std::iter::zip(0..(n - 1), 1..n) {
383            g.add_edge(i, j);
384        }
385        g
386    }
387
388    /// Makes a triangle graph (2-simplex).
389    #[cfg(test)]
390    pub fn triangle() -> Self {
391        let mut g: Self = Default::default();
392        g.add_vertices(3);
393        g.add_edge(0, 1);
394        g.add_edge(1, 2);
395        g.add_edge(0, 2);
396        g
397    }
398
399    /// Make a cycle graph with `n` vertices.
400    #[cfg(test)]
401    pub fn cycle(n: usize) -> Self {
402        assert!(n > 0);
403        let mut g = SkelGraph::path(n);
404        g.add_edge(n - 1, 0);
405        g
406    }
407}
408
409impl Validate for SkelGraph {
410    type ValidationError = InvalidGraph<usize>;
411
412    fn validate(&self) -> Result<(), NonEmpty<Self::ValidationError>> {
413        validate::wrap_errors(self.iter_invalid())
414    }
415}
416
417/// A finite graph with indexed source and target maps, based on hash maps.
418///
419/// Unlike in a skeletal finite graph, the vertices and edges can have arbitrary
420/// hashable types.
421#[derive(Clone, Derivative, Debug)]
422#[derivative(PartialEq(bound = "V: Eq + Hash, E: Eq + Hash"))]
423#[derivative(Eq(bound = "V: Eq + Hash, E: Eq + Hash"))]
424#[derivative(Default(bound = ""))]
425pub struct HashGraph<V, E> {
426    vertex_set: HashFinSet<V>,
427    edge_set: HashFinSet<E>,
428    src_map: IndexedHashColumn<E, V>,
429    tgt_map: IndexedHashColumn<E, V>,
430}
431
432/// A finite graph with vertices and edges of type `Ustr`.
433pub type UstrGraph = HashGraph<Ustr, Ustr>;
434
435impl<V, E> ColumnarGraph for HashGraph<V, E>
436where
437    V: Eq + Hash + Clone,
438    E: Eq + Hash + Clone,
439{
440    type V = V;
441    type E = E;
442
443    type Vertices = HashFinSet<V>;
444    type Edges = HashFinSet<E>;
445    type Src = IndexedHashColumn<E, V>;
446    type Tgt = IndexedHashColumn<E, V>;
447
448    fn vertex_set(&self) -> &Self::Vertices {
449        &self.vertex_set
450    }
451    fn edge_set(&self) -> &Self::Edges {
452        &self.edge_set
453    }
454    fn src_map(&self) -> &Self::Src {
455        &self.src_map
456    }
457    fn tgt_map(&self) -> &Self::Tgt {
458        &self.tgt_map
459    }
460}
461
462impl<V, E> MutColumnarGraph for HashGraph<V, E>
463where
464    V: Eq + Hash + Clone,
465    E: Eq + Hash + Clone,
466{
467    fn src_map_mut(&mut self) -> &mut Self::Src {
468        &mut self.src_map
469    }
470    fn tgt_map_mut(&mut self) -> &mut Self::Tgt {
471        &mut self.tgt_map
472    }
473}
474
475impl<V, E> ColumnarFinGraph for HashGraph<V, E>
476where
477    V: Eq + Hash + Clone,
478    E: Eq + Hash + Clone,
479{
480}
481
482impl<V, E> HashGraph<V, E>
483where
484    V: Eq + Hash + Clone,
485    E: Eq + Hash + Clone,
486{
487    /// Adds a vertex to the graph, returning whether the vertex is new.
488    pub fn add_vertex(&mut self, v: V) -> bool {
489        self.vertex_set.insert(v)
490    }
491
492    /// Adds multiple vertices to the graph.
493    pub fn add_vertices<T>(&mut self, iter: T)
494    where
495        T: IntoIterator<Item = V>,
496    {
497        self.vertex_set.extend(iter)
498    }
499
500    /// Adds an edge to the graph, returning whether the edge is new.
501    ///
502    /// If the edge is not new, its source and target are updated.
503    pub fn add_edge(&mut self, e: E, src: V, tgt: V) -> bool {
504        self.src_map.set(e.clone(), src);
505        self.tgt_map.set(e.clone(), tgt);
506        self.make_edge(e)
507    }
508
509    /// Adds an edge without initializing its source or target.
510    pub fn make_edge(&mut self, e: E) -> bool {
511        self.edge_set.insert(e)
512    }
513}
514
515impl<V, E> Validate for HashGraph<V, E>
516where
517    V: Eq + Hash + Clone,
518    E: Eq + Hash + Clone,
519{
520    type ValidationError = InvalidGraph<E>;
521
522    fn validate(&self) -> Result<(), NonEmpty<Self::ValidationError>> {
523        validate::wrap_errors(self.iter_invalid())
524    }
525}
526
527/// A mapping between graphs.
528///
529/// Just as a [`Mapping`] is the data of a function without specified domain or
530/// codomain sets, a *graph mapping* is the data of a graph homomorphism without
531/// specified domain or codomain graphs. Turning this around, a *graph morphism* is
532/// a pair of graphs with a compatible graph mapping.
533///
534/// The data of a graph mapping is a pair of mappings, one on vertices and the other
535/// edges. Use a [`ColumnarGraphMapping`] to supply this data directly.
536pub trait GraphMapping {
537    /// Type of vertices in domain graph.
538    type DomV: Eq + Clone;
539
540    /// Type of edges in domain graph.
541    type DomE: Eq + Clone;
542
543    /// Type of vertices in codomain graph.
544    type CodV: Eq + Clone;
545
546    /// Type of edges in codomain graph.
547    type CodE: Eq + Clone;
548
549    /// Type of underlying mapping on vertices.
550    type VertexMap: Mapping<Dom = Self::DomV, Cod = Self::CodV>;
551
552    /// Type of underlying mapping on edges.
553    type EdgeMap: Mapping<Dom = Self::DomE, Cod = Self::CodE>;
554
555    /// Gets the underlying mapping on vertices.
556    fn vertex_map(&self) -> &Self::VertexMap;
557
558    /// Gets the underlying mapping on edges.
559    fn edge_map(&self) -> &Self::EdgeMap;
560
561    /// Applies the graph mapping at a vertex.
562    fn apply_vertex(&self, v: Self::DomV) -> Option<Self::CodV> {
563        self.vertex_map().apply(v)
564    }
565
566    /// Applies the graph mapping at an edge.
567    fn apply_edge(&self, e: Self::DomE) -> Option<Self::CodE> {
568        self.edge_map().apply(e)
569    }
570
571    /// Is the mapping defined at a vertex?
572    fn is_vertex_assigned(&self, v: &Self::DomV) -> bool {
573        self.vertex_map().is_set(v)
574    }
575
576    /// Is the mapping defined at an edge?
577    fn is_edge_assigned(&self, e: &Self::DomE) -> bool {
578        self.edge_map().is_set(e)
579    }
580}
581
582/// A homomorphism between graphs defined by a [mapping](GraphMapping).
583///
584/// This struct borrows its data to perform validation. The domain and codomain are
585/// assumed to be valid graphs. If that is in question, the graphs should be
586/// validated *before* validating this object.
587pub struct GraphMorphism<'a, Map, Dom, Cod>(pub &'a Map, pub &'a Dom, pub &'a Cod);
588
589impl<'a, Map, Dom, Cod> GraphMorphism<'a, Map, Dom, Cod>
590where
591    Map: GraphMapping,
592    Map::DomE: Clone,
593    Dom: FinGraph<V = Map::DomV, E = Map::DomE>,
594    Cod: Graph<V = Map::CodV, E = Map::CodE>,
595{
596    /// Iterates over failures of the mapping to be a graph homomorphism.
597    pub fn iter_invalid(
598        &self,
599    ) -> impl Iterator<Item = InvalidGraphMorphism<Map::DomV, Map::DomE>> + 'a + use<'a, Map, Dom, Cod>
600    {
601        let GraphMorphism(mapping, dom, cod) = *self;
602        let vertex_errors = dom.vertices().filter_map(|v| {
603            if mapping.vertex_map().apply_to_ref(&v).is_some_and(|w| cod.has_vertex(&w)) {
604                None
605            } else {
606                Some(InvalidGraphMorphism::Vertex(v))
607            }
608        });
609
610        let edge_errors = dom.edges().flat_map(|e| {
611            if let Some(f) = mapping.edge_map().apply_to_ref(&e)
612                && cod.has_edge(&f)
613            {
614                let mut errs = Vec::new();
615                if mapping.apply_vertex(dom.src(&e)).is_some_and(|v| v != cod.src(&f)) {
616                    errs.push(InvalidGraphMorphism::Src(e.clone()))
617                }
618                if mapping.apply_vertex(dom.tgt(&e)).is_some_and(|v| v != cod.tgt(&f)) {
619                    errs.push(InvalidGraphMorphism::Tgt(e.clone()))
620                }
621                return errs;
622            }
623            vec![InvalidGraphMorphism::Edge(e)]
624        });
625
626        vertex_errors.chain(edge_errors)
627    }
628}
629
630impl<Map, Dom, Cod> Validate for GraphMorphism<'_, Map, Dom, Cod>
631where
632    Map: GraphMapping,
633    Map::DomE: Clone,
634    Dom: FinGraph<V = Map::DomV, E = Map::DomE>,
635    Cod: Graph<V = Map::CodV, E = Map::CodE>,
636{
637    type ValidationError = InvalidGraphMorphism<Map::DomV, Map::DomE>;
638
639    fn validate(&self) -> Result<(), NonEmpty<Self::ValidationError>> {
640        validate::wrap_errors(self.iter_invalid())
641    }
642}
643
644/// A failure of a [mapping](GraphMapping) between graphs to define a graph
645/// homomorphism.
646#[derive(Debug, Error)]
647pub enum InvalidGraphMorphism<V, E> {
648    /// A vertex in the domain graph not mapped to a vertex in the codomain.
649    #[error("Vertex `{0}` is not mapped to a vertex in the codomain")]
650    Vertex(V),
651
652    /// An edge in the domain graph not mapped to an edge in the codomain.
653    #[error("Edge `{0}` is not mapped to an edge in the codomain")]
654    Edge(E),
655
656    /// An edge in the domain graph whose source is not preserved.
657    #[error("Mapping of edge `{0}` does not preserve its source")]
658    Src(E),
659
660    /// An edge in the domain graph whose target is not preserved.
661    #[error("Mapping of edge `{0}` does not preserve its target")]
662    Tgt(E),
663}
664
665/// A graph mapping backed by columns.
666///
667/// That is, the data of the graph mapping is defined by two columns. The mapping
668/// can be between arbitrary graphs with compatible vertex and edge types.
669#[derive(Clone, Debug, Default, PartialEq, Eq, Constructor)]
670pub struct ColumnarGraphMapping<VMap, EMap> {
671    vertex_map: VMap,
672    edge_map: EMap,
673}
674
675impl<VMap, EMap> GraphMapping for ColumnarGraphMapping<VMap, EMap>
676where
677    VMap: Mapping,
678    EMap: Mapping,
679{
680    type DomV = VMap::Dom;
681    type DomE = EMap::Dom;
682    type CodV = VMap::Cod;
683    type CodE = EMap::Cod;
684    type VertexMap = VMap;
685    type EdgeMap = EMap;
686
687    fn vertex_map(&self) -> &Self::VertexMap {
688        &self.vertex_map
689    }
690    fn edge_map(&self) -> &Self::EdgeMap {
691        &self.edge_map
692    }
693}
694
695/// A graph mapping between skeletal finite graphs, backed by vectors.
696pub type SkelGraphMapping = ColumnarGraphMapping<VecColumn<usize>, VecColumn<usize>>;
697
698impl SkelGraphMapping {
699    /// Constructs a graph mapping from a pair of vectors.
700    pub fn from_vec(vertex_map: Vec<usize>, edge_map: Vec<usize>) -> Self {
701        Self::new(VecColumn::new(vertex_map), VecColumn::new(edge_map))
702    }
703}
704
705/// An element in a graph.
706///
707/// This type plays no role in the core API for graphs but is useful on rare
708/// occasion when heterogeneous collection of vertices *and* edges is needed.
709#[derive(Clone, Debug, PartialEq, Eq)]
710pub enum GraphElem<V, E> {
711    /// A vertex in a graph.
712    Vertex(V),
713
714    /// An edge in a graph.
715    Edge(E),
716}
717
718#[cfg(test)]
719mod tests {
720    use super::*;
721
722    #[test]
723    fn skel_graph() {
724        let g = SkelGraph::triangle();
725        assert_eq!(g.vertex_count(), 3);
726        assert_eq!(g.edge_count(), 3);
727        assert_eq!(g.src(&1), 1);
728        assert_eq!(g.tgt(&1), 2);
729        assert_eq!(g.out_edges(&0).collect::<Vec<_>>(), vec![0, 2]);
730        assert_eq!(g.in_edges(&2).collect::<Vec<_>>(), vec![1, 2]);
731        assert_eq!(g.out_degree(&0), 2);
732        assert_eq!(g.in_degree(&2), 2);
733        assert_eq!(g.degree(&1), 2);
734    }
735
736    #[test]
737    fn hash_graph() {
738        let mut g: HashGraph<char, &str> = Default::default();
739        assert!(g.add_vertex('x'));
740        g.add_vertices(['y', 'z']);
741        assert!(g.add_edge("f", 'x', 'y'));
742        assert!(g.add_edge("g", 'y', 'z'));
743        assert!(g.make_edge("fg"));
744        g.set_src("fg", 'x');
745        g.set_tgt("fg", 'z');
746        assert_eq!(g.src(&"fg"), 'x');
747        assert_eq!(g.tgt(&"fg"), 'z');
748    }
749
750    #[test]
751    fn vertex_set() {
752        let set: VertexSet<_> = SkelGraph::triangle().into();
753        assert!(set.contains(&2));
754        assert_eq!(set.len(), 3);
755    }
756
757    #[test]
758    fn validate_columnar_graph() {
759        let mut g = SkelGraph::triangle();
760        assert!(g.validate().is_ok());
761        g.src_map.set(2, 3); // Vertex 3 doesn't exist yet.
762        assert!(g.validate().is_err());
763        assert_eq!(g.add_vertex(), 3); // OK, now it does!
764        assert!(g.validate().is_ok());
765    }
766
767    #[test]
768    fn validate_graph_morphism() {
769        let g = SkelGraph::path(3);
770        let h = SkelGraph::path(4);
771        let f = SkelGraphMapping::from_vec(vec![1, 2, 3], vec![1, 2]);
772        assert!(GraphMorphism(&f, &g, &h).validate().is_ok());
773
774        let f = SkelGraphMapping::from_vec(vec![1, 2, 3], vec![2, 1]); // Not a homomorphism.
775        assert!(GraphMorphism(&f, &g, &h).validate().is_err());
776    }
777}
catlog/one/graph.rs

catlog/one/
graph.rs
