use std::collections::{HashSet, VecDeque};
use std::hash::Hash;
pub fn reachable_from<N, I, S, Out>(roots: I, mut successors: S) -> Vec<N>
where
N: Clone + Eq + Hash,
I: IntoIterator<Item = N>,
S: FnMut(&N) -> Out,
Out: IntoIterator<Item = N>,
{
reachable_from_with_edges(roots, |node| successors(node).into_iter().map(|next| (next, ()))).0
}
pub fn reachable_from_with_edges<N, E, I, S, Out>(roots: I, mut incident: S) -> (Vec<N>, Vec<E>)
where
N: Clone + Eq + Hash,
I: IntoIterator<Item = N>,
S: FnMut(&N) -> Out,
Out: IntoIterator<Item = (N, E)>,
{
let mut visited = HashSet::new();
let mut order = Vec::new();
let mut edges = Vec::new();
let mut queue: VecDeque<N> = roots.into_iter().collect();
while let Some(curr) = queue.pop_front() {
if !visited.insert(curr.clone()) {
continue;
}
order.push(curr.clone());
for (next, edge) in incident(&curr) {
edges.push(edge);
if !visited.contains(&next) {
queue.push_back(next);
}
}
}
(order, edges)
}
#[cfg(test)]
mod tests {
use super::{reachable_from, reachable_from_with_edges};
#[test]
fn traversal_multi_root_and_cycles_are_deterministic() {
let edges: &[(&str, &str)] = &[("r1", "a"), ("a", "r1"), ("r2", "b"), ("a", "b")];
let got = reachable_from(["r1", "r2"], |n| {
edges.iter().filter(|(s, _)| s == n).map(|(_, t)| *t).collect::<Vec<_>>()
});
assert_eq!(got, vec!["r1", "r2", "a", "b"]);
}
#[test]
fn traversal_collects_diamond_and_parallel_edges_once_per_node() {
let graph: &[(&str, &str, &str)] = &[
("out", "mid1", "left"),
("out", "mid2", "right"),
("mid1", "root", "e1"),
("mid2", "root", "e2"),
("mid2", "root", "e2_alt"),
];
let (nodes, collected) = reachable_from_with_edges(["out"], |n| {
graph
.iter()
.filter(|(src, _, _)| src == n)
.map(|(_, dst, lbl)| (*dst, *lbl))
.collect::<Vec<_>>()
});
assert_eq!(nodes, vec!["out", "mid1", "mid2", "root"]);
assert_eq!(collected, vec!["left", "right", "e1", "e2", "e2_alt"]);
}
}