catlog/one/
graph.rs

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

catlog/one/
graph.rs
