publet_algorithms/graph.rs
1//! Traversals over a directed graph of string labels.
2//!
3//! The graph is never materialized here. Each function takes the start and
4//! a `next` function giving a node's neighbours, so the caller decides which
5//! edges count -- only authoritative ones, the union of two kinds, edges
6//! whose signer a viewpoint trusts -- and this module decides only the
7//! order they are walked in. That order is part of the contract: every
8//! traversal is breadth-first, visits each node once, and takes neighbours
9//! in the order `next` yields them, so the same graph always gives the same
10//! sequence, which keeps results that depend on it reproducible.
11
12use std::collections::{BTreeMap, BTreeSet, VecDeque};
13
14/// Every node reachable from `start`, `start` first, in breadth-first
15/// order.
16///
17/// # Example
18///
19/// ```
20/// use publet_algorithms::graph::reachable;
21///
22/// # use std::collections::BTreeMap;
23/// # let edges = BTreeMap::from([("a", vec!["b", "c"]), ("b", vec!["d"]), ("c", vec!["d"])]);
24/// # let next = |n: &str| -> Vec<String> {
25/// # edges.get(n).into_iter().flatten().map(|s| s.to_string()).collect()
26/// # };
27/// // a -> b, a -> c, b -> d, c -> d: breadth-first, each node once.
28/// assert_eq!(reachable("a", next), ["a", "b", "c", "d"]);
29/// ```
30pub fn reachable<F, I>(start: &str, mut next: F) -> Vec<String>
31where
32 F: FnMut(&str) -> I,
33 I: IntoIterator<Item = String>,
34{
35 let mut out = Vec::new();
36 let mut seen = BTreeSet::new();
37 let mut queue = VecDeque::from([start.to_owned()]);
38 while let Some(current) = queue.pop_front() {
39 if !seen.insert(current.clone()) {
40 continue;
41 }
42 queue.extend(next(¤t));
43 out.push(current);
44 }
45 out
46}
47
48/// Whether `target` can be reached from `start`; a node reaches itself.
49///
50/// Adding an edge `from -> to` closes a cycle exactly when
51/// `reaches(to, from, ..)`.
52///
53/// # Example
54///
55/// ```
56/// use publet_algorithms::graph::reaches;
57///
58/// # use std::collections::BTreeMap;
59/// # let edges = BTreeMap::from([("a", vec!["b", "c"]), ("b", vec!["d"]), ("c", vec!["d"])]);
60/// # let next = |n: &str| -> Vec<String> {
61/// # edges.get(n).into_iter().flatten().map(|s| s.to_string()).collect()
62/// # };
63/// assert!(reaches("a", "d", next));
64/// assert!(!reaches("d", "a", next));
65/// // Adding d -> a would close a cycle exactly when a already reaches d.
66/// ```
67pub fn reaches<F, I>(start: &str, target: &str, mut next: F) -> bool
68where
69 F: FnMut(&str) -> I,
70 I: IntoIterator<Item = String>,
71{
72 let mut seen = BTreeSet::new();
73 let mut queue = VecDeque::from([start.to_owned()]);
74 while let Some(current) = queue.pop_front() {
75 if current == target {
76 return true;
77 }
78 if !seen.insert(current.clone()) {
79 continue;
80 }
81 queue.extend(next(¤t));
82 }
83 false
84}
85
86/// [`closure`] found an edge leading back to its start.
87#[derive(Debug, Clone, PartialEq, Eq)]
88pub struct CycleThroughStart;
89
90/// Every node reachable from `start` by at least one edge, in
91/// breadth-first order, `start` itself excluded.
92///
93/// # Errors
94///
95/// [`CycleThroughStart`] if an edge leads back to `start`: for a relation
96/// that must be acyclic, the closure of a node on a cycle is not defined.
97///
98/// # Example
99///
100/// ```
101/// use publet_algorithms::graph::{CycleThroughStart, closure};
102///
103/// # use std::collections::BTreeMap;
104/// # let edges = BTreeMap::from([("a", vec!["b", "c"]), ("b", vec!["d"]), ("c", vec!["d"])]);
105/// # let next = |n: &str| -> Vec<String> {
106/// # edges.get(n).into_iter().flatten().map(|s| s.to_string()).collect()
107/// # };
108/// assert_eq!(closure("a", next).unwrap(), ["b", "c", "d"]);
109///
110/// // With d -> a added, the closure of a would contain a itself.
111/// let cyclic = |n: &str| if n == "d" { vec!["a".to_string()] } else { next(n) };
112/// assert_eq!(closure("a", cyclic), Err(CycleThroughStart));
113/// ```
114pub fn closure<F, I>(start: &str, mut next: F) -> Result<Vec<String>, CycleThroughStart>
115where
116 F: FnMut(&str) -> I,
117 I: IntoIterator<Item = String>,
118{
119 let mut out = Vec::new();
120 let mut seen = BTreeSet::new();
121 let mut queue = VecDeque::from([start.to_owned()]);
122 let mut first = true;
123 while let Some(current) = queue.pop_front() {
124 if current == start && !first {
125 return Err(CycleThroughStart);
126 }
127 first = false;
128 if !seen.insert(current.clone()) {
129 continue;
130 }
131 queue.extend(next(¤t));
132 if current != start {
133 out.push(current);
134 }
135 }
136 Ok(out)
137}
138
139/// Follow `parent` from `start` until a node has none, and return that
140/// node. If the walk returns to a node it has passed, it stops there, so a
141/// cycle cannot make it run forever.
142///
143/// # Example
144///
145/// ```
146/// use publet_algorithms::graph::root;
147///
148/// // Each version names the one it replaces.
149/// let replaces = |v: &str| match v {
150/// "v3" => Some("v2".to_string()),
151/// "v2" => Some("v1".to_string()),
152/// _ => None,
153/// };
154/// assert_eq!(root("v3", replaces), "v1");
155/// ```
156pub fn root<F>(start: &str, mut parent: F) -> String
157where
158 F: FnMut(&str) -> Option<String>,
159{
160 let mut current = start.to_owned();
161 let mut passed = BTreeSet::new();
162 loop {
163 if !passed.insert(current.clone()) {
164 return current;
165 }
166 match parent(¤t) {
167 Some(next) => current = next,
168 None => return current,
169 }
170 }
171}
172
173/// `nodes` ordered so every node comes after everything `deps` says it
174/// depends on.
175///
176/// Depth-first, taking `nodes` and each node's dependencies in the order
177/// given, so the order is deterministic. A dependency that is not among
178/// `nodes` is still placed, before the nodes that need it.
179///
180/// # Errors
181///
182/// The cycle, as the path that closes it -- `["a", "b", "a"]` -- if the
183/// dependencies form one.
184///
185/// # Example
186///
187/// ```
188/// use std::collections::BTreeMap;
189/// use publet_algorithms::graph::topological_order;
190///
191/// let deps = BTreeMap::from([("app", vec!["lib"]), ("lib", vec!["util"])]);
192/// let needs = |id: &str| -> Vec<String> {
193/// deps.get(id).into_iter().flatten().map(|d| d.to_string()).collect()
194/// };
195/// assert_eq!(topological_order(["app", "lib", "util"], needs).unwrap(), ["util", "lib", "app"]);
196///
197/// // A cycle is reported as the path that closes it.
198/// let cyclic = |id: &str| vec![if id == "a" { "b" } else { "a" }.to_string()];
199/// assert_eq!(topological_order(["a"], cyclic).unwrap_err(), ["a", "b", "a"]);
200/// ```
201pub fn topological_order<'a, N, F, I>(nodes: N, mut deps: F) -> Result<Vec<String>, Vec<String>>
202where
203 N: IntoIterator<Item = &'a str>,
204 F: FnMut(&str) -> I,
205 I: IntoIterator<Item = String>,
206{
207 #[derive(Clone, Copy, PartialEq)]
208 enum Mark {
209 Visiting,
210 Done,
211 }
212 fn visit<F, I>(
213 id: &str,
214 deps: &mut F,
215 marks: &mut BTreeMap<String, Mark>,
216 path: &mut Vec<String>,
217 order: &mut Vec<String>,
218 ) -> Result<(), Vec<String>>
219 where
220 F: FnMut(&str) -> I,
221 I: IntoIterator<Item = String>,
222 {
223 match marks.get(id) {
224 Some(Mark::Done) => return Ok(()),
225 Some(Mark::Visiting) => {
226 let start = path.iter().position(|p| p == id).unwrap_or(0);
227 let mut cycle: Vec<String> = path.iter().skip(start).cloned().collect();
228 cycle.push(id.to_owned());
229 return Err(cycle);
230 }
231 None => {}
232 }
233 marks.insert(id.to_owned(), Mark::Visiting);
234 path.push(id.to_owned());
235 let needed: Vec<String> = deps(id).into_iter().collect();
236 for dep in &needed {
237 visit(dep, deps, marks, path, order)?;
238 }
239 path.pop();
240 marks.insert(id.to_owned(), Mark::Done);
241 order.push(id.to_owned());
242 Ok(())
243 }
244
245 let mut marks = BTreeMap::new();
246 let mut order = Vec::new();
247 for id in nodes {
248 visit(id, &mut deps, &mut marks, &mut Vec::new(), &mut order)?;
249 }
250 Ok(order)
251}
252
253#[cfg(test)]
254#[allow(clippy::unwrap_used, clippy::indexing_slicing)]
255mod tests {
256 use super::*;
257
258 /// A graph from `"a>b"` edge strings.
259 fn graph(edges: &[&str]) -> BTreeMap<String, Vec<String>> {
260 let mut g: BTreeMap<String, Vec<String>> = BTreeMap::new();
261 for e in edges {
262 let (from, to) = e.split_once('>').unwrap();
263 g.entry(from.to_owned()).or_default().push(to.to_owned());
264 }
265 g
266 }
267
268 fn next(g: &BTreeMap<String, Vec<String>>) -> impl FnMut(&str) -> Vec<String> + '_ {
269 |n: &str| g.get(n).cloned().unwrap_or_default()
270 }
271
272 // covers: graph::reachable
273 #[test]
274 fn reachable_is_breadth_first_from_the_start() {
275 let g = graph(&["a>b", "a>c", "b>d", "c>d", "d>a"]);
276 assert_eq!(reachable("a", next(&g)), ["a", "b", "c", "d"]);
277 assert_eq!(reachable("z", next(&g)), ["z"]);
278 }
279
280 // covers: graph::reaches
281 #[test]
282 fn reaches_finds_paths_and_a_node_reaches_itself() {
283 let g = graph(&["a>b", "b>c"]);
284 assert!(reaches("a", "c", next(&g)));
285 assert!(!reaches("c", "a", next(&g)));
286 assert!(reaches("b", "b", next(&g)));
287 }
288
289 // covers: graph::closure
290 #[test]
291 fn closure_excludes_the_start_and_refuses_a_cycle_through_it() {
292 let g = graph(&["a>b", "b>c", "c>b"]);
293 assert_eq!(closure("a", next(&g)).unwrap(), ["b", "c"]);
294 let g = graph(&["a>b", "b>a"]);
295 assert_eq!(closure("a", next(&g)), Err(CycleThroughStart));
296 let g = graph(&["a>a"]);
297 assert_eq!(closure("a", next(&g)), Err(CycleThroughStart));
298 }
299
300 // covers: graph::root
301 #[test]
302 fn root_follows_parents_and_stops_on_a_cycle() {
303 let parents = graph(&["c>b", "b>a"]);
304 let up = |n: &str| parents.get(n).and_then(|p| p.first().cloned());
305 assert_eq!(root("c", up), "a");
306 let looped = graph(&["a>b", "b>a"]);
307 let up = |n: &str| looped.get(n).and_then(|p| p.first().cloned());
308 assert_eq!(root("a", up), "a");
309 }
310
311 // covers: graph::topological_order
312 #[test]
313 fn topological_order_puts_dependencies_first() {
314 let deps = graph(&["app>lib", "app>util", "lib>util"]);
315 let order = topological_order(["app", "lib", "util"], next(&deps)).unwrap();
316 assert_eq!(order, ["util", "lib", "app"]);
317 let pos = |n: &str| order.iter().position(|o| o == n).unwrap();
318 assert!(pos("util") < pos("lib") && pos("lib") < pos("app"));
319 }
320
321 // covers: graph::topological_order
322 #[test]
323 fn topological_order_names_the_cycle() {
324 let deps = graph(&["a>b", "b>c", "c>b"]);
325 assert_eq!(
326 topological_order(["a"], next(&deps)),
327 Err(vec!["b".to_owned(), "c".to_owned(), "b".to_owned()])
328 );
329 }
330}