rs-graph 0.14.1

/*
 * Copyright (c) 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/>
 */

//! Dijkstra's shortest path algorithm.

use graph::{Digraph, Edge, IndexDigraph, IndexGraph, IndexNetwork, Node};
use shortestpath::binheap::BinHeap;
use shortestpath::heap::Heap;
use EdgeMap;

use num::traits::NumAssign;
use std::cmp::Ordering;
use std::collections::HashMap;
use std::hash::Hash;

/// Dijkstra's shortest path algorithm.
pub struct Dijkstra<'a, G, W, N, E, H = BinHeap<NodeItem<N, E, W>, usize>>
where
    G: 'a + IndexGraph<'a, Node = N, Edge = E>,
    N: 'a + Node + Hash,
    E: 'a + Edge,
    W: NumAssign + Ord + Copy,
    H: Heap<Key = NodeItem<G::Node, G::Edge, W>, Item = usize>,
{
    g: &'a G,
    items: HashMap<G::Node, usize>,
    heap: H,
}

impl<'a, G, W, N, E, H> Dijkstra<'a, G, W, N, E, H>
where
    G: 'a + IndexGraph<'a, Node = N, Edge = E>,
    N: 'a + Node + Hash,
    E: 'a + Edge,
    W: NumAssign + Ord + Copy,
    H: Heap<Key = NodeItem<G::Node, G::Edge, W>, Item = usize>,
{
    /// Create new data structure for running Dijkstra on a graph.
    pub fn new(g: &'a G) -> Self {
        Dijkstra {
            g: g,
            items: HashMap::new(),
            heap: H::new(),
        }
    }

    /// Compute a shortest path with Dijkstra's algorithm on an undirected graph.
    ///
    /// Each edge can be traversed in both directions with the same weight.
    ///
    /// - `weights` the (non-negative) edge weights
    /// - `src` the source node
    /// - `snk` the sink node
    ///
    /// Return the incoming edge for each node forming the shortest path
    /// tree.
    pub fn undirected<Weights>(
        &mut self,
        weights: Weights,
        src: G::Node,
        snk: Option<G::Node>,
    ) -> Vec<(G::Node, G::Edge)>
    where
        Weights: EdgeMap<'a, G, W>,
    {
        self.generic(weights, src, snk, |dist, w| dist + w, |g, u| g.neighs(u))
    }

    /// Solve shortest path with Dijkstra as bidirected graph.
    ///
    /// The graph is considered as bidirected graph with different weights
    /// for each direction.
    ///
    /// - `weights` the (non-negative) arc weights
    /// - `src` the source node
    /// - `snk` the sink node
    ///
    /// Return the incoming arc for each node forming the shortest path
    /// tree.
    pub fn bidirected<Weights>(
        &mut self,
        weights: Weights,
        src: G::Node,
        snk: Option<G::Node>,
    ) -> Vec<(G::Node, G::Edge)>
    where
        G: IndexNetwork<'a>,
        Weights: EdgeMap<'a, G, W>,
    {
        self.generic(weights, src, snk, |dist, w| dist + w, |g, u| g.neighs(u))
    }

    /// Solve shortest path with Dijkstra as directed graph.
    ///
    /// The graph is considered directed, travel is only allowed along
    /// outgoing edges.
    ///
    /// - `weights` the (non-negative) arc weights
    /// - `src` the source node
    /// - `snk` the sink node
    ///
    /// Return the incoming arc for each node forming the shortest path
    /// tree.
    pub fn directed<Weights>(&mut self, weights: Weights, src: G::Node, snk: Option<G::Node>) -> Vec<(G::Node, G::Edge)>
    where
        G: Digraph<'a>,
        Weights: EdgeMap<'a, G, W>,
    {
        self.generic(weights, src, snk, |dist, w| dist + w, |g, u| g.outedges(u))
    }

    pub fn generic<Weights, F, Neighs, It>(
        &mut self,
        weights: Weights,
        src: G::Node,
        snk: Option<G::Node>,
        accum: F,
        neighs: Neighs,
    ) -> Vec<(G::Node, G::Edge)>
    where
        Weights: EdgeMap<'a, G, W>,
        F: Fn(W, W) -> W,
        Neighs: Fn(&'a G, G::Node) -> It,
        It: Iterator<Item = (G::Edge, G::Node)>,
    {
        self.items.clear();
        self.heap.clear();

        let mut preds = vec![];

        self.items.insert(
            src,
            self.heap.insert(NodeItem::<_, G::Edge, _> {
                node: src,
                pred: None,
                weight: W::zero(),
            }),
        );

        while let Some(uitem) = self.heap.pop_min() {
            let u = uitem.node;
            let dist = uitem.weight;
            if let Some(e) = uitem.pred {
                preds.push((u, e));
            }

            // stop if reaching the sink
            if Some(u) == snk {
                break;
            }

            // mark the item as completed
            self.items.insert(u, usize::max_value());

            // go through all incident edges
            for (e, v) in neighs(self.g, u) {
                match self.items.get(&v) {
                    // unknown node
                    None => {
                        let newd = accum(dist, weights[e]);
                        self.items.insert(
                            v,
                            self.heap.insert(NodeItem {
                                node: v,
                                weight: newd,
                                pred: Some(e),
                            }),
                        );
                    }
                    // seen but uncompleted node
                    Some(&vitem) if vitem < usize::max_value() => {
                        let newd = accum(dist, weights[e]);
                        if newd < self.heap.key(vitem).weight {
                            self.heap.key(vitem).weight = newd;
                            self.heap.key(vitem).pred = Some(e);
                            self.heap.decrease(vitem);
                        }
                    }
                    // completed node
                    _ => (),
                }
            }
        }

        preds
    }
}

/// Compute a shortest path with Dijkstra's algorithm on an undirected graph.
///
/// Each edge can be traversed in both directions with the same weight.
///
/// - `g` the graph
/// - `weights` the (non-negative) edge weights
/// - `src` the source node
/// - `snk` the sink node
///
/// Return the incoming edge for each node forming the shortest path
/// tree.
///
/// # Example
///
/// ```
/// use rs_graph::*;
/// use rs_graph::shortestpath::dijkstra;
///
/// let mut g = LinkedListGraph::<u32>::default();
/// let mut weights: Vec<usize> = vec![];
///
/// let nodes: Vec<_> = (0..6).map(|_| g.add_node()).collect();
/// for &(u,v,w) in [(0,1,7), (0,2,9), (0,3,14),
///                  (1,2,10), (1,3,15),
///                  (2,3,11), (2,5,2),
///                  (3,4,6), (5,4,9)].iter() {
///     g.add_edge(nodes[u], nodes[v]);
///     weights.push(w);
/// }
///
/// let preds = dijkstra::undirected(&g, EdgeVec::from(weights), nodes[0], Some(nodes[4]));
/// assert_eq!(g.src(preds.iter().find(|&&(u,_)| u==nodes[2]).unwrap().1), nodes[0]);
/// assert_eq!(g.src(preds.iter().find(|&&(u,_)| u==nodes[5]).unwrap().1), nodes[2]);
/// assert_eq!(g.src(preds.iter().find(|&&(u,_)| u==nodes[4]).unwrap().1), nodes[5]);
/// ```
pub fn undirected<'a, 'b, G, Ws, W>(
    g: &'a G,
    weights: Ws,
    src: G::Node,
    snk: Option<G::Node>,
) -> Vec<(G::Node, G::Edge)>
where
    G: IndexGraph<'a>,
    G::Node: Hash,
    Ws: EdgeMap<'a, G, W>,
    W: NumAssign + Ord + Copy,
{
    let mut d = Dijkstra::<_, _, _, _, BinHeap<NodeItem<_, _, Ws::Output>, usize>>::new(g);
    d.undirected(weights, src, snk)
}

/// Solve shortest path with Dijkstra as bidirected graph.
///
/// The graph is considered as bidirected graph with different weights
/// for each direction.
///
/// - `g` the graph
/// - `weights` the (non-negative) arc weights
/// - `src` the source node
/// - `snk` the sink node
///
/// Return the incoming arc for each node forming the shortest path
/// tree.
pub fn bidirected<'a, G, Ws, W>(g: &'a G, weights: Ws, src: G::Node, snk: Option<G::Node>) -> Vec<(G::Node, G::Edge)>
where
    G: IndexNetwork<'a>,
    G::Node: Hash,
    Ws: EdgeMap<'a, G, W>,
    W: NumAssign + Ord + Copy,
{
    let mut d = Dijkstra::<_, _, _, _, BinHeap<NodeItem<_, _, W>, usize>>::new(g);
    d.bidirected(weights, src, snk)
}

