dsalgo 0.3.10

A package for Datastructures and Algorithms.
Documentation 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61

use crate::{
    dijkstra_sparse_queue::DijkstraSparseQueue,
    graph::edge::{
        To,
        Weight,
    },
};

// TODO: generalized dijkstra -> rename as extended dijkstra
pub fn general_dijkstra_sparse<E, T, F, Q>(
    sparse_graph: &[Vec<E>],
    callback: &F,
    mut data: T,
    src: usize,
) -> (Vec<Option<u64>>, T)
where
    E: To<V = usize> + Weight<u64>,
    F: Fn(&Vec<Option<u64>>, &mut T, usize, &E),
    Q: DijkstraSparseQueue,
{
    let n = sparse_graph.len();

    let mut hq = Q::default();

    let mut dist = vec![None; n];

    dist[src] = Some(0);

    hq.push((0, src));

    while let Some((du, u)) = hq.pop() {
        if du > dist[u].unwrap() {
            continue;
        }

        for e in sparse_graph[u].iter() {
            callback(&dist, &mut data, u, e);

            let v = *e.to();

            let dv = du + e.weight();

            if dist[v].is_some() && dv >= dist[v].unwrap() {
                continue;
            }

            dist[v] = Some(dv);

            hq.push((dv, v));
        }
    }

    (dist, data)
}

// TODO
// test on each specific problems
// like sssp, path-count, and predecessors, ....
#[cfg(test)]

mod tests {}