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
64
65
66
67
68
69
70

use crate::lowlink::LowlinkResult;

pub fn undirected_lowlink(
    v_size: usize,
    undirected_edges: &[(usize, usize)],
) -> LowlinkResult {
    let mut g = vec![vec![]; v_size];

    for (i, &(u, v)) in undirected_edges.iter().enumerate() {
        g[u].push((v, i));

        g[v].push((u, i));
    }

    let mut orders = vec![v_size; v_size];

    let mut order = 0;

    let mut low_orders = vec![v_size; v_size];

    fn compute_low_order(
        g: &[Vec<(usize, usize)>],
        orders: &mut [usize],
        order: &mut usize,
        low_orders: &mut [usize],
        u: usize,
        edge_from: usize,
    ) {
        orders[u] = *order;

        low_orders[u] = *order;

        *order += 1;

        for &(v, eid) in &g[u] {
            if orders[v] == g.len() {
                compute_low_order(g, orders, order, low_orders, v, eid);

                low_orders[u] = std::cmp::min(low_orders[u], low_orders[v]);
            } else if eid != edge_from {
                low_orders[u] = std::cmp::min(low_orders[u], orders[v]);
            }
        }
    }

    for u in 0..v_size {
        if orders[u] == g.len() {
            compute_low_order(
                &g,
                &mut orders,
                &mut order,
                &mut low_orders,
                u,
                undirected_edges.len(),
            );
        }
    }

    LowlinkResult { orders, low_orders }
}

// TOO
#[cfg(test)]

mod tests {

    #[test]

    fn test() {}
}