/// Solve shortest path with Dijkstra as directed graph.
///
/// The graph is considered directed, travel is only allowed along
/// outgoing edges.
///
/// - `g` the graph
/// - `weights` the (non-negative) arc weights
/// - `src` the source node
/// - `snk` the sink node
///
/// Return the incoming arc for each node forming the shortest path
/// tree.
pub fn directed<'a, 'b, G, Ws, W>(g: &'a G, weights: Ws, src: G::Node, snk: Option<G::Node>) -> Vec<(G::Node, G::Edge)>
where
    G: IndexDigraph<'a>,
    G::Node: Hash,
    Ws: EdgeMap<'a, G, W>,
    W: NumAssign + Ord + Copy,
{
    let mut d = Dijkstra::<_, _, _, _, BinHeap<NodeItem<_, _, Ws::Output>, usize>>::new(g);
    d.directed(weights, src, snk)
}

pub fn generic<'a, G, W, Weights, F, Neighs, It, H>(
    g: &'a G,
    weights: Weights,
    src: G::Node,
    snk: Option<G::Node>,
    f: F,
    neighs: Neighs,
) -> Vec<(G::Node, G::Edge)>
where
    G: IndexGraph<'a>,
    G::Node: Hash,
    W: NumAssign + Ord + Copy,
    Weights: EdgeMap<'a, G, W>,
    F: Fn(W, W) -> W,
    Neighs: Fn(&'a G, G::Node) -> It,
    It: Iterator<Item = (G::Edge, G::Node)>,
    H: Heap<Key = NodeItem<G::Node, G::Edge, W>, Item = usize>,
{
    let mut d = Dijkstra::<_, _, _, _, BinHeap<NodeItem<_, _, W>, usize>>::new(g);
    d.generic(weights, src, snk, f, neighs)
}

#[derive(Clone, Copy)]
pub struct NodeItem<Node: Copy, Edge: Copy, W: Copy + PartialOrd> {
    node: Node,
    pred: Option<Edge>,
    weight: W,
}

impl<Node: Copy, Edge: Copy, W: PartialOrd + Copy> PartialEq for NodeItem<Node, Edge, W> {
    fn eq(&self, other: &Self) -> bool {
        self.weight.eq(&other.weight)
    }
}

impl<Node: Copy, Edge: Copy, W: PartialOrd + Copy> PartialOrd for NodeItem<Node, Edge, W> {
    fn partial_cmp(&self, other: &Self) -> Option<Ordering> {
        self.weight.partial_cmp(&other.weight)
    }
}