catlog/one/
graph_algorithms.rs

1//! Algorithms on graphs.
2
3use derivative::Derivative;
4use derive_more::Constructor;
5use indexmap::IndexMap;
6use std::collections::{HashMap, HashSet, VecDeque};
7use std::hash::Hash;
8
9use super::graph::*;
10use super::path::*;
11
12/// Iterates over all simple paths between two vertices of a finite graph.
13///
14/// On our definition, a **simple path** is a path in which all edges are distinct.
15///
16/// A **simple cycle** is a simple path in which the source and target coincide.
17/// This being a category theory library, we do consider the empty/identity path at
18/// a vertex to be a simple cycle.
19///
20/// # References
21///
22/// This function is adapted from previous implementations of the same algorithm:
23///
24/// - [`all_simple_paths`](https://docs.rs/petgraph/latest/petgraph/algo/simple_paths/fn.all_simple_paths.html)
25///   in [petgraph](https://github.com/petgraph/petgraph)
26/// - [`all_simple_paths`](https://networkx.org/documentation/stable/reference/algorithms/generated/networkx.algorithms.simple_paths.all_simple_paths.html)
27///   in [NetworkX](https://networkx.org)
28pub fn simple_paths<'a, G>(
29    graph: &'a G,
30    from: &'a G::V,
31    to: &'a G::V,
32) -> impl Iterator<Item = Path<G::V, G::E>> + 'a
33where
34    G: FinGraph,
35    G::V: Hash,
36    G::E: Hash,
37{
38    bounded_simple_paths(graph, from, to, None)
39}
40
41/// Iterates over all simple paths of bounded length between two vertices.
42///
43/// Works like [`simple_paths`], with the same definition of *simple path*, but the
44/// returned paths are also optionally restricted to those of bounded length. The
45/// length** of a path is the number of edges in it.
46pub fn bounded_simple_paths<'a, G>(
47    graph: &'a G,
48    from: &'a G::V,
49    to: &'a G::V,
50    max_length: Option<usize>,
51) -> impl Iterator<Item = Path<G::V, G::E>> + 'a
52where
53    G: FinGraph,
54    G::V: Hash,
55    G::E: Hash,
56{
57    // The current path.
58    let mut path: Vec<G::E> = Vec::new();
59    // The set of edges in the current path.
60    // NOTE: This could be combined with `path` as an `IndexedSet`.
61    let mut visited: HashSet<G::E> = HashSet::new();
62    // Stack of out-edges of each vertex in the current path.
63    let mut stack: Vec<Vec<G::E>> = vec![graph.out_edges(from).collect()];
64
65    let maybe_empty_path = if from == to {
66        Some(Path::Id(to.clone()))
67    } else {
68        None
69    };
70
71    let nonempty_paths = std::iter::from_fn(move || {
72        while let Some(out_edges) = stack.last_mut() {
73            let Some(e) = out_edges.pop() else {
74                stack.pop();
75                if let Some(e) = path.pop() {
76                    visited.remove(&e);
77                }
78                continue;
79            };
80            if visited.contains(&e) || max_length.is_some_and(|n| path.len() >= n) {
81                continue;
82            }
83            let tgt = graph.tgt(&e);
84            path.push(e.clone());
85            visited.insert(e);
86            stack.push(graph.out_edges(&tgt).collect());
87            if tgt == *to {
88                let result = Path::collect(path.iter().cloned());
89                return Some(result.unwrap());
90            }
91        }
92        None
93    });
94
95    maybe_empty_path.into_iter().chain(nonempty_paths)
96}
97
98/// Arrange all the elements of a finite graph in specialization order.
99///
100/// The [specialization
101/// order](https://en.wikipedia.org/wiki/Specialization_(pre)order) is the preorder
102/// associated with the [Alexandrov
103/// topology](https://en.wikipedia.org/wiki/Alexandrov_topology) on the graph.
104/// Equivalently, it is the preorder reflection of the category of elements of the
105/// graph. In simple terms, this means that every edge is greater than its source
106/// and its target.
107///
108/// This function computes a total ordering of the elements of the graph that
109/// extends the specialization order. Such a total ordering is precisely a
110/// [topological ordering](https://en.wikipedia.org/wiki/Topological_ordering) on
111/// the category of elements of the graph. The particular ordering is computed using
112/// breadth-first search, which ensures that edges are close to their sources and
113/// targets (while still always being greater than them).
114pub fn spec_order_all<G>(graph: &G) -> Vec<GraphElem<G::V, G::E>>
115where
116    G: FinGraph,
117    G::V: Hash,
118{
119    spec_order(graph, graph.vertices())
120}
121
122/// Arrange some or all elements of a graph in specialization order.
123///
124/// This function is similar to [`spec_order_all`] except that the breadth-first
125/// search starts only from the given vertices.
126pub fn spec_order<G>(graph: &G, vertices: impl Iterator<Item = G::V>) -> Vec<GraphElem<G::V, G::E>>
127where
128    G: FinGraph,
129    G::V: Hash,
130{
131    let mut result = Vec::new();
132    let mut queue = VecDeque::new();
133    let mut visited = HashSet::new();
134    for v in vertices {
135        if !visited.contains(&v) {
136            queue.push_back(v);
137        }
138        while let Some(v) = queue.pop_front() {
139            if visited.contains(&v) {
140                continue;
141            }
142            result.push(GraphElem::Vertex(v.clone()));
143            for e in graph.out_edges(&v) {
144                let w = graph.tgt(&e);
145                if w == v || visited.contains(&w) {
146                    // Include loops at v.
147                    result.push(GraphElem::Edge(e))
148                } else {
149                    queue.push_back(w);
150                }
151            }
152            for e in graph.in_edges(&v) {
153                let w = graph.src(&e);
154                if w == v {
155                    // Exclude loops at v.
156                    continue;
157                }
158                if visited.contains(&w) {
159                    result.push(GraphElem::Edge(e))
160                } else {
161                    queue.push_back(w);
162                }
163            }
164            visited.insert(v);
165        }
166    }
167    result
168}
169
170/// An enum which parameterises the traversal direction for the depth first
171/// traversal function.
172#[derive(Debug)]
173pub enum TraversalDirection {
174    /// Visit out_neighbors for each vertex.
175    Outward,
176    /// Visit in_neighbors for each vertex.
177    Inward,
178}
179
180/// Depth-first search over a finite graph.
181///
182/// Constructed via [`DFS::new`] with a builder-style API. The `discovered` set
183/// is persisted internally, allowing multiple calls to [`traverse`](Self::traverse) with
184/// different start vertices while sharing visited-vertex state.
185///
186/// The type parameters `D` and `C` are the callback types for `on_discover` and
187/// `on_complete`, respectively.
188#[derive(Debug, Derivative)]
189#[derivative(Default(bound = ""))]
190pub struct DFS<V, D, C>
191where
192    D: FnMut(V),
193    C: FnMut(V),
194{
195    discovered: HashSet<V>,
196    #[derivative(Default(value = "TraversalDirection::Outward"))]
197    traversal_direction: TraversalDirection,
198    on_discover: Option<D>,
199    on_complete: Option<C>,
200}
201
202impl<V> DFS<V, fn(V), fn(V)> {
203    /// Creates a new DFS.
204    ///
205    /// Defaults to outward traversal, an empty discovered set, and no callbacks.
206    /// Use the builder methods to configure before calling [`traverse`](Self::traverse).
207    pub fn new() -> Self {
208        Self::default()
209    }
210}
211
212impl<V, D, C> DFS<V, D, C>
213where
214    D: FnMut(V),
215    C: FnMut(V),
216{
217    /// Sets the traversal direction (outward or inward along edges).
218    /// Defaults to [`TraversalDirection::Outward`].
219    pub fn traversal_direction(mut self, dir: TraversalDirection) -> Self {
220        self.traversal_direction = dir;
221        self
222    }
223
224    /// Sets a callback invoked when a vertex is first discovered.
225    pub fn on_discover<D2: FnMut(V)>(self, on_discover: D2) -> DFS<V, D2, C> {
226        DFS {
227            traversal_direction: self.traversal_direction,
228            discovered: self.discovered,
229            on_discover: Some(on_discover),
230            on_complete: self.on_complete,
231        }
232    }
233
234    /// Sets a callback invoked when backtracking from a vertex after all its
235    /// neighbors have been processed.
236    pub fn on_complete<C2: FnMut(V)>(self, on_complete: C2) -> DFS<V, D, C2> {
237        DFS {
238            traversal_direction: self.traversal_direction,
239            discovered: self.discovered,
240            on_discover: self.on_discover,
241            on_complete: Some(on_complete),
242        }
243    }
244
245    /// Provides a pre-populated discovered set, useful for resuming a traversal
246    /// or excluding specific vertices.
247    pub fn discovered(mut self, discovered: HashSet<V>) -> Self {
248        self.discovered = discovered;
249        self
250    }
251
252    /// Clears the `discovered` set, allowing the DFS to revisit all vertices.
253    pub fn reset(&mut self) {
254        self.discovered.clear();
255    }
256
257    /// Traverses the graph depth-first starting from the given vertex.
258    ///
259    /// Vertices already in the `discovered` set are skipped, and newly visited
260    /// vertices are added to it. This allows multiple calls with different start
261    /// vertices to share state.
262    ///
263    /// # Example
264    ///
265    /// ```rust,ignore
266    /// let mut discover_order = Vec::new();
267    /// let mut complete_order = Vec::new();
268    /// let mut dfs = DFS::new()
269    ///     .traversal_direction(TraversalDirection::Outward)
270    ///     .on_discover(|v| discover_order.push(v))
271    ///     .on_complete(|v| complete_order.push(v));
272    /// dfs.traverse(&graph, start_vertex);
273    /// ```
274    pub fn traverse<G>(&mut self, graph: &G, start_vertex: V)
275    where
276        V: Clone + Eq + Hash,
277        G: FinGraph<V = V>,
278    {
279        let mut stack = Vec::new();
280        stack.push(start_vertex);
281
282        while let Some(nx) = stack.last().cloned() {
283            if self.discovered.insert(nx.clone()) {
284                if let Some(ref mut callback) = self.on_discover {
285                    callback(nx.clone());
286                }
287                let successors: Vec<_> = match self.traversal_direction {
288                    TraversalDirection::Outward => graph.out_neighbors(&nx).collect(),
289                    TraversalDirection::Inward => graph.in_neighbors(&nx).collect(),
290                };
291                for succ in successors {
292                    if !self.discovered.contains(&succ) {
293                        stack.push(succ);
294                    }
295                }
296            } else {
297                stack.pop();
298                if let Some(ref mut callback) = self.on_complete {
299                    callback(nx.clone());
300                }
301            }
302        }
303    }
304}
305
306/// Contains both the topologically-sorted stack of vertices and feedback vertices.
307#[derive(Debug, Clone, Constructor)]
308pub struct ToposortData<V> {
309    /// Stores an array of topologically-sorted vertices.
310    pub stack: Vec<V>,
311
312    /// Stores the feedback vertices with their outneighbors.
313    pub cycles: IndexMap<V, Vec<V>>,
314}
315
316type ToposortResult<V> = Result<ToposortData<V>, V>;
317
318/// Implementation of topological sort which returns an error when it encounters a cycle.
319pub fn toposort_strict<G>(graph: &G) -> Result<Vec<G::V>, G::V>
320where
321    G: FinGraph,
322    G::V: Hash + std::fmt::Debug,
323{
324    toposort_impl(graph, true).map(|t| t.stack)
325}
326
327/// Implementation of topological sort which does not return an error when it encounters cycle.
328pub fn toposort_lenient<G>(graph: &G) -> ToposortData<G::V>
329where
330    G: FinGraph,
331    G::V: Hash + std::fmt::Debug,
332{
333    toposort_impl(graph, false).expect("toposort in lenient mode should return a valid result")
334}
335
336/// Computes a topological sorting for a given graph.
337///
338/// This toposort algorithm was adapted from the crate `petgraph`, found
339/// [here](https://github.com/petgraph/petgraph/blob/4d807c19304c02c9dd687c68577f75aefcb98491/src/algo/mod.rs#L204).
340fn toposort_impl<G>(graph: &G, is_strict: bool) -> ToposortResult<G::V>
341where
342    G: FinGraph,
343    G::V: Hash + std::fmt::Debug,
344{
345    let mut finished = HashSet::new();
346    let mut finish_stack = Vec::new();
347
348    let mut dfs =
349        DFS::new()
350            .traversal_direction(TraversalDirection::Outward)
351            .on_complete(|nx: G::V| {
352                if finished.insert(nx.clone()) {
353                    finish_stack.push(nx);
354                }
355            });
356
357    for v in graph.vertices() {
358        if dfs.discovered.contains(&v) {
359            continue;
360        }
361        dfs.traverse(graph, v);
362    }
363    finish_stack.reverse();
364
365    // Instead of multiple DFSs backwards to validate that we have no cycles, we
366    // simply test directly by comparing positions of vertices.
367    let position: HashMap<G::V, usize> =
368        finish_stack.iter().enumerate().map(|(i, v)| (v.clone(), i)).collect();
369    let mut cycles = IndexMap::new();
370    for e in graph.edges() {
371        let s = graph.src(&e);
372        let t = graph.tgt(&e);
373        // Note that we did a DFS starting at every vertex, so it's impossible
374        // that they don't appear _somewhere_ in our map.
375        if position[&s] >= position[&t] {
376            if is_strict {
377                return Err(s);
378            } else {
379                let outs = graph.out_neighbors(&s).collect();
380                cycles.insert(s, outs);
381            }
382        }
383    }
384
385    Ok(ToposortData::new(finish_stack, cycles))
386}
387
388#[cfg(test)]
389mod tests {
390    use super::GraphElem::*;
391    use super::*;
392    use nonempty::nonempty;
393
394    #[test]
395    fn find_simple_paths() {
396        let mut g = SkelGraph::triangle();
397        let paths: Vec<_> = simple_paths(&g, &0, &2).collect();
398        assert_eq!(paths, vec![Path::single(2), Path::pair(0, 1)]);
399        assert_eq!(bounded_simple_paths(&g, &0, &2, None).count(), 2);
400        assert_eq!(bounded_simple_paths(&g, &0, &2, Some(2)).count(), 2);
401        assert_eq!(bounded_simple_paths(&g, &0, &2, Some(1)).count(), 1);
402        assert_eq!(bounded_simple_paths(&g, &0, &2, Some(0)).count(), 0);
403
404        g.add_vertices(2);
405        let s = g.add_edge(3, 0);
406        let t = g.add_edge(2, 4);
407        let paths: Vec<_> = simple_paths(&g, &3, &4).collect();
408        assert_eq!(paths, vec![Path::Seq(nonempty![s, 2, t]), Path::Seq(nonempty![s, 0, 1, t])]);
409
410        let g = SkelGraph::cycle(3);
411        let paths: Vec<_> = simple_paths(&g, &0, &0).collect();
412        assert_eq!(paths, vec![Path::Id(0), Path::Seq(nonempty![0, 1, 2])]);
413        let paths: Vec<_> = simple_paths(&g, &0, &2).collect();
414        assert_eq!(paths, vec![Path::Seq(nonempty![0, 1])]);
415
416        let mut g: HashGraph<_, _> = Default::default();
417        assert!(g.add_vertex('x'));
418        assert!(g.add_edge('f', 'x', 'x'));
419        assert!(g.add_edge('g', 'x', 'x'));
420        let paths: HashSet<_> = simple_paths(&g, &'x', &'x').collect();
421        let target = HashSet::from([
422            Path::Id('x'),
423            Path::Seq(nonempty!['f']),
424            Path::Seq(nonempty!['g']),
425            Path::Seq(nonempty!['f', 'g']),
426            Path::Seq(nonempty!['g', 'f']),
427        ]);
428        assert_eq!(paths, target);
429    }
430
431    #[test]
432    fn toposorting() {
433        let g = SkelGraph::path(5);
434        let result = toposort_strict(&g);
435        assert_eq!(result.unwrap(), vec![0, 1, 2, 3, 4]);
436
437        let mut g = SkelGraph::path(3);
438        g.add_vertices(1);
439        g.add_edge(2, 3);
440        g.add_edge(3, 0);
441        let t = &toposort_strict(&g).unwrap_err();
442        expect_test::expect!["3"].assert_eq(&format!("{t}"));
443
444        let g = SkelGraph::triangle();
445        assert_eq!(toposort_strict(&g).unwrap(), vec![0, 1, 2]);
446
447        let mut g = SkelGraph::path(4);
448        g.add_vertices(2);
449        g.add_edge(1, 4);
450        g.add_edge(4, 3);
451        g.add_edge(5, 2);
452
453        assert_eq!(toposort_strict(&g).unwrap(), vec![5, 0, 1, 2, 4, 3]);
454
455        let mut g: HashGraph<_, _> = Default::default();
456        g.add_vertices(vec![0, 1, 2, 3, 4, 5]);
457        g.add_edge("0-1", 0, 1);
458        g.add_edge("1-2", 1, 2);
459        g.add_edge("2-3", 2, 3);
460        g.add_edge("1-4", 1, 4);
461        g.add_edge("4-3", 4, 3);
462        g.add_edge("5-2", 5, 2);
463        if let Ok(sort) = toposort_strict(&g) {
464            let (i0, i1) = (sort.iter().position(|&x| x == 5), sort.iter().position(|&x| x == 2));
465            assert!(i0.unwrap() < i1.unwrap());
466        }
467    }
468
469    #[test]
470    fn spec_ordering() {
471        let g = SkelGraph::path(3);
472        assert_eq!(
473            spec_order(&g, Some(0).into_iter()),
474            vec![Vertex(0), Vertex(1), Edge(0), Vertex(2), Edge(1)]
475        );
476        assert_eq!(
477            spec_order(&g, Some(2).into_iter()),
478            vec![Vertex(2), Vertex(1), Edge(1), Vertex(0), Edge(0)]
479        );
480
481        let g = SkelGraph::triangle();
482        let desired = vec![Vertex(0), Vertex(1), Edge(0), Vertex(2), Edge(1), Edge(2)];
483        assert_eq!(spec_order_all(&g), desired);
484        assert_eq!(spec_order(&g, Some(0).into_iter()), desired);
485
486        let g = SkelGraph::cycle(1);
487        assert_eq!(spec_order_all(&g), vec![Vertex(0), Edge(0)]);
488    }
489
490    #[test]
491    fn dfs_with_callbacks() {
492        // Test 1: Simple acyclic graph (path: 0 -> 1 -> 2)
493        let g = SkelGraph::path(3);
494        let mut discovered_order = Vec::new();
495        let mut completed_order = Vec::new();
496        let mut dfs = DFS::new()
497            .traversal_direction(TraversalDirection::Outward)
498            .on_discover(|v| discovered_order.push(v))
499            .on_complete(|v| completed_order.push(v));
500        dfs.traverse(&g, 0);
501        // Discover in DFS order from 0: 0, then 1, then 2
502        assert_eq!(discovered_order, vec![0, 1, 2]);
503        // Complete in reverse order: finish 2, then 1, then 0
504        assert_eq!(completed_order, vec![2, 1, 0]);
505
506        // Test 2: Graph with branching (triangle: 0 -> 1 -> 2, 0 -> 2)
507        let g = SkelGraph::triangle();
508        let mut discovered_order = Vec::new();
509        let mut completed_order = Vec::new();
510        let mut dfs = DFS::new()
511            .traversal_direction(TraversalDirection::Outward)
512            .on_discover(|v| discovered_order.push(v))
513            .on_complete(|v| completed_order.push(v));
514        dfs.traverse(&g, 0);
515        // Discover all three vertices
516        assert_eq!(discovered_order.len(), 3);
517        assert_eq!(discovered_order.iter().collect::<HashSet<_>>(), [0, 1, 2].iter().collect());
518        // Vertex 0 should complete last (it's the root)
519        assert_eq!(completed_order.last(), Some(&0));
520
521        // Test 3: Self-loops are handled gracefully (no error, no infinite loop)
522        let mut g: HashGraph<usize, &str> = Default::default();
523        g.add_vertices(vec![0, 1]);
524        g.add_edge("self", 0, 0);
525        g.add_edge("e", 0, 1);
526        let mut discovered_order = Vec::new();
527        let mut dfs = DFS::new()
528            .traversal_direction(TraversalDirection::Outward)
529            .on_discover(|v| discovered_order.push(v));
530        dfs.traverse(&g, 0);
531        assert_eq!(discovered_order.iter().collect::<HashSet<_>>(), [0, 1].iter().collect());
532    }
533}
catlog/one/graph_algorithms.rs

catlog/one/
graph_algorithms.rs
