Function rs_graph::shortestpath::moorebellmanford::directed
source · pub fn directed<'a, G, W, F>(
g: &'a G,
weights: F,
src: G::Node<'a>
) -> (Vec<Option<G::Edge<'a>>>, Option<G::Node<'a>>)where
G: 'a + IndexDigraph,
W: NumAssign + Ord + Copy,
F: Fn(G::Edge<'a>) -> W,
Expand description
The shortest-path algorithm by Moore-Bellman-Ford on a directed graph.
The function returns pair. The first element is the vector of the
incoming edge for each (reachable) node. The second element a node
on a negative cylce if it exists, otherwise it is None
.
Example
use rs_graph::{LinkedListGraph, Buildable, Builder, traits::*};
use rs_graph::shortestpath::moorebellmanford;
let mut weights = vec![];
let mut g = LinkedListGraph::<usize>::new_with(|b| {
let nodes = b.add_nodes(7);
for &(u,v,w) in [(0,1,-8), (1,4,-3), (2,0,2), (2,1,1), (2,5,-3), (3,1,0), (3,2,5),
(4,3,8), (5,3,-1), (6,3,4), (6,4,6), (6,5,3)].iter()
{
b.add_edge(nodes[u], nodes[v]);
weights.push(w);
}
});
let (pred, cycle) = moorebellmanford::directed(&g, |e| weights[g.edge_id(e)], g.id2node(6));
assert_eq!(cycle, None);
assert_eq!(pred[6], None);
for &(u,p) in [(0,2), (1,0), (2,3), (4,1), (5,6)].iter() {
assert_eq!(g.src(pred[u].unwrap()), g.id2node(p));
}