rs-graph 0.14.1

// Copyright (c) 2016, 2017, 2018 Frank Fischer <frank-fischer@shadow-soft.de>
//
// This program is free software: you can redistribute it and/or
// modify it under the terms of the GNU General Public License as
// published by the Free Software Foundation, either version 3 of the
// License, or (at your option) any later version.
//
// This program is distributed in the hope that it will be useful, but
// WITHOUT ANY WARRANTY; without even the implied warranty of
// MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
// General Public License for more details.
//
// You should have received a copy of the GNU General Public License
// along with this program.  If not, see  <http://www.gnu.org/licenses/>
//

use num::traits::NumAssign;

use {EdgeMap, Graph, IndexDigraph, IndexGraph, IndexNodeVec};

/// 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]);
/// }
/// ```
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,
{
    let mut pred = idxnodevec![g; None];
    let mut dist = idxnodevec![g; W::zero()];

    dist[src] = W::zero();

    for i in 0..g.num_nodes() {
        let mut changed = false;
        for e in g.edges() {
            let (u, v) = (g.src(e), g.snk(e));

            // skip source nodes that have not been seen, yet
            if u != src && pred[u].is_none() {
                continue;
            }

            let newdist = dist[u] + weights[e];
            if dist[v] > newdist || pred[v].is_none() {
                dist[v] = newdist;
                pred[v] = Some(e);
                changed = true;

                if i + 1 == g.num_nodes() {
                    return (pred, Some(v));
                }
            }
        }
        if !changed {
            break;
        }
    }

    (pred, None)
}

/// The shortest-path algorithm by Moore-Bellman-Ford on an undirected 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`.
pub fn undirected<'a, G, Ws, W>(
    g: &'a G,
    weights: Ws,
    src: G::Node,
) -> (IndexNodeVec<'a, G, Option<G::Edge>>, Option<G::Node>)
where
    G: 'a + IndexGraph<'a> + Graph<'a>,
    Ws: EdgeMap<'a, G, W>,
    W: NumAssign + Ord + Copy,
{
    let mut pred = idxnodevec![g; None];
    let mut dist = idxnodevec![g; W::zero()];

    dist[src] = W::zero();

    for i in 0..g.num_nodes() {
        let mut changed = false;
        for e in g.edges() {
            let (u, v) = g.enodes(e);
            for &(u, v) in &[(u, v), (v, u)] {
                // skip source nodes that have not been seen, yet
                if u != src && pred[u].is_none() {
                    continue;
                }

                let newdist = dist[u] + weights[e];
                if dist[v] > newdist || pred[v].is_none() {
                    dist[v] = newdist;
                    pred[v] = Some(e);
                    changed = true;

                    if i + 1 == g.num_nodes() {
                        return (pred, Some(v));
                    }
                }
            }
        }
        if !changed {
            break;
        }
    }

    (pred, None)
}