Function rs_graph::search::path_from_incomings
source · pub fn path_from_incomings<N, E, I>(
dst: N,
incomings: I
) -> impl Iterator<Item = E>where
N: Copy,
E: Clone,
I: Fn(N) -> Option<(E, N)>,
Expand description
Compute a path from a map of incoming edges for each node.
Parameters
dst
: the destination nodeincomings(v)
: return the incoming edge and preceding node for nodev
(orNone
if it does not exist)
Return
An iterator over the incoming edges starting from the last one.
Example
// Breadth-first-search on a directed with 7 nodes.
use rs_graph::LinkedListGraph;
use rs_graph::traits::*;
use rs_graph::classes;
use rs_graph::search::{path_from_incomings, bfs};
use std::collections::{HashMap, VecDeque};
let g: LinkedListGraph = classes::cycle(7);
let mut incomings = HashMap::new();
let mut bfs = bfs::start_with_data(g.outgoing(), g.id2node(0), (&mut incomings, VecDeque::new()));
for _ in bfs {}
{
let mut path = path_from_incomings(g.id2node(3), |u| incomings.get(&u).map(|&e| (e, g.src(e))));
assert_eq!(path.next().map(|e| g.edge_id(e)), Some(2));
assert_eq!(path.next().map(|e| g.edge_id(e)), Some(1));
assert_eq!(path.next().map(|e| g.edge_id(e)), Some(0));
assert_eq!(path.next().map(|e| g.edge_id(e)), None);
}
{
let mut path = path_from_incomings(g.id2node(4), |u| incomings.get(&u).map(|&e| (e, g.src(e))));
assert_eq!(path.next().map(|e| g.edge_id(e)), Some(3));
assert_eq!(path.next().map(|e| g.edge_id(e)), Some(2));
assert_eq!(path.next().map(|e| g.edge_id(e)), Some(1));
assert_eq!(path.next().map(|e| g.edge_id(e)), Some(0));
assert_eq!(path.next().map(|e| g.edge_id(e)), None);
}