Function rs_graph::shortestpath::moorebellmanford::directed

pub fn directed<'a, G, Ws, W>(
    g: &'a G,
    weights: Ws,
    src: G::Node
) -> (IndexNodeVec<'a, G, Option<G::Edge>>, Option<G::Node>)where
    G: 'a + IndexDigraph<'a>,
    Ws: EdgeMap<'a, G, W>,
    W: NumAssign + Ord + Copy,

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::{Digraph, LinkedListGraph, Builder, EdgeVec};
use rs_graph::shortestpath::moorebellmanford;

let mut g = LinkedListGraph::<usize>::new();
let nodes = g.add_nodes(7);
let mut weights = vec![];
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()
{
    g.add_edge(nodes[u], nodes[v]);
    weights.push(w);
}

let (pred, cycle) = moorebellmanford::directed(&g, EdgeVec::from(weights), nodes[6]);
assert_eq!(cycle, None);
assert_eq!(pred[nodes[6]], None);
for &(u,p) in [(0,2), (1,0), (2,3), (4,1), (5,6)].iter() {
    assert_eq!(g.src(pred[nodes[u]].unwrap()), nodes[p]);
}