catlog/one/
path.rs

1/*! Paths in graphs and categories.
2
3The central data type is [`Path`]. In addition, this module provides a simple
4data type for [path equations](`PathEq`).
5*/
6
7use either::Either;
8use nonempty::{NonEmpty, nonempty};
9use std::ops::Range;
10use std::{collections::HashSet, hash::Hash};
11
12#[cfg(feature = "serde")]
13use serde::{Deserialize, Serialize};
14#[cfg(feature = "serde-wasm")]
15use tsify_next::Tsify;
16
17use super::graph::Graph;
18use crate::validate;
19
20/** A path in a [graph](Graph) or [category](crate::one::category::Category).
21
22This definition by cases can be compared with the perhaps more obvious
23definition:
24
25```
26struct Path<V, E> {
27    start: V,
28    end: V, // Optional: more symmetric but also more redundant.
29    seq: Vec<E>,
30}
31```
32
33Not only does the single struct store redundant (hence possibly inconsistent)
34information when the sequence of edges is nonempty, one will often need to do a
35case analysis on the edge sequence anyway to determine whether, say,
36[`fold`](std::iter::Iterator::fold) can be called or the result of
37[`reduce`](std::iter::Iterator::reduce) is valid. Thus, it seems better to reify
38the two cases in the data structure itself.
39*/
40#[derive(Clone, Debug, PartialEq, Eq, Hash)]
41#[cfg_attr(feature = "serde", derive(Serialize, Deserialize))]
42#[cfg_attr(feature = "serde", serde(tag = "tag", content = "content"))]
43#[cfg_attr(feature = "serde-wasm", derive(Tsify))]
44#[cfg_attr(feature = "serde-wasm", tsify(into_wasm_abi, from_wasm_abi))]
45pub enum Path<V, E> {
46    /// The identity, or empty, path at a vertex.
47    Id(V),
48
49    /// A nontrivial path, comprising a *non-empty* vector of consecutive edges.
50    Seq(NonEmpty<E>),
51}
52
53/// Converts an edge into a path of length one.
54impl<V, E> From<E> for Path<V, E> {
55    fn from(e: E) -> Self {
56        Path::single(e)
57    }
58}
59
60/// Converts the path into an iterater over its edges.
61impl<V, E> IntoIterator for Path<V, E> {
62    type Item = E;
63    type IntoIter = Either<std::iter::Empty<E>, <NonEmpty<E> as IntoIterator>::IntoIter>;
64
65    fn into_iter(self) -> Self::IntoIter {
66        match self {
67            Path::Id(_) => Either::Left(std::iter::empty()),
68            Path::Seq(edges) => Either::Right(edges.into_iter()),
69        }
70    }
71}
72
73impl<V, E> Path<V, E> {
74    /// Constructs the empty or identity path.
75    pub fn empty(v: V) -> Self {
76        Path::Id(v)
77    }
78
79    /// Constructs a path with a single edge.
80    pub fn single(e: E) -> Self {
81        Path::Seq(NonEmpty::singleton(e))
82    }
83
84    /// Constructs a pair of consecutive edges, or path of length 2.
85    pub fn pair(e: E, f: E) -> Self {
86        Path::Seq(nonempty![e, f])
87    }
88
89    /** Constructs a path from an iterator over edges.
90
91    Returns `None` if the iterator is empty.
92     */
93    pub fn collect<I>(iter: I) -> Option<Self>
94    where
95        I: IntoIterator<Item = E>,
96    {
97        NonEmpty::collect(iter).map(Path::Seq)
98    }
99
100    /** Constructs a path from a vector of edges.
101
102    Returns `None` if the vector is empty.
103     */
104    pub fn from_vec(vec: Vec<E>) -> Option<Self> {
105        NonEmpty::from_vec(vec).map(Path::Seq)
106    }
107
108    /** Constructs a path by repeating an edge `n` times.
109
110    The edge should have the same source and target, namely the first argument.
111     */
112    pub fn repeat_n(v: V, e: E, n: usize) -> Self
113    where
114        E: Clone,
115    {
116        Path::collect(std::iter::repeat_n(e, n)).unwrap_or_else(|| Path::empty(v))
117    }
118
119    /// Length of the path.
120    pub fn len(&self) -> usize {
121        match self {
122            Path::Id(_) => 0,
123            Path::Seq(edges) => edges.len(),
124        }
125    }
126
127    /// Is the path empty?
128    pub fn is_empty(&self) -> bool {
129        match self {
130            Path::Id(_) => true,
131            Path::Seq(_) => false,
132        }
133    }
134
135    /** Iterates over edges in the path, if any.
136
137    This method is a one-sided inverse to [`Path::collect`].
138     */
139    pub fn iter(&self) -> impl Iterator<Item = &E> {
140        match self {
141            Path::Id(_) => Either::Left(std::iter::empty()),
142            Path::Seq(edges) => Either::Right(edges.iter()),
143        }
144    }
145
146    /** Returns the unique edge in a path of length 1.
147
148    This method is a one-sided inverse to [`Path::single`].
149     */
150    pub fn only(self) -> Option<E> {
151        match self {
152            Path::Id(_) => None,
153            Path::Seq(edges) => {
154                if edges.tail.is_empty() {
155                    Some(edges.head)
156                } else {
157                    None
158                }
159            }
160        }
161    }
162
163    /// Inserts an edge into the path at the given index.
164    pub fn insert(&mut self, index: usize, edge: E) {
165        if let Path::Seq(edges) = self {
166            edges.insert(index, edge);
167        } else {
168            *self = Path::single(edge);
169        }
170    }
171
172    /// Splices a path into another path at the given range of indices.
173    pub fn splice(self, range: Range<usize>, replace_with: Self) -> Self {
174        let new_path = if range.start == 0 && range.end == self.len() {
175            Some(replace_with)
176        } else if let Path::Seq(edges) = self {
177            let mut edges: Vec<_> = edges.into();
178            edges.splice(range, replace_with);
179            Path::from_vec(edges)
180        } else {
181            None
182        };
183        new_path.expect("Range of indices into path should be valid")
184    }
185
186    /** Source of the path in the given graph.
187
188    Assumes that the path is [contained in](Path::contained_in) the graph.
189    */
190    pub fn src(&self, graph: &impl Graph<V = V, E = E>) -> V
191    where
192        V: Clone,
193    {
194        match self {
195            Path::Id(v) => v.clone(),
196            Path::Seq(edges) => graph.src(edges.first()),
197        }
198    }
199
200    /** Target of the path in the given graph.
201
202    Assumes that the path is [contained in](Path::contained_in) the graph.
203    */
204    pub fn tgt(&self, graph: &impl Graph<V = V, E = E>) -> V
205    where
206        V: Clone,
207    {
208        match self {
209            Path::Id(v) => v.clone(),
210            Path::Seq(edges) => graph.tgt(edges.last()),
211        }
212    }
213
214    /** Extracts a subpath of a path in a graph.
215
216    Panics if the range is invalid or an empty subpath would be inconsistent.
217     */
218    pub fn subpath(&self, graph: &impl Graph<V = V, E = E>, range: Range<usize>) -> Self
219    where
220        V: Eq + Clone,
221        E: Clone,
222    {
223        if let Path::Seq(edges) = self {
224            if range.is_empty() {
225                let index = range.start;
226                let v = if index == 0 {
227                    graph.src(edges.first())
228                } else if index == edges.len() {
229                    graph.tgt(edges.last())
230                } else if index < edges.len() {
231                    let (t, s) = (graph.tgt(&(*edges)[index - 1]), graph.src(&(*edges)[index]));
232                    assert!(t == s, "Inconsistent intermediate vertex in path");
233                    t
234                } else {
235                    panic!("Invalid index for empty subpath of path");
236                };
237                Path::Id(v)
238            } else {
239                let (start, end) = (range.start, range.end);
240                let iter = if start == 0 {
241                    let head = std::iter::once(edges.head.clone());
242                    let tail = edges.tail[0..(end - 1)].iter().cloned();
243                    Either::Left(head.chain(tail))
244                } else {
245                    Either::Right(edges.tail[(start - 1)..(end - 1)].iter().cloned())
246                };
247                Path::collect(iter).unwrap()
248            }
249        } else {
250            assert!(range.start == 0 && range.is_empty(), "Invalid subpath of empty path");
251            self.clone()
252        }
253    }
254
255    /** Replaces the subpath at the given range with a function of that subpath.
256
257    Panics under the same conditions as [`subpath`](Self::subpath).
258     */
259    pub fn replace_subpath<F>(
260        self,
261        graph: &impl Graph<V = V, E = E>,
262        range: Range<usize>,
263        f: F,
264    ) -> Self
265    where
266        V: Eq + Clone,
267        E: Clone,
268        F: FnOnce(Self) -> Self,
269    {
270        let subpath = self.subpath(graph, range.clone());
271        self.splice(range, f(subpath))
272    }
273
274    /** Concatenates this path with another path in the graph.
275
276    This methods *checks* that the two paths are compatible (the target of this
277    path equals the source of the other path) and it *assumes* that both paths
278    are contained in the graph, which should be checked with
279    [`contained_in`](Self::contained_in) if in doubt. Thus, when returned, the
280    concatenated path is also a valid path.
281     */
282    pub fn concat_in(self, graph: &impl Graph<V = V, E = E>, other: Self) -> Option<Self>
283    where
284        V: Eq + Clone,
285    {
286        if self.tgt(graph) != other.src(graph) {
287            return None;
288        }
289        let concatenated = match (self, other) {
290            (path, Path::Id(_)) => path,
291            (Path::Id(_), path) => path,
292            (Path::Seq(mut edges), Path::Seq(mut other_edges)) => {
293                edges.push(other_edges.head);
294                edges.append(&mut other_edges.tail);
295                Path::Seq(edges)
296            }
297        };
298        Some(concatenated)
299    }
300
301    /// Is the path contained in the given graph?
302    pub fn contained_in(&self, graph: &impl Graph<V = V, E = E>) -> bool
303    where
304        V: Eq,
305    {
306        match self {
307            Path::Id(v) => graph.has_vertex(v),
308            Path::Seq(edges) => {
309                // All the edges exist in the graph...
310                edges.iter().all(|e| graph.has_edge(e)) &&
311                // ...and their sources and target are compatible.
312                std::iter::zip(edges.iter(), edges.iter().skip(1)).all(
313                    |(e,f)| graph.tgt(e) == graph.src(f))
314            }
315        }
316    }
317
318    /** Returns whether the path is simple.
319
320    On our definition, a path is **simple** if it has no repeated edges.
321     */
322    pub fn is_simple(&self) -> bool
323    where
324        E: Eq + Hash,
325    {
326        match self {
327            Path::Id(_) => true,
328            Path::Seq(edges) => {
329                let edges: HashSet<_> = edges.into_iter().collect();
330                edges.len() == self.len()
331            }
332        }
333    }
334
335    /// Reduces a path using functions on vertices and edges.
336    pub fn reduce<FnV, FnE>(self, fv: FnV, fe: FnE) -> E
337    where
338        FnV: FnOnce(V) -> E,
339        FnE: FnMut(E, E) -> E,
340    {
341        match self {
342            Path::Id(v) => fv(v),
343            // `reduce` cannot fail since edge sequence is nonempty.
344            Path::Seq(edges) => edges.into_iter().reduce(fe).unwrap(),
345        }
346    }
347
348    /// Maps a path over functions on vertices and edges.
349    pub fn map<CodV, CodE, FnV, FnE>(self, fv: FnV, fe: FnE) -> Path<CodV, CodE>
350    where
351        FnV: FnOnce(V) -> CodV,
352        FnE: FnMut(E) -> CodE,
353    {
354        match self {
355            Path::Id(v) => Path::Id(fv(v)),
356            Path::Seq(edges) => Path::Seq(edges.map(fe)),
357        }
358    }
359
360    /// Maps a path over partial functions on vertices and edges.
361    pub fn partial_map<CodV, CodE, FnV, FnE>(self, fv: FnV, fe: FnE) -> Option<Path<CodV, CodE>>
362    where
363        FnV: FnOnce(V) -> Option<CodV>,
364        FnE: FnMut(E) -> Option<CodE>,
365    {
366        match self {
367            Path::Id(v) => {
368                let w = fv(v)?;
369                Some(Path::Id(w))
370            }
371            Path::Seq(edges) => {
372                let edges: Option<Vec<_>> = edges.into_iter().map(fe).collect();
373                let edges = edges?;
374                Path::from_vec(edges)
375            }
376        }
377    }
378
379    /// Maps a path over fallible functions on vertices and edges.
380    pub fn try_map<CodV, CodE, FnV, FnE, Err>(
381        self,
382        fv: FnV,
383        fe: FnE,
384    ) -> Result<Path<CodV, CodE>, Err>
385    where
386        FnV: FnOnce(V) -> Result<CodV, Err>,
387        FnE: FnMut(E) -> Result<CodE, Err>,
388    {
389        match self {
390            Path::Id(v) => {
391                let w = fv(v)?;
392                Ok(Path::Id(w))
393            }
394            Path::Seq(edges) => {
395                let edges: Result<Vec<_>, _> = edges.into_iter().map(fe).collect();
396                let edges = edges?;
397                Ok(Path::from_vec(edges).unwrap())
398            }
399        }
400    }
401}
402
403impl<V, E> Path<V, Path<V, E>> {
404    /** Flattens a path of paths into a single path.
405
406    Unlike [`flatten_in`](Self::flatten_in), this method does not check that the
407    composite is well typed before computing it.
408     */
409    pub fn flatten(self) -> Path<V, E> {
410        match self {
411            Path::Id(x) => Path::Id(x),
412            Path::Seq(paths) => {
413                if paths.iter().any(|p| matches!(p, Path::Seq(_))) {
414                    // We either have at least one non-empty sequence...
415                    let edges = paths
416                        .into_iter()
417                        .filter_map(|p| match p {
418                            Path::Id(_) => None,
419                            Path::Seq(edges) => Some(edges),
420                        })
421                        .flatten();
422                    Path::Seq(NonEmpty::collect(edges).unwrap())
423                } else {
424                    // ...or else every path is an identity.
425                    paths.head
426                }
427            }
428        }
429    }
430
431    /** Flattens a path of paths in a graph into a single path.
432
433    Returns the flattened path just when the original paths have compatible
434    start and end points.
435     */
436    pub fn flatten_in(self, graph: &impl Graph<V = V, E = E>) -> Option<Path<V, E>>
437    where
438        V: Eq + Clone,
439    {
440        if let Path::Seq(paths) = &self {
441            let mut pairs = std::iter::zip(paths.iter(), paths.iter().skip(1));
442            if !pairs.all(|(p1, p2)| p1.tgt(graph) == p2.src(graph)) {
443                return None;
444            }
445        }
446        Some(self.flatten())
447    }
448}
449
450/// A path in a graph with skeletal vertex and edge sets.
451pub type SkelPath = Path<usize, usize>;
452
453/// Assertion of an equation between the composites of two paths in a category.
454#[derive(Clone, Debug, PartialEq, Eq)]
455pub struct PathEq<V, E> {
456    /// Left hand side of equation.
457    pub lhs: Path<V, E>,
458
459    /// Right hand side of equation.
460    pub rhs: Path<V, E>,
461}
462
463impl<V, E> PathEq<V, E> {
464    /// Constructs a path equation with the given left- and right-hand sides.
465    pub fn new(lhs: Path<V, E>, rhs: Path<V, E>) -> PathEq<V, E> {
466        PathEq { lhs, rhs }
467    }
468
469    /** Source of the path equation in the given graph.
470
471    Panics if the two sides of the path equation have different sources.
472    */
473    pub fn src(&self, graph: &impl Graph<V = V, E = E>) -> V
474    where
475        V: Eq + Clone,
476    {
477        let (x, y) = (self.lhs.src(graph), self.rhs.src(graph));
478        assert!(x == y, "Both sides of path equation should have same source");
479        x
480    }
481
482    /** Target of the path equation in the given graph.
483
484    Panics if the two sides of the path equation have different targets.
485    */
486    pub fn tgt(&self, graph: &impl Graph<V = V, E = E>) -> V
487    where
488        V: Eq + Clone,
489    {
490        let (x, y) = (self.lhs.tgt(graph), self.rhs.tgt(graph));
491        assert!(x == y, "Both sides of path equation should have same target");
492        x
493    }
494
495    /// Validates that the path equation is well defined in the given graph.
496    pub fn validate_in<G>(&self, graph: &G) -> Result<(), NonEmpty<InvalidPathEq>>
497    where
498        V: Eq + Clone,
499        G: Graph<V = V, E = E>,
500    {
501        validate::wrap_errors(self.iter_invalid_in(graph))
502    }
503
504    /// Iterators over failures of the path equation to be well defined.
505    pub fn iter_invalid_in<G>(
506        &self,
507        graph: &G,
508    ) -> impl Iterator<Item = InvalidPathEq> + use<G, V, E>
509    where
510        V: Eq + Clone,
511        G: Graph<V = V, E = E>,
512    {
513        let mut errs = Vec::new();
514        if !self.lhs.contained_in(graph) {
515            errs.push(InvalidPathEq::Lhs());
516        }
517        if !self.rhs.contained_in(graph) {
518            errs.push(InvalidPathEq::Rhs());
519        }
520        if errs.is_empty() {
521            if self.lhs.src(graph) != self.rhs.src(graph) {
522                errs.push(InvalidPathEq::Src());
523            }
524            if self.lhs.tgt(graph) != self.rhs.tgt(graph) {
525                errs.push(InvalidPathEq::Tgt());
526            }
527        }
528        errs.into_iter()
529    }
530}
531
532/// A failure of a path equation to be well defined in a graph.
533#[derive(Debug)]
534pub enum InvalidPathEq {
535    /// Path in left hand side of equation not contained in the graph.
536    Lhs(),
537
538    /// Path in right hand side of equation not contained in the graph.
539    Rhs(),
540
541    /// Sources of left and right hand sides of path equation are not equal.
542    Src(),
543
544    /// Targets of left and right hand sides of path equation are not equal.
545    Tgt(),
546}
547
548#[cfg(test)]
549mod tests {
550    use super::super::graph::SkelGraph;
551    use super::*;
552    use std::convert::identity;
553
554    #[test]
555    fn path_in_graph() {
556        let g = SkelGraph::triangle();
557        let path = Path::pair(0, 1);
558        assert_eq!(path.src(&g), 0);
559        assert_eq!(path.tgt(&g), 2);
560        assert_eq!(Path::single(0).concat_in(&g, Path::single(1)), Some(path));
561
562        assert!(Path::Id(2).contained_in(&g));
563        assert!(!Path::Id(3).contained_in(&g));
564        assert!(Path::pair(0, 1).contained_in(&g));
565        assert!(!Path::pair(1, 0).contained_in(&g));
566    }
567
568    #[test]
569    fn singleton_path() {
570        let e = 1;
571        assert_eq!(SkelPath::single(e).only(), Some(e));
572    }
573
574    #[test]
575    fn insert_into_path() {
576        let mut path = SkelPath::Id(0);
577        path.insert(0, 2);
578        assert_eq!(path, Path::single(2));
579        path.insert(0, 1);
580        assert_eq!(path, Path::pair(1, 2));
581
582        assert_eq!(SkelPath::empty(0).splice(0..0, Path::pair(0, 1)), Path::pair(0, 1));
583        assert_eq!(SkelPath::empty(0).splice(0..0, Path::empty(0)), Path::empty(0));
584        let target = SkelPath::Seq(nonempty![0, 1, 2]);
585        assert_eq!(Path::pair(0, 2).splice(1..1, Path::single(1)), target);
586        assert_eq!(Path::pair(0, 2).splice(1..2, Path::pair(1, 2)), target);
587        assert_eq!(target.clone().splice(1..3, Path::pair(1, 2)), target);
588        assert_eq!(target.clone().splice(1..1, Path::empty(0)), target);
589    }
590
591    #[test]
592    fn subpath() {
593        let g = SkelGraph::path(4);
594        assert_eq!(Path::Id(1).subpath(&g, 0..0), Path::Id(1));
595        let path = Path::Seq(nonempty![0, 1, 2]);
596        assert_eq!(path.subpath(&g, 0..0), Path::Id(0));
597        assert_eq!(path.subpath(&g, 1..1), Path::Id(1));
598        assert_eq!(path.subpath(&g, 3..3), Path::Id(3));
599        assert_eq!(path.subpath(&g, 0..2), Path::pair(0, 1));
600        assert_eq!(path.subpath(&g, 1..3), Path::pair(1, 2));
601    }
602
603    #[test]
604    fn map_path() {
605        let id = SkelPath::Id(1);
606        assert_eq!(id.iter().count(), 0);
607        assert_eq!(id.clone().into_iter().count(), 0);
608        assert_eq!(id.clone().map(|v| v + 1, identity), Path::Id(2));
609        assert_eq!(id.partial_map(|v| Some(v + 1), Some), Some(Path::Id(2)));
610
611        let pair = SkelPath::pair(0, 1);
612        assert_eq!(pair.iter().count(), 2);
613        assert_eq!(pair.clone().into_iter().count(), 2);
614        assert_eq!(pair.clone().map(identity, |e| e + 1), Path::pair(1, 2));
615        assert_eq!(pair.partial_map(Some, |e| Some(e + 1)), Some(Path::pair(1, 2)));
616    }
617
618    #[test]
619    fn path_eq() {
620        let g = SkelGraph::triangle();
621        let eq = PathEq::new(Path::pair(0, 1), Path::single(2));
622        assert_eq!(eq.src(&g), 0);
623        assert_eq!(eq.tgt(&g), 2);
624        assert!(eq.validate_in(&g).is_ok());
625    }
626
627    #[test]
628    fn path_is_simple() {
629        assert!(SkelPath::pair(0, 1).is_simple());
630        assert!(!SkelPath::pair(0, 0).is_simple());
631        assert!(SkelPath::Id(0).is_simple());
632    }
633}
catlog/one/path.rs

catlog/one/
path.rs
