use std::collections::{BinaryHeap, HashMap};
use std::hash::Hash;
use crate::algo::Measure;
use crate::scored::MinScored;
use crate::visit::{EdgeRef, IntoEdges, NodeCount, NodeIndexable, Visitable};
pub fn k_shortest_path<G, F, K>(
graph: G,
start: G::NodeId,
goal: Option<G::NodeId>,
k: usize,
mut edge_cost: F,
) -> HashMap<G::NodeId, K>
where
G: IntoEdges + Visitable + NodeCount + NodeIndexable,
G::NodeId: Eq + Hash,
F: FnMut(G::EdgeRef) -> K,
K: Measure + Copy,
{
let mut counter: Vec<usize> = vec![0; graph.node_count()];
let mut scores = HashMap::new();
let mut visit_next = BinaryHeap::new();
let zero_score = K::default();
visit_next.push(MinScored(zero_score, start));
while let Some(MinScored(node_score, node)) = visit_next.pop() {
counter[graph.to_index(node)] += 1;
let current_counter = counter[graph.to_index(node)];
if current_counter > k {
continue;
}
if current_counter == k {
scores.insert(node, node_score);
}
if goal.as_ref() == Some(&node) && current_counter == k {
break;
}
for edge in graph.edges(node) {
visit_next.push(MinScored(node_score + edge_cost(edge), edge.target()));
}
}
scores
}