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
62
63

use crate::{
    adjacency_list_graph_old::AdjacencyList,
    dijkstra_sparse_queue::DijkstraSparseQueue,
    graph::edge::{
        From,
        To,
        Weight,
    },
    sssp_dijkstra_sparse_with_general::dijkstra_sparse,
};

/// return edge ids.

pub fn dijkstra_arborescense<E, Q>(
    v_size: usize,
    directed_edges: &[E],
    root: usize,
) -> Vec<usize>
where
    E: From<V = usize> + To<V = usize> + Weight<u64> + Clone,
    Q: DijkstraSparseQueue,
{
    let g = AdjacencyList::from((v_size, directed_edges.to_vec()));

    let dist = dijkstra_sparse::<_, Q>(g.edges(), root);

    let mut visited = vec![false; v_size];

    visited[root] = true;

    let mut added = vec![];

    for (i, e) in directed_edges.iter().enumerate() {
        let u = *e.from();

        let v = *e.to();

        if dist[u].is_none()
            || visited[v]
            || dist[u].unwrap() + e.weight() > dist[v].unwrap()
        {
            continue;
        }

        visited[v] = true;

        added.push(i);
    }

    debug_assert_eq!(added.len(), v_size - 1);

    added
}

// TODO
#[cfg(test)]

mod tests {

    #[test]

    fn test() {}
}