catlog/one/
graph_algorithms.rs

1//! Algorithms on graphs.
2
3use std::collections::{HashSet, VecDeque};
4use std::hash::Hash;
5
6use super::graph::*;
7use super::path::*;
8
9/** Iterates over all simple paths between two vertices of a finite graph.
10
11On our definition, a **simple path** is a path in which all edges are distinct.
12
13A **simple cycle** is a simple path in which the source and target coincide.
14This being a category theory library, we do consider the empty/identity path at
15a vertex to be a simple cycle.
16
17# References
18
19This function is adapted from previous implementations of the same algorithm:
20
21- [`all_simple_paths`](https://docs.rs/petgraph/latest/petgraph/algo/simple_paths/fn.all_simple_paths.html)
22  in [petgraph](https://github.com/petgraph/petgraph)
23- [`all_simple_paths`](https://networkx.org/documentation/stable/reference/algorithms/generated/networkx.algorithms.simple_paths.all_simple_paths.html)
24  in [NetworkX](https://networkx.org)
25 */
26pub fn simple_paths<'a, G>(
27    graph: &'a G,
28    from: &'a G::V,
29    to: &'a G::V,
30) -> impl Iterator<Item = Path<G::V, G::E>> + 'a
31where
32    G: FinGraph,
33    G::V: Hash,
34    G::E: Hash,
35{
36    bounded_simple_paths(graph, from, to, None)
37}
38
39/** Iterates over all simple paths of bounded length between two vertices.
40
41Works like [`simple_paths`], with the same definition of *simple path*, but the
42returned paths are also optionally restricted to those of bounded length. The
43**length** of a path is the number of edges in it.
44 */
45pub fn bounded_simple_paths<'a, G>(
46    graph: &'a G,
47    from: &'a G::V,
48    to: &'a G::V,
49    max_length: Option<usize>,
50) -> impl Iterator<Item = Path<G::V, G::E>> + 'a
51where
52    G: FinGraph,
53    G::V: Hash,
54    G::E: Hash,
55{
56    // The current path.
57    let mut path: Vec<G::E> = Vec::new();
58    // The set of edges in the current path.
59    // NOTE: This could be combined with `path` as an `IndexedSet`.
60    let mut visited: HashSet<G::E> = HashSet::new();
61    // Stack of out-edges of each vertex in the current path.
62    let mut stack: Vec<Vec<G::E>> = vec![graph.out_edges(from).collect()];
63
64    let maybe_empty_path = if from == to {
65        Some(Path::Id(to.clone()))
66    } else {
67        None
68    };
69
70    let nonempty_paths = std::iter::from_fn(move || {
71        while let Some(out_edges) = stack.last_mut() {
72            let Some(e) = out_edges.pop() else {
73                stack.pop();
74                if let Some(e) = path.pop() {
75                    visited.remove(&e);
76                }
77                continue;
78            };
79            if visited.contains(&e) || max_length.is_some_and(|n| path.len() >= n) {
80                continue;
81            }
82            let tgt = graph.tgt(&e);
83            path.push(e.clone());
84            visited.insert(e);
85            stack.push(graph.out_edges(&tgt).collect());
86            if tgt == *to {
87                let result = Path::collect(path.iter().cloned());
88                return Some(result.unwrap());
89            }
90        }
91        None
92    });
93
94    maybe_empty_path.into_iter().chain(nonempty_paths)
95}
96
97/** Arrange all the elements of a finite graph in specialization order.
98
99The [specialization
100order](https://en.wikipedia.org/wiki/Specialization_(pre)order) is the preorder
101associated with the [Alexandrov
102topology](https://en.wikipedia.org/wiki/Alexandrov_topology) on the graph.
103Equivalently, it is the preorder reflection of the category of elements of the
104graph. In simple terms, this means that every edge is greater than its source
105and its target.
106
107This function computes a total ordering of the elements of the graph that
108extends the specialization order. Such a total ordering is precisely a
109[topological ordering](https://en.wikipedia.org/wiki/Topological_ordering) on
110the category of elements of the graph. The particular ordering is computed using
111breadth-first search, which ensures that edges are close to their sources and
112targets (while still always being greater than them).
113 */
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
124This function is similar to [`spec_order_all`] except that the breadth-first
125search starts only from the given vertices.
126 */
127pub fn spec_order<G>(graph: &G, vertices: impl Iterator<Item = G::V>) -> Vec<GraphElem<G::V, G::E>>
128where
129    G: FinGraph,
130    G::V: Hash,
131{
132    let mut result = Vec::new();
133    let mut queue = VecDeque::new();
134    let mut visited = HashSet::new();
135    for v in vertices {
136        if !visited.contains(&v) {
137            queue.push_back(v);
138        }
139        while let Some(v) = queue.pop_front() {
140            if visited.contains(&v) {
141                continue;
142            }
143            result.push(GraphElem::Vertex(v.clone()));
144            for e in graph.out_edges(&v) {
145                let w = graph.tgt(&e);
146                if w == v || visited.contains(&w) {
147                    // Include loops at v.
148                    result.push(GraphElem::Edge(e))
149                } else {
150                    queue.push_back(w);
151                }
152            }
153            for e in graph.in_edges(&v) {
154                let w = graph.src(&e);
155                if w == v {
156                    // Exclude loops at v.
157                    continue;
158                }
159                if visited.contains(&w) {
160                    result.push(GraphElem::Edge(e))
161                } else {
162                    queue.push_back(w);
163                }
164            }
165            visited.insert(v);
166        }
167    }
168    result
169}
170
171#[cfg(test)]
172mod tests {
173    use super::GraphElem::*;
174    use super::*;
175    use nonempty::nonempty;
176
177    #[test]
178    fn find_simple_paths() {
179        let mut g = SkelGraph::triangle();
180        let paths: Vec<_> = simple_paths(&g, &0, &2).collect();
181        assert_eq!(paths, vec![Path::single(2), Path::pair(0, 1)]);
182        assert_eq!(bounded_simple_paths(&g, &0, &2, None).count(), 2);
183        assert_eq!(bounded_simple_paths(&g, &0, &2, Some(2)).count(), 2);
184        assert_eq!(bounded_simple_paths(&g, &0, &2, Some(1)).count(), 1);
185        assert_eq!(bounded_simple_paths(&g, &0, &2, Some(0)).count(), 0);
186
187        g.add_vertices(2);
188        let s = g.add_edge(3, 0);
189        let t = g.add_edge(2, 4);
190        let paths: Vec<_> = simple_paths(&g, &3, &4).collect();
191        assert_eq!(paths, vec![Path::Seq(nonempty![s, 2, t]), Path::Seq(nonempty![s, 0, 1, t])]);
192
193        let g = SkelGraph::cycle(3);
194        let paths: Vec<_> = simple_paths(&g, &0, &0).collect();
195        assert_eq!(paths, vec![Path::Id(0), Path::Seq(nonempty![0, 1, 2])]);
196        let paths: Vec<_> = simple_paths(&g, &0, &2).collect();
197        assert_eq!(paths, vec![Path::Seq(nonempty![0, 1])]);
198
199        let mut g: HashGraph<_, _> = Default::default();
200        assert!(g.add_vertex('x'));
201        assert!(g.add_edge('f', 'x', 'x'));
202        assert!(g.add_edge('g', 'x', 'x'));
203        let paths: HashSet<_> = simple_paths(&g, &'x', &'x').collect();
204        let target = HashSet::from([
205            Path::Id('x'),
206            Path::Seq(nonempty!['f']),
207            Path::Seq(nonempty!['g']),
208            Path::Seq(nonempty!['f', 'g']),
209            Path::Seq(nonempty!['g', 'f']),
210        ]);
211        assert_eq!(paths, target);
212    }
213
214    #[test]
215    fn spec_ordering() {
216        let g = SkelGraph::path(3);
217        assert_eq!(
218            spec_order(&g, Some(0).into_iter()),
219            vec![Vertex(0), Vertex(1), Edge(0), Vertex(2), Edge(1)]
220        );
221        assert_eq!(
222            spec_order(&g, Some(2).into_iter()),
223            vec![Vertex(2), Vertex(1), Edge(1), Vertex(0), Edge(0)]
224        );
225
226        let g = SkelGraph::triangle();
227        let desired = vec![Vertex(0), Vertex(1), Edge(0), Vertex(2), Edge(1), Edge(2)];
228        assert_eq!(spec_order_all(&g), desired);
229        assert_eq!(spec_order(&g, Some(0).into_iter()), desired);
230
231        let g = SkelGraph::cycle(1);
232        assert_eq!(spec_order_all(&g), vec![Vertex(0), Edge(0)]);
233    }
234}
catlog/one/graph_algorithms.rs

catlog/one/
graph_algorithms.rs
