rs-graph 0.6.3

/*
 * Copyright (c) 2017 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::{Node, Edge, Digraph, IndexGraph, IndexDigraph, IndexNetwork};
use vec::{EdgeSlice, BiEdgeSlice};
use shortestpath::binheap::BinHeap;
use shortestpath::heap::Heap;

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

/// 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<'b>(&mut self,
                          weights: &EdgeSlice<'a,'b,G,W>,
                          src: G::Node,
                          snk: Option<G::Node>) -> Vec<(G::Node, G::Edge)>
    {
        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<'b>(&mut self,
                          weights: &BiEdgeSlice<'a,'b,G,W>,
                          src: G::Node,
                          snk: Option<G::Node>) -> Vec<(G::Node, G::Edge)>
        where G: IndexNetwork<'a>,
    {
        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<'b>(&mut self,
                        weights: &EdgeSlice<'a,'b,G,W>,
                        src: G::Node,
                        snk: Option<G::Node>) -> Vec<(G::Node, G::Edge)>
        where G: Digraph<'a>,
    {
        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: Index<G::Edge, Output=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, &EdgeSlice::new(&g, &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, W>(g: &'a G,
                                weights: &EdgeSlice<'a,'b,G,W>,
                                src: G::Node,
                                snk: Option<G::Node>) -> Vec<(G::Node, G::Edge)>
    where G: IndexGraph<'a>,
          G::Node: Hash,
          W: NumAssign + Ord + Copy,
{
    let mut d = Dijkstra::<_, _, _, _, BinHeap<NodeItem<_, _, W>, 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, 'b, G, W>(g: &'a G,
                                weights: &BiEdgeSlice<'a,'b,G,W>,
                                src: G::Node,
                                snk: Option<G::Node>) -> Vec<(G::Node, G::Edge)>
    where G: IndexNetwork<'a>,
          G::Node: Hash,
          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, W>(g: &'a G,
                              weights: &EdgeSlice<'a,'b,G,W>,
                              src: G::Node,
                              snk: Option<G::Node>) -> Vec<(G::Node, G::Edge)>
    where G: IndexDigraph<'a>,
          G::Node: Hash,
          W: NumAssign + Ord + Copy,
{
    let mut d = Dijkstra::<_, _, _, _, BinHeap<NodeItem<_, _, W>, 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: Index<G::Edge, Output=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)
    }
}