hypergraphx 0.0.5

use hashbrown::HashMap;
use std::collections::BinaryHeap;

use crate::traits::{CommonProperties, GraphBasics, GraphType};

use super::MinScored;
use super::measures::Measure;
// use crate::visit::{EdgeRef, IntoEdges, NodeCount, NodeIndexable, Visitable};

/// \[Generic\] k'th shortest path algorithm.
///
/// Compute the length of the k'th shortest path from `start` to every reachable
/// node.
///
/// The graph should be `Visitable` and implement `IntoEdges`. The function
/// `edge_cost` should return the cost for a particular edge, which is used
/// to compute path costs. Edge costs must be non-negative.
///
/// If `goal` is not `None`, then the algorithm terminates once the `goal` node's
/// cost is calculated.
///
/// Computes in **O(k * (|E| + |V|*log(|V|)))** time (average).
///
/// Returns a `HashMap` that maps `NodeId` to path cost.
///
pub fn k_shortest_path<'a, G: ?Sized, F, K, T: GraphType>(
    graph: &'a G,
    start: usize,
    goal: Option<usize>,
    k: usize,
    edge_cost: F,
) -> HashMap<usize, K>
where
    G: CommonProperties<'a, T, NodeIndex = usize>,
    F: Fn(<G as GraphBasics>::EdgeIndex) -> 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[node] += 1;
        let current_counter = counter[node];

        if current_counter > k {
            continue;
        }

        if current_counter == k {
            scores.insert(node, node_score);
        }

        // Already reached goal k times
        if goal.as_ref() == Some(&node) && current_counter == k {
            break;
        }

        for (cost, nodes) in
            graph.costed_neighbours(node, |edge_index| node_score + edge_cost(edge_index))
        {
            for next in nodes {
                if next == node {
                    continue; // Skip self-loops
                }
                visit_next.push(MinScored(cost, next));
                // if counter[next] < k {
                //     visit_next.push(MinScored(cost, next));
                // }
            }
        }
    }
    scores
}