hypergraphx 0.0.5

use core::marker::Copy;
use hashbrown::HashMap;
use hashbrown::hash_map::Entry::{Occupied, Vacant};
use std::collections::BinaryHeap;

use crate::prelude::*;

// use crate::algo::Measure;
use super::{MinScored, measures::BoundedMeasure};
// use crate::visit::{EdgeRef, IntoEdges, VisitMap, Visitable};

/// \[Generic\] Dijkstra's shortest path algorithm.
///
/// Compute the length of the shortest path from `start` to every reachable
/// node.
///
/// The function `edge_cost` should return the cost for a particular edge, which is used
/// to compute path costs.
///
/// If `goal` is not `None`, then the algorithm terminates once the `goal` node's
/// cost is calculated.
///
/// Returns a `HashMap` that maps node to path cost.
///
pub fn dijkstra<'a, G: ?Sized, F, K, T: GraphType>(
    graph: &'a G,
    start: G::NodeIndex,
    goal: Option<G::NodeIndex>,
    edge_cost: F,
) -> Result<HashMap<G::NodeIndex, K>, HypergraphErrors>
where
    G: CommonProperties<'a, T>,
    F: Fn(G::EdgeIndex) -> K,
    K: BoundedMeasure + Copy,
{
    let mut visited = graph.visit_map();
    let mut scores = HashMap::new();
    let mut visit_next = BinaryHeap::new();
    let zero_score = K::default();
    scores.insert(start, zero_score);
    visit_next.push(MinScored(zero_score, start));
    while let Some(MinScored(node_score, node)) = visit_next.pop() {
        if visited.contains(node.into()) {
            continue;
        }
        if goal.as_ref() == Some(&node) {
            break;
        }
        for (next_score, nodes) in
            graph.costed_neighbours(node, |edge_index| node_score + edge_cost(edge_index))
        {
            for next in nodes {
                if visited.contains(next.into()) {
                    continue;
                }
                match scores.entry(next) {
                    Occupied(ent) => {
                        if next_score < *ent.get() {
                            *ent.into_mut() = next_score;
                            visit_next.push(MinScored(next_score, next));
                        }
                    }
                    Vacant(ent) => {
                        ent.insert(next_score);
                        visit_next.push(MinScored(next_score, next));
                    }
                }
            }
        }
        visited.insert(node.into());
    }
    Ok(scores)
}