Skip to main content

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(&current));
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(&current));
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(&current));
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(&current) {
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}