use std::collections::{BTreeMap, BTreeSet, VecDeque};
pub fn reachable<F, I>(start: &str, mut next: F) -> Vec<String>
where
F: FnMut(&str) -> I,
I: IntoIterator<Item = String>,
{
let mut out = Vec::new();
let mut seen = BTreeSet::new();
let mut queue = VecDeque::from([start.to_owned()]);
while let Some(current) = queue.pop_front() {
if !seen.insert(current.clone()) {
continue;
}
queue.extend(next(¤t));
out.push(current);
}
out
}
pub fn reaches<F, I>(start: &str, target: &str, mut next: F) -> bool
where
F: FnMut(&str) -> I,
I: IntoIterator<Item = String>,
{
let mut seen = BTreeSet::new();
let mut queue = VecDeque::from([start.to_owned()]);
while let Some(current) = queue.pop_front() {
if current == target {
return true;
}
if !seen.insert(current.clone()) {
continue;
}
queue.extend(next(¤t));
}
false
}
#[derive(Debug, Clone, PartialEq, Eq)]
pub struct CycleThroughStart;
pub fn closure<F, I>(start: &str, mut next: F) -> Result<Vec<String>, CycleThroughStart>
where
F: FnMut(&str) -> I,
I: IntoIterator<Item = String>,
{
let mut out = Vec::new();
let mut seen = BTreeSet::new();
let mut queue = VecDeque::from([start.to_owned()]);
let mut first = true;
while let Some(current) = queue.pop_front() {
if current == start && !first {
return Err(CycleThroughStart);
}
first = false;
if !seen.insert(current.clone()) {
continue;
}
queue.extend(next(¤t));
if current != start {
out.push(current);
}
}
Ok(out)
}
pub fn root<F>(start: &str, mut parent: F) -> String
where
F: FnMut(&str) -> Option<String>,
{
let mut current = start.to_owned();
let mut passed = BTreeSet::new();
loop {
if !passed.insert(current.clone()) {
return current;
}
match parent(¤t) {
Some(next) => current = next,
None => return current,
}
}
}
pub fn topological_order<'a, N, F, I>(nodes: N, mut deps: F) -> Result<Vec<String>, Vec<String>>
where
N: IntoIterator<Item = &'a str>,
F: FnMut(&str) -> I,
I: IntoIterator<Item = String>,
{
#[derive(Clone, Copy, PartialEq)]
enum Mark {
Visiting,
Done,
}
fn visit<F, I>(
id: &str,
deps: &mut F,
marks: &mut BTreeMap<String, Mark>,
path: &mut Vec<String>,
order: &mut Vec<String>,
) -> Result<(), Vec<String>>
where
F: FnMut(&str) -> I,
I: IntoIterator<Item = String>,
{
match marks.get(id) {
Some(Mark::Done) => return Ok(()),
Some(Mark::Visiting) => {
let start = path.iter().position(|p| p == id).unwrap_or(0);
let mut cycle: Vec<String> = path.iter().skip(start).cloned().collect();
cycle.push(id.to_owned());
return Err(cycle);
}
None => {}
}
marks.insert(id.to_owned(), Mark::Visiting);
path.push(id.to_owned());
let needed: Vec<String> = deps(id).into_iter().collect();
for dep in &needed {
visit(dep, deps, marks, path, order)?;
}
path.pop();
marks.insert(id.to_owned(), Mark::Done);
order.push(id.to_owned());
Ok(())
}
let mut marks = BTreeMap::new();
let mut order = Vec::new();
for id in nodes {
visit(id, &mut deps, &mut marks, &mut Vec::new(), &mut order)?;
}
Ok(order)
}
#[cfg(test)]
#[allow(clippy::unwrap_used, clippy::indexing_slicing)]
mod tests {
use super::*;
fn graph(edges: &[&str]) -> BTreeMap<String, Vec<String>> {
let mut g: BTreeMap<String, Vec<String>> = BTreeMap::new();
for e in edges {
let (from, to) = e.split_once('>').unwrap();
g.entry(from.to_owned()).or_default().push(to.to_owned());
}
g
}
fn next(g: &BTreeMap<String, Vec<String>>) -> impl FnMut(&str) -> Vec<String> + '_ {
|n: &str| g.get(n).cloned().unwrap_or_default()
}
#[test]
fn reachable_is_breadth_first_from_the_start() {
let g = graph(&["a>b", "a>c", "b>d", "c>d", "d>a"]);
assert_eq!(reachable("a", next(&g)), ["a", "b", "c", "d"]);
assert_eq!(reachable("z", next(&g)), ["z"]);
}
#[test]
fn reaches_finds_paths_and_a_node_reaches_itself() {
let g = graph(&["a>b", "b>c"]);
assert!(reaches("a", "c", next(&g)));
assert!(!reaches("c", "a", next(&g)));
assert!(reaches("b", "b", next(&g)));
}
#[test]
fn closure_excludes_the_start_and_refuses_a_cycle_through_it() {
let g = graph(&["a>b", "b>c", "c>b"]);
assert_eq!(closure("a", next(&g)).unwrap(), ["b", "c"]);
let g = graph(&["a>b", "b>a"]);
assert_eq!(closure("a", next(&g)), Err(CycleThroughStart));
let g = graph(&["a>a"]);
assert_eq!(closure("a", next(&g)), Err(CycleThroughStart));
}
#[test]
fn root_follows_parents_and_stops_on_a_cycle() {
let parents = graph(&["c>b", "b>a"]);
let up = |n: &str| parents.get(n).and_then(|p| p.first().cloned());
assert_eq!(root("c", up), "a");
let looped = graph(&["a>b", "b>a"]);
let up = |n: &str| looped.get(n).and_then(|p| p.first().cloned());
assert_eq!(root("a", up), "a");
}
#[test]
fn topological_order_puts_dependencies_first() {
let deps = graph(&["app>lib", "app>util", "lib>util"]);
let order = topological_order(["app", "lib", "util"], next(&deps)).unwrap();
assert_eq!(order, ["util", "lib", "app"]);
let pos = |n: &str| order.iter().position(|o| o == n).unwrap();
assert!(pos("util") < pos("lib") && pos("lib") < pos("app"));
}
#[test]
fn topological_order_names_the_cycle() {
let deps = graph(&["a>b", "b>c", "c>b"]);
assert_eq!(
topological_order(["a"], next(&deps)),
Err(vec!["b".to_owned(), "c".to_owned(), "b".to_owned()])
);
}
